Euler's theorem on Eulerian circuits
Statement
A connected finite multigraph has an Eulerian circuit — a closed walk that traverses every edge exactly once — if and only if every vertex has even degree.
Why is it true?
Whenever a walk enters a vertex along one unused edge, it must leave along a different unused edge, pairing up the edges incident to that vertex two by two. If every vertex has an even number of edges, you can never get stranded mid-walk except back where you started, and any leftover loops can be spliced into the main tour.
Proof sketch
Necessity is immediate since each visit to a vertex uses two incident edges (one in, one out). For sufficiency, start at any vertex and walk along unused edges until stuck; even degrees guarantee the walk can only get stuck at the starting vertex, forming a closed trail. If unused edges remain, by connectedness some vertex on the trail still has unused incident edges; start another closed trail from there in the residual graph (which still has all even degrees) and splice it in, repeating until all edges are used.
Stated by
Topics that use this theorem
Related theorems
Step-by-step proofs
No step-by-step proof yet for this theorem.
References
- Leonhard Euler (1741). Solutio problematis ad geometriam situs pertinentis · DOI:10.1090/spec/098/33