If G is a bipartite Euler and Hamiltonian graph, prove that complement of G, G is not Eulers.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 dG(upsilon) is even AA upsilon inV(G), where V(G) is set of vertices of the graph G.

Dylan Benitez

Dylan Benitez

Answered question

2022-11-04

If G is a bipartite Euler and Hamiltonian graph, prove that complement of G, 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 d G ( v ) is even v V ( G ), where V(G) is set of vertices of the graph G.
Now, let's look at some vertex v 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 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 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 G ¯ ( v ) is odd. That means G ¯ is not Eulerian;
If | X | = | Y | is odd, in 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 G ¯ is once again d G ¯ ( v ) = | X | 1 + m, but this time | X | 1is even, and m is odd. d G ¯ ( v ) is odd and that means G ¯ is not Eulerian.
Thank You!

Answer & Explanation

Sean Sutton

Sean Sutton

Beginner2022-11-05Added 17 answers

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 2 l which is even. This implies that every vertex in the complement G ¯ of G will have odd degree [indeed, d G ¯ ( v ) = n G 1 d G ( v ) = 2 l 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 G ¯ is not Eulerian.
[However, G ¯ can still be Hamiltonian itself. In fact, if G is a cycle on (say) 16 vertices then G ¯ is Hamiltonian.]

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?