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

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

• A connected regular graph that isn't Eulerian has $n$ vertices of degree $2k+1$, or odd degree. What can you say about the parity of $n$ if the sum of the degrees must be even? Nov 30, 2019 at 18:17
• $n$ must be even. So that finishes it. I got it
– user728115
Nov 30, 2019 at 18:26

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