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 1 of 6: Choose a vertex and name its neighbors

Previous step Next step

N(A)=\{B_1,\ldots,B_m\},\qquad\deg A=m.

Detailed analysis

Choose $A$ with degree $m$ and call its neighbors $B_1,\ldots,B_m$ . No two $B_i$ are adjacent, or they and $A$ form a triangle. For each $i$ , label the $\deg(B_i)-1$ neighbors of $B_i$ other than $A$ as $C_{ij}$ .