Condition about regular graphs

Question

I am trying to do this graph theory exercise:

Let graph $G$ doesn't contain triangle and for each unconnected vertices of $G$ exists exactly two vertices that are neighbors of both. Show that graph is regular.

I can imagine only two cases of such graphs $K_2$ and $C_4$. Are there other such graphs? I need hint how to construct them.

Answer 1

Here is a proof of why the degrees have to be equal. Let $p$ be any node and $k = \deg(p)$ its degree. Assume $p$ is adjacent to nodes $v_1, v_2, \ldots, v_k$. We want to show that $\deg(v_i) = k$.

Firstly, from the triangle condition, none of the $v_i$ are adjacent. Since they are not adjacent we can, for any pair of vertices $v_i, v_j$, find a vertex $w$ which is adjacent those two. Note that this $w$ is distinct for all pairs $v_i, v_j$, otherwise $w$ and $p$ would share more than two neighbours.

Thus, with all these edges added we have that $\deg(v_i) = \deg(p)$ (you add in one edge for every other $v_j$).

What we need to show now is that there is no way we can add more edges to any $v_i$. Assume $q$ is adjacent to $v_i$, and since it is not adjacent to $p$, to some $v_j$. But now $v_i, v_j$ have three neighbours: $w, p, q$. Contradiction.

edit the following seems to be an example with degree 5.

Let $p, v_1, \ldots, v_5$ be as above, and $w_{ij}$ is adjacent to $v_i$ and $v_j$, for $i<j$. Add in the edges $[w_{ij}, w_{kl}]$ for $k>i, k\neq j, l\neq j$.

Every vertex has degree 5, no connected vertices share a neighbour, and seemingly the last condition is satisfied as well?

edit 2: it is a small exercise to see that it fails with $\deg(p) =3$ or $\deg(p) = 4$.

edit 3: as noted in the other answer, the example above is the Clebsch graph.

Answer 2

Once you know the graph is regular, it follows that your graph is strongly regular with parameters $$ \binom{k}{2}+1,\ k,\ 0,\ 2. $$ In addition to the 4-cycle, there are two other examples - The Gewirtz graph on 56 vertices with $k=10$ and the one in the other example, known as the Clebsch graph. I think the details are all in Biggs's book "Finite Groups of Automorphisms".