Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
The graph needs to be connected as well. –  Michael Biro Oct 26 '12 at 5:23
    
Yes, you are right. The graph is connected and undirected. I modified the post. –  CaptainObvious Oct 26 '12 at 5:24

1 Answer 1

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.

share|improve this answer
    
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. –  CaptainObvious Oct 26 '12 at 5:28
1  
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? –  ronno Oct 26 '12 at 5:33
    
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? –  CaptainObvious Oct 26 '12 at 6:26
    
Components are by definition connected, but what can you say about them by induction? –  ronno Oct 26 '12 at 6:28
    
Could you tell me....? –  CaptainObvious Oct 26 '12 at 16:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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