Euler tour is a closed walk that can traverse each edge in a graph exactly once.

If every edge in a connected undirected graph has even degree, how can you prove that it has an Euler tour?

  • 1
    $\begingroup$ The graph needs to be connected as well. $\endgroup$ Oct 26 '12 at 5:23
  • $\begingroup$ Yes, you are right. The graph is connected and undirected. I modified the post. $\endgroup$ Oct 26 '12 at 5:24

Hint: Find a cycle, and use induction.

Expanded: Find a closed walk in the graph. Remove this from the graph, and consider the remaining subgraph. Each vertex had an even number of edges removed, so they still have even degree. Hence each component satisfies the conditions for the original graph, and hence by induction (on the number of edges) each has an Eulerian tour. Now, we have finitely many edge disjoint closed walks which cover the whole graph, and each of which intersect the first one at some vertex. Thus we can attach them to the initial closed walk one by one and get an Eulerian tour of the whole graph. For the base case (no edges), notice that it has to have exactly one vertex, and hence the empty walk suffices.

  • $\begingroup$ Thanks for your answering. I am thinking of the following procedure: traverse the graph from vertex u, and get a closed walk. If there are edges left, start from the vertex in the current closed walk that has an untraversed edge (*). And find another closed walk. But the problem is how can we ensure in the recursive steps *, we can always find a closed walk. Maybe some of the edges inside the closed walk we need to traverse have already been traversed by previous steps. That's my question. $\endgroup$ Oct 26 '12 at 5:28
  • 1
    $\begingroup$ What if you remove the closed walk you obtained from the original graph? The remaining subgraph might not be connected, but what can you say about each component? $\endgroup$
    – ronno
    Oct 26 '12 at 5:33
  • $\begingroup$ The remaining subgraph must have at least one vertex that is incident to an untraversed edge. And that vertex must have even number of degrees. Oh, because each remaining vertex has even number of degrees, so they each has at least a degree of two. So each of the remaining component is connected. Am I right? $\endgroup$ Oct 26 '12 at 6:26
  • $\begingroup$ Components are by definition connected, but what can you say about them by induction? $\endgroup$
    – ronno
    Oct 26 '12 at 6:28
  • $\begingroup$ Could you tell me....? $\endgroup$ Oct 26 '12 at 16:04

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.