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