The complement of $G$, $\overline{G}$, is the graph formed only by connecting with an arc all nodes $x$ and $y$ such that $x$ and $y$ are not connected by an arc in G.

The theory that I am asked to prove is that if a simple graph $G$ with odd $n >= 1$ nodes has an Euler circuit, then the complement of $G$ will also have an Euler circuit, if $\overline{G}$ connected.

My basic idea for this proof is to use the fact that all nodes in $G$ have even degree to prove that all nodes in $\overline{G}$ have even degree, which would be sufficient to show that $\overline{G}$ has an Euler circuit. I have tried to use ideas about how each node in $\overline{G}$ will have degree $n - deg(node)$ degree, but I haven't really made any progress. Could anyone give me a hint?

  • $\begingroup$ Suppose $G$ is a cycle of length 6. Then every vertex in the complement has degree 3, right? $\endgroup$ – Gerry Myerson Apr 11 '18 at 9:50
  • 1
    $\begingroup$ @GerryMyerson Thank you, your comment made me realise that I misread the question - it specifies that n must be odd. I will be able to do the question now I think. $\endgroup$ – James Williams Apr 11 '18 at 10:51
  • 1
    $\begingroup$ Good. When you have it done, let me encourage you to write it up and post it as an answer. $\endgroup$ – Gerry Myerson Apr 11 '18 at 12:14
  • $\begingroup$ @GerryMyerson Well I was massively overthinking this problem... I wrote up my answer and added it below. I think my answer is a bit cumbersome, but I think it's correct. $\endgroup$ – James Williams Apr 12 '18 at 11:59
  • 1
    $\begingroup$ Looks fine to me. $\endgroup$ – Gerry Myerson Apr 12 '18 at 12:21

I figured out the answer, I believe:

Suppose we have some simple graph $G$, with odd $n \ge 1$ nodes, and that this graph has an Euler circuit.

Now consider an arbitrary node in $\overline{G}$. The degree of this node will be $(n-1)$ minus the degree of the corresponding node in $G$, since there are $n-1$ possible arcs from the node. Then the degree of the node will be of the form $$(n-1) - 2m$$ for some $m$, since the degree of all nodes in $G$ are even. But since $n$ is odd, we can write $n$ as $2k + 1$ for some k, and then we have the degree of the node as $$(2k + 1 - 1) - 2m$$$$=2k-2m$$$$=2(k - m)$$ for some integers $k$, $m$, and therefore the degree of the node is even.

Since all nodes in $\overline{G}$ have even degree, and $\overline{G}$ is connected, we can conclude that $\overline{G}$ has an Euler circuit.


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.