"An Eulerian tour is a walk that goes over every edge exactly once. If G is a graph on n vertices such that degree of each vertex is even then prove that G has an Eulerian tour."

I'm thinking since the degree of each vertex is even, then there will be a cycle in the graph. I don't know how much this helps though, because I don't know how to prove that there is a cycle that goes through every edge exactly once.
Thanks for any help!

  • 1
    $\begingroup$ Are sure the problem doesn't say anything about the graph being connected? $\endgroup$ – bof Mar 11 '14 at 23:46
  • $\begingroup$ It doesn't say anything about being connected. I think he wants us to assume that it is though $\endgroup$ – Ryan McClure Mar 12 '14 at 2:38

Of course we need connectedness (otherwise 2 disjoint triangles is a counterexample). First it has to contain a cycle you can keep walking, because the edges have even degree, eventually you need to reach a point you have already crossed. (This gives a cycle.) If this is not a euler tour then there are edges not contained in you cycle then walk along that edge you reach a vertex that has an odd degree of never walked edges. So walk along such an edge. You can keep doing that and you have to return sometime, if not then you are stranded somewhere. This is only possible when you come to an edge and there are no "never walked" edges anymore this means that that vertex has an odd degree this gives a contradiction.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.