Frank Morgan

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.