Triangle-free graph where every pair of nonadjacent vertices has exactly two common neighbors

Question

Consider triangle-free graphs where every pair of nonadjacent vertices has exactly two common neighbors.

Except for $K_1$, $K_2$ and $C_4$, I could not find any other graphs. When I go beyond $4$ vertices, it seems that I am forced to add more and more vertices in order to satisfy the required condition, while avoiding triangles.

Are there any other graphs?

Answer 1

Here is a counterexample on $16$ vertices. Visualize the Petersen graph as the complement of $L(K_5)$ (i.e, a graph with with as vertices the $2$-element subsets of $[5]$ connecting $I$ and $J$ iff $I\cap J=\emptyset$). Next add in $5$ extra vertices and call them $1,2,3,4,5$, connect $\{i,j\}$ with $i$ and $\{i,j\}$ with $j$. Finally, add in one final vertex, say $0$ and connect $01,02,\dots,05$. This graph is $3$-regular, triangle-free, and satisfies the neighbours hypothesis.

Here is a proof that graphs of the type you describe are always $d$-regular where $d(d+1)/2+1=n$. Isolate a vertex $p$, and say it has $d$ neighbours $a_1,\dots,a_d$. For all $1\le i<j\le d$, there is a unique vertex $b_{ij}\ne p$ connected to $a_i,a_j$ and none of the other $a_k$ by applying the hypothesis to $\{a_i,a_j\}$ and $\{p,b_{ij}\}$. Moreover, there are no other nonadjacent vertices to $p$ than the $b_{ij}$. Hence the number of $b_{ij}$ can be counted in 2 ways and is equal to $$\binom{d}{2}=n-1-d,$$ implying the graph is regular and $d(d+1)/2+1=n$.

From the proof it follows that for $d=0,1,2$ we get $K_1,K_2,C_4$, for $d=4$ there is no possible such graph, the one described above. For $d=5$ there is a unique such graph. For $d\ge 6$ I believe there are also counterexamples, but the construction is more messy. Similarly I expect them to arise by adding some vertices to a Kneser graph.

Answer 2

Building upon the hard work of ArtW, who gave an excellent proof of regularity, we know that there are only two known examples of such graphs in the mathematical literature, excluding the trivial cases. They are:

• The Clebsch graph, with $16$ nodes and degree $5$, which is what ArtW constructed.
• The Gewirtz graph, which has $56$ nodes and degree $10$.

If you were to find another graph of your kind, which is a special case of a triangle free strongly regular (TFSR) graph, then you will make a breakthrough in graph theory. So I doubt we'll do it on MSE.

See this link for the seven known TFSR graphs, two of which are the above graphs I named that fit your criteria.