To start, say that a vertex is even if it has an even number of edges coming into it, and odd otherwise. We want to trace any graph with two or fewer odd vertices.

At first, don't worry about hitting all the edges, and just trace a path. Keep in mind that once our path gets going, it will never get stuck at an even vertex.

There are two cases:

1. If the graph has no odd vertices, pick any vertex to start the path. Once you leave the start vertex, it is left with an odd number of edges. Wander as long as possible, until you're stuck. Because every other vertex was even, you can only get stuck back at the start.
2. If the graph has an odd vertex, start there. It will be left with an even number of edges after you depart, so your path must end at some other odd vertex. This also shows that no graph can have exactly one odd vertex!

Suppose you color the edges of your original path. You may have missed some edges, but there will always be an even number of uncolored edges at every vertex (zero is even). Now make your path longer:

• Follow the original path until you reach an uncolored edge.
• Take a detour, following only uncolored edges. Because each vertex had an even number of uncolored edges, you will eventually return to the start of the detour.
• Finish your original path. Repeat this lengthening process until the whole graph is traced.