0
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ 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? $\endgroup$
    – Hendrix
    Commented Nov 30, 2019 at 18:17
  • 1
    $\begingroup$ $n$ must be even. So that finishes it. I got it $\endgroup$
    – user728115
    Commented Nov 30, 2019 at 18:26

1 Answer 1

1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.