Euler's Circuit Theorem

Here is a neat way to prove Euler's circuit theorem using induction on the number of vertices.

Theorem. A pseudograph has a circuit containing all edges and vertices if it is connected and every vertex has even degree.

Proof. This proof is by induction on the number n of vertices.

Base case of n = 1. Follow the loops in succession.

Assume for n and prove for a pseudograph of n+1 vertices. Now pick a vertex. Since the degree is even, you can pair the incident edges, and you can avoiding pairing the two ends of a loop. Shortcut each pair to avoid the vertex and delete it. By induction, each component of the new pseudograph has the desired circuit. Then restore the vertex and undo the shortcuts to obtain the desired circuit.