= Triangle-free graphs with three common neighbours
{title2=$n=1+d(d+2)/3,\quad d\in\{1,3,21\}$}
For a finite simple graph with at least two vertices, no triangles, and exactly three common neighbours for every nonadjacent pair, the graph is connected. For adjacent vertices $u,v$, the bipartite graph between $N(u)\setminus\{v\}$ and $N(v)\setminus\{u\}$ has degree two at every vertex, forcing $d(u)=d(v)$. Thus the graph is regular. Counting second neighbours gives $3(n-d-1)=d(d-1)$. The nontrivial adjacency eigenvalues are $(-3\pm\sqrt{4d-3})/2$, and the larger-root multiplicity is $[n-1+d^2/\sqrt{4d-3}]/2$. Integrality forces $t=\sqrt{4d-3}$ to be an odd integer dividing $9$, yielding the stated degrees. The complete bipartite graph $K_{3,3}$ realizes degree three. The one-vertex graph is a vacuous exception with degree zero.
Back to article page
