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.

• @ml0105, the cube, 8 vertices, 12 edges, 2 opposite vertices have no common neighbors. – Gerry Myerson Apr 4 '14 at 22:13
• I stand corrected. The hypercube isn't a good candidate for the general case. I think my other construction holds, though. Thanks for catching that, Gerry Myerson! – ml0105 Apr 4 '14 at 22:14
• @ml0105 In your construction with $C_8$, vertices 1 and 3 are non-adjacent, but both are adjacent to 2, 4, and 6. – Perry Elliott-Iverson Apr 4 '14 at 22:20
• Do you also want a hint on how to do that exercise, or just on how to construct examples? – bof Apr 4 '14 at 22:25
• @bof I just need example of such graph or prove that it doesn't exist – Ashot Apr 5 '14 at 7:26

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.

• uhm, given that this is correct(:-), this restricts the degree to a maximum of 2. – M.B. Apr 4 '14 at 23:02
• Ashot did not ask for a proof that the graph has to be regular; he asked if there are any examples besides $K_2$ and $C_4$. It would follow from the claim in your comment that there are no more examples. But I don't see how your comment follows from the argument you gave in your answer. – bof Apr 5 '14 at 8:10
• @bof: you're right. Let me think about the details tomorrow; perhaps one can do degree > 2. With that being said - I wrote the answer as I enjoyed solving the problem :-) – M.B. Apr 5 '14 at 9:22
• Here's another proof that $G$ is regular. Since $G$ is connected, it's enough to show that adjacent vertices have the same degree. If $u$ and $v$ are adjacent, then each vertex in $N(u)\setminus\{v\}$ is adjacent to one and only one vertex in $N(v)\setminus\{u\}$, and vice versa. This one-to-one correspondence shows that $|N(u)\setminus\{v\}|=|N(v)\setminus\{u\}|$, and so $\operatorname{deg}(u)=\operatorname{deg}(v)$. – bof Apr 5 '14 at 9:37
• By the way, if a graph satisfying that condition has degree $k$, then the number of vertices must be $\binom{k+1}2+1$. – bof Apr 5 '14 at 9:39

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".

• What is a strongly regular graph? What is the meaning of the parameters? Links? And what is wrong with the example given in the other answer? – bof Apr 6 '14 at 2:14
• Just google on strongly regular graph for unexplained terms. There's nothing wrong with the other example, I've edited my answer. – Chris Godsil Apr 6 '14 at 12:37
• Interesting, did not know that it had a name. Thanks. – M.B. Apr 6 '14 at 16:07