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?
[Math] Every edge with even degree -> Euler tour
graph theory
Best Answer
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.