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 4 of 6: Restart the argument at each

B_i

Previous step Next step

\deg A=\deg C_{ij}=m\Longrightarrow\deg B_i=m\quad(1\le i\le m).

Detailed analysis

The argument just used has a general form: for any root of degree $r$ , every vertex at distance two from it has degree $r$ . Since condition (i) excludes $m=1$ , choose $k\ne i$ . The edge supplied in the previous step between $C_{ij}$ and some $C_{kh}$ makes $B_i$ a distance-two vertex from $C_{kh}$ ; because $\deg(C_{kh})=m$ , this gives $\deg(B_i)=m$ . Thus $A$ , every $B_i$ , and every $C_{ij}$ have degree $m$ .