Prove or disprove:

  1. If $G$ is an Euler graph with even number of vertices then it's bipartite.

  2. If $G$ is an Euler and bipartite graph then the number of its vertices is even.

The second claim is false I think because for example for a graph of $7$ vertices we can construct Euler circuit and it can be a bipartite graph. This is the illustration:

enter image description here

Regarding the second claim because it's an Euler graph then the degree of every vertex is even. But I don't see how to use this fact to prove that it is/is not a bipartite graph.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.