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.

Leave a Reply

Your email address will not be published. Required fields are marked *