Problem 4

Let G be a graph with n vertices satisfying: (i) no vertex is joined to all the other vertices; (ii) there are no triangles; (iii) for every two nonjoined vertices A and B, there is exactly one vertex C joined to both. Prove that every vertex has the same degree, and find the smallest possible n.

Step 6 of 6: Find the minimum and construct it

Previous step Next step

m=1\Rightarrow n=2\text{ violates (i)};\qquad m=2\Rightarrow n=5,\quad C_5\text{ works}.

Detailed analysis

For m=1, n=2 and each vertex is joined to all other vertices, violating (i). Thus m>=2 and n>=5. The 5-cycle has no triangle, no universal vertex, and exactly one common neighbor for each nonjoined pair, so it satisfies all conditions and attains n=5.