Let $G$ be a connected regular graph that isn't Eulerian. Prove that if $\overline{G}$ is connected, then $\overline{G}$ is Eulerian

Question

Let $G$ be a connected regular graph that isn't Eulerian. Prove that if $\overline{G}$ is connected, then $\overline{G}$ is Eulerian

I tried to solve this problem with no progress.

Suppose $G$ is a regular graph that isn't Eulerian. Then all of the vertices in $G$ have degree $2k + 1$ for some $k$. Now the degree of the vertices in $\overline{G}$ is given by

$$(n - 1) -(2k + 1) = n - 2(k + 1).$$

But this doesn't quite work out for when $n$ is odd (the quantity becomes odd, and we know Eulerian iff all vertices have even degree).

Can someone please help me?

Answer 1

This question is a problem in Gary Chartrand and Ping Zhang's A first Course In Graph Theory. I implore those studying Graph Theory to give this an honest attempt. Here are some hints:

1. $G$ must be $r$-regular. What can be said about $r$?
2. Since $G$ is $r$-regular. How about $\overline{G}$?
3. What is the parity of the order of $G$?

Solution:

Theorem 1) A nontrivial connected graph $G$ is Eulerian if and only if every vertex of $G$ has even degree.

Proof. Let $G$ be connected, regular and not Eulerian. Then $G$ must be $2k+1$ regular for some $k\in\mathbb{N}$. Suppose not, $G$ is $2k$ regular, then $G$ is Eulerian by Theorem 1. Thus for all $v\in V(\overline{G})$, $$\deg(v)=n-1-2k+1=n-2k.$$ Then for $G$, $\sum_{i=1}^n\deg(v_i)=(2k+1)*n$. Hence $n$ even and for $v\in V(\overline{G})$, $\deg(v)$ even. Therefore by Theorem 1. $\overline{G}$ is Eulerian. □