If $G$ is a bipartite Euler and Hamiltonian graph, prove that complement of $G$, $\bar G$ is not Eulers.

Question

I would like to know if my proof of the statement in the title is correct.

So, I started like this:

As $G$ is a bipartite graph, it has two sets $X$ and $Y$. Using the condition $G$ is Hamiltonian, then $|X| = |Y|$.

As $G$ is also Eulerian, stands $d_G(v)$ is even $\forall v \in V(G)$, where $V(G)$ is set of vertices of the graph $G$.

Now, let's look at some vertex $v \in X(G)$. As stated above, it's degree is even. Let's look at two possible cases:

• If $|X| = |Y|$ is even too, then in $\bar G$, $v$ will be connected with all the remaining vertices from $X$. That vertex $v$ will also be connected with remaining vertices from $Y$, with which it wasn't connected in the graph $G$. That is, $d_\bar G(v) = |X| - 1 + m$, where $m$ represents number of remaining vertices from $Y$. As $|X|$ is even, then $|X| - 1$ is odd, and $m$ is also even, because $d_G(v)$ is even and $|Y|$ is even, so the remaining number of vertices, $m$ is even too. Sum of an even and an odd number is odd, so $d_\bar G(v)$ is odd. That means $\bar G$ is not Eulerian;
• If $|X| = |Y|$ is odd, in $\bar G$, $v$ will be connected with all the remaining vertices from $X$ and all the remaining vertices from $Y$, and let's call the number of $Y$ remaining vertices $m$. As $|Y|$ is odd and $d_G(v)$ is even, then $m$ is odd. Degree of $v$ in $\bar G$ is once again $d_\bar G(v) = |X| - 1 + m$, but this time $|X| - 1$ is even, and $m$ is odd. $d_\bar G(v)$ is odd and that means $\bar G$ is not Eulerian.

Thank You!

Excuse me for my bad English, I tried to write this as clear as I can.

Answer 1

Your line of reasoning is correct. There is a simpler way to prove/disprove this though: If $G$ is bipartite Eulerian with both sides having the same number $l$ of vertices, then the number $n_G$ of vertices in $G$ is $2l$ which is even. This implies that every vertex in the complement $\bar{G}$ of $G$ will have odd degree [indeed, $d_{\bar{G}}(v) = n_G-1-d_G(v) =2l-1-d_G(v)$ where $d_G(v)$ the degree of vertex $v$ in $G$; make sure you see why this is so and why it is odd]. So $\bar{G}$ is not Eulerian.

[However, $\bar{G}$ can still be Hamiltonian itself. In fact, if $G$ is a cycle on (say) 16 vertices then $\bar{G}$ is Hamiltonian.]