MathLabs

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 5 of 6: Count the vertices
Previous stepNext step
n=1+m+m(m−1)=m2+1.n=1+m+m(m-1)=m^2+1.
Detailed analysis

There are A, its m neighbors B_i, and m-1 further neighbors for each B_i. These latter sets are disjoint by the uniqueness condition, and there are no vertices beyond distance two. Hence n=m^2+1.