Theorem 5.13 — Euler: a graph is eulerian iff it is connected and all degrees are even
ProvedAppliedComb.Graphs.eulerian_iffLet be a finite graph without isolated vertices (every vertex has at least one neighbour). Then is eulerian (it has a closed sequence of vertices that traverses every edge exactly once) if and only if
This is Euler's 1736 characterization, the result with which the book opens the theory of graph traversals.
Formalization Note. The book defines "eulerian" only for graphs without isolated vertices (p. 75), so that restriction is a hypothesis here; without it the equivalence fails, e.g. an edgeless graph on two vertices has an eulerian circuit in the sense of the definition (a one-vertex sequence covers its empty edge set) but is disconnected. Connectedness is Mathlib's SimpleGraph.Connected, which includes nonemptiness of .
import Mathlib import Definitions.Def_AppliedComb_Graphs_IsEulerian
namespace AppliedComb.Graphs
/-- Keller–Trotter, p. 77, Theorem 5.13 (Euler). For a finite graph `G` without isolated
vertices (the class on which the book defines "eulerian", p. 75), `G` is eulerian if and only
if it is connected and every vertex has even degree. -/
theorem eulerian_iff {V : Type*} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj]
(hG : ∀ v : V, ∃ w : V, G.Adj v w) :
IsEulerian G ↔ G.Connected ∧ ∀ v : V, Even (G.degree v) := by sorry
end AppliedComb.Graphs
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Setting. Let be a finite type of vertices, and let be a simple graph on with decidable adjacency. The theorem assumes that every vertex has at least one neighbour with . In other words, has no isolated vertices.
Conclusion. Under that assumption, the theorem states:
The two sides mean the following.
- Eulerian: there is a nonempty list of vertices, repetitions allowed, satisfying three conditions:
- ;
- for all ;
- for every edge of there is exactly one index with .
- Connected (Mathlib's sense): is nonempty, and any two vertices are joined by a walk.
- Degree: is the number of neighbours of .
Degenerate cases.
- empty: the no-isolated-vertices hypothesis holds vacuously.
- The left side is false, because no nonempty list of vertices exists.
- The right side is false, because connectedness requires nonempty.
- So the equivalence holds with both sides false.
- has one vertex: the hypothesis cannot be satisfied, since a simple graph has no loops. The theorem says nothing in this case.
- Every other allowed graph: it has at least one edge, and every vertex lies on an edge.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.