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 3 of 6: Count the degree of

C_{ij}

Previous step Next step

\deg(C_{ij})=1+(m-1)=m.

Detailed analysis

Besides $B_i$ , any neighbor of $C_{ij}$ must be some $C_{hk}$ : it cannot be $A$ (a triangle with $A,B_i$ ), and if it were $B_k$ for $k\ne i$ , then the nonadjacent pair $B_i,B_k$ would have common neighbors $A$ and $C_{ij}$ . For each $k\ne i$ , at most one $C_{kh}$ can neighbor $C_{ij}$ , or $B_k$ and $C_{ij}$ would have two common neighbors. The pair $B_k,C_{ij}$ is nonadjacent, so it has a unique common neighbor; it must be such a $C_{kh}$ , not $A$ . Hence there is exactly one for each $k\ne i$ , and $\deg(C_{ij})=1+(m-1)=m$ .