0

Let $G=(V,E)$ be a simple, disconnected graph with at least $2$ vertices. $G$ has exactly two vertices of even degree. Let $G'=(V,E')$ be the complement graph of $G$. Prove that $G'$ has Eulerian path.

I think we have two cases when $|V|$ is odd or even. If $|V|$ is odd then the degrees of vertices $x,y$ (whose degrees are even in $G$) will be odd in $G'$ while all the degrees of all other vertices will be even. Also $G'$ is connected (the proof is here). This satisfies the definition of Eulerian path: there's either $0$ or $2$ vertices of odd degree in a graph.

But what if $|V|$ is even? Then the degrees of $x,y$ are even and there're $|V|-2$ vertices of odd degree which is not necessarily a Eulerian path.

How can I prove this when $|V|$ is even?

Yos
  • 2,663
  • 1
    You have it backwards. If $|V|$ is odd, then a vertex with even degree in $G$ will have even degree in $G'$; if $|V|$ is even, then a vertex with even degree in $G$ will have odd degree in $G'$. – bof Jun 27 '18 at 11:00
  • 1
    Observe that $d_G(x)+d_{G'}(x)=|V|-1.$ – bof Jun 27 '18 at 11:01
  • @bof thank you for the correction. In this case everything works out. If $|V|$ is odd then there're $0$ vertices with odd degree. If $|V|$ is even there're exactly two vertices with odd degrees! – Yos Jun 27 '18 at 11:10
  • 1
    Think again about the odd case. In any finite graph, the number of vertices of odd degree is even. If the number of vertices of even degree is $2$ (or any even number) then $|V|$ must be even. – bof Jun 27 '18 at 11:33

0 Answers0