Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 5.13 — Euler: a graph is eulerian iff it is connected and all degrees are even

Proved
AppliedComb.Graphs.eulerian_iff

by mikedeng1 · Sep 28, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatoricseuleriangraph-theoryp2o-batch-books5p2o-gran-per-chapterp2o-plan-bookp2o-v1

Let G=(V,E)G = (V, E)G=(V,E) be a finite graph without isolated vertices (every vertex has at least one neighbour). Then GGG is eulerian (it has a closed sequence of vertices that traverses every edge exactly once) if and only if

G is connectedanddeg⁡G(v) is even for every v∈V.G \text{ is connected} \quad\text{and}\quad \deg_G(v) \text{ is even for every } v \in V.G is connectedanddegG​(v) is even for every v∈V.

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 VVV.

Preamble
import Mathlib
import Definitions.Def_AppliedComb_Graphs_IsEulerian
Formal statement
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
Source
Keller & Trotter, Applied Combinatorics (2017 Edition), p. 77, Theorem 5.13 (definition of eulerian on p. 75)
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Setting. Let VVV be a finite type of vertices, and let GGG be a simple graph on VVV with decidable adjacency. The theorem assumes that every vertex vvv has at least one neighbour www with v∼Gwv \sim_G wv∼G​w. In other words, GGG has no isolated vertices.

Conclusion. Under that assumption, the theorem states:

G is eulerian  ⟺  (G is connected) ∧ (∀v∈V, deg⁡G(v) is even).G \text{ is eulerian} \iff \bigl(G \text{ is connected}\bigr) \ \wedge\ \bigl(\forall v \in V,\ \deg_G(v) \text{ is even}\bigr).G is eulerian⟺(G is connected) ∧ (∀v∈V, degG​(v) is even).

The two sides mean the following.

  • Eulerian: there is a nonempty list (x0,…,xt)(x_0, \dots, x_t)(x0​,…,xt​) of vertices, repetitions allowed, satisfying three conditions:
    • x0=xtx_0 = x_tx0​=xt​;
    • xi∼Gxi+1x_i \sim_G x_{i+1}xi​∼G​xi+1​ for all 0≤i<t0 \le i < t0≤i<t;
    • for every edge eee of GGG there is exactly one index i<ti < ti<t with e={xi,xi+1}e = \{x_i, x_{i+1}\}e={xi​,xi+1​}.
  • Connected (Mathlib's sense): VVV is nonempty, and any two vertices are joined by a walk.
  • Degree: deg⁡G(v)\deg_G(v)degG​(v) is the number of neighbours of vvv.

Degenerate cases.

  • VVV 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 VVV nonempty.
    • So the equivalence holds with both sides false.
  • VVV 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.
Human review
  • Endorsed by Shuze Chen · Oct 2, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 2, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me