If G is a bipartite Euler and Hamiltonian graph, prove that complement of G, is not Eulers.
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 is even , where V(G) is set of vertices of the graph G.
Now, let's look at some vertex . As stated above, it's degree is even. Let's look at two possible cases:
If |X|=|Y| is even too, then in , 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, , where m represents number of remaining vertices from Y. As |X| is even, then |X|−1 is odd, and m is also even, because 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 is odd. That means is not Eulerian;
If is odd, in , 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 is odd and is even, then m is odd. Degree of v in is once again , but this time is even, and m is odd. is odd and that means is not Eulerian.
Thank You!