## Euler’s Theorem by Induction on Vertices

In my Discrete Math class today, Ryan Patton asked to prove Eulerâ€™s circuit theorem by induction on the number of vertices. Alex Summers contributed an idea about pairing/short-cutting instead of removing the edges incident to a deleted vertex. The class came up with the following proof. Is this proof out there somewhere?

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

Proof by induction on the number *n* of vertices.

Base case *n*=1. Just follow the loops in succession.

Now assume for *n* and prove for a pseudo-graph of *n*+1 vertices. Pick a vertex. Since degree even, you can pair the incident edges, and you can avoid pairing the two ends of a loop. Short-cut each pair to avoid the vertex and delete it. By induction, each component of the new pseudo-graph has the desired circuit. Now restore the vertex and undo the short cuts to obtain the desired circuit.