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 2 of 6: Separate the distance-two vertices

Previous step Next step

C_{ij}\ne C_{hk}\text{ for distinct pairs }(i,j)\ne(h,k);\qquad\operatorname{dist}(A,X)\le2.

Detailed analysis

All $C_{ij}$ are distinct: if one were shared by different $B_i$ and $B_h$ , the nonadjacent pair would have two common neighbors, $A$ and that vertex. Every vertex $X$ is either $A$ , adjacent to $A$ , or nonadjacent to $A$ and hence shares a neighbor with $A$ by (iii). Thus $\operatorname{dist}(A,X)\le2$ .