# Prove if $G$ has an Euler circuit, then the complement of $G$ will also have an Euler circuit, if connected

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?

• Suppose $G$ is a cycle of length 6. Then every vertex in the complement has degree 3, right? – Gerry Myerson Apr 11 '18 at 9:50
• @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. – James Williams Apr 11 '18 at 10:51
• Good. When you have it done, let me encourage you to write it up and post it as an answer. – Gerry Myerson Apr 11 '18 at 12:14
• @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. – James Williams Apr 12 '18 at 11:59
• Looks fine to me. – Gerry Myerson Apr 12 '18 at 12:21

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.