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.

  • 2
    $\begingroup$ @ml0105, the cube, 8 vertices, 12 edges, 2 opposite vertices have no common neighbors. $\endgroup$ – Gerry Myerson Apr 4 '14 at 22:13
  • 1
    $\begingroup$ 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! $\endgroup$ – ml0105 Apr 4 '14 at 22:14
  • $\begingroup$ @ml0105 In your construction with $C_8$, vertices 1 and 3 are non-adjacent, but both are adjacent to 2, 4, and 6. $\endgroup$ – Perry Elliott-Iverson Apr 4 '14 at 22:20
  • $\begingroup$ Do you also want a hint on how to do that exercise, or just on how to construct examples? $\endgroup$ – bof Apr 4 '14 at 22:25
  • $\begingroup$ @bof I just need example of such graph or prove that it doesn't exist $\endgroup$ – 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.

  • $\begingroup$ uhm, given that this is correct(:-), this restricts the degree to a maximum of 2. $\endgroup$ – M.B. Apr 4 '14 at 23:02
  • $\begingroup$ 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. $\endgroup$ – bof Apr 5 '14 at 8:10
  • $\begingroup$ @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 :-) $\endgroup$ – M.B. Apr 5 '14 at 9:22
  • $\begingroup$ 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)$. $\endgroup$ – bof Apr 5 '14 at 9:37
  • $\begingroup$ By the way, if a graph satisfying that condition has degree $k$, then the number of vertices must be $\binom{k+1}2+1$. $\endgroup$ – 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".

  • $\begingroup$ 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? $\endgroup$ – bof Apr 6 '14 at 2:14
  • $\begingroup$ Just google on strongly regular graph for unexplained terms. There's nothing wrong with the other example, I've edited my answer. $\endgroup$ – Chris Godsil Apr 6 '14 at 12:37
  • $\begingroup$ Interesting, did not know that it had a name. Thanks. $\endgroup$ – M.B. Apr 6 '14 at 16:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.