simple_graph_top_is_hamiltonian
The complete graph on at least three vertices contains a Hamilton cycle.
Statement
theorem simple_graph_top_is_hamiltonian {V : Type*} [Fintype V] [DecidableEq V] (hV : 3 ≤ Fintype.card V) : (⊤ : SimpleGraph V).IsHamiltonian
- Source
- step towards radius_independence_connectivity_hamiltonian_interpolation
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- simple_graph_vertex_connectivity_two_card_three_hamiltonianFor card V = 3 and κ(G) ≥ 2, simple_graph_vertex_connectivity_two_card_three_eq_top forces G = ⊤. Then simple_graph_top_is_hamiltonian…
The proof, explained
The complete graph on at least three vertices is shown to be Hamiltonian by transferring a Hamiltonian cycle from the standard finite set Fin (n + 3). First, an auxiliary lemma shows that the complete graph on Fin (n + 3) is Hamiltonian by reducing to its subgraph, the standard cycle graph C_{n+3}, which contains an explicit canonical Hamiltonian cycle of length n + 3. For an arbitrary finite type V with |V| ≥ 3, setting m = |V| - 3 yields a bijection φ : Fin (m + 3) ≃ V, which lifts to an isomorphism between their complete graphs. Transporting the Hamiltonian cycle from Fin (m + 3) across this isomorphism produces a Hamiltonian cycle in the complete graph on V.
To show that the complete graph on Fin (n + 3) is Hamiltonian, it suffices to show that its subgraph, the cycle graph on n + 3 vertices, has a Hamiltonian cycle.
By monotonicity of Hamiltonicity (`SimpleGraph.IsHamiltonian.mono`), any supergraph of a Hamiltonian graph is Hamiltonian. Since the cycle graph on n + 3 vertices is a subgraph of the complete graph on the same vertices (`le_top`), Hamiltonicity reduces to that of the cycle graph. Unfolding the definition of Hamiltonicity introduces the assumption that the vertex count is not 1, leaving the existence of a Hamiltonian cycle to be proven.
uses
SimpleGraph.IsHamiltonian.mono,le_toprefine SimpleGraph.IsHamiltonian.mono (G := SimpleGraph.cycleGraph (n + 3)) le_top ?_ intro _
The canonical cycle in the cycle graph on Fin (n + 3) is a Hamiltonian cycle, completing the proof that the complete graph on Fin (n + 3) is Hamiltonian.
We exhibit the starting vertex 0 and the canonical closed walk `SimpleGraph.cycleGraph.cycle n`. By `SimpleGraph.Walk.isHamiltonianCycle_iff_isCycle_and_length_eq`, this walk is a Hamiltonian cycle if and only if it is a cycle and its length equals |Fin (n + 3)|. The first condition holds by `SimpleGraph.cycleGraph.isCycle_cycle`, and the second holds because both the walk's length and the cardinality of Fin (n + 3) equal n + 3, verified by simplification.
uses
SimpleGraph.Walk.isHamiltonianCycle_iff_isCycle_and_length_eq,SimpleGraph.cycleGraph.isCycle_cyclerefine ⟨0, SimpleGraph.cycleGraph.cycle n, ?_⟩ rw [SimpleGraph.Walk.isHamiltonianCycle_iff_isCycle_and_length_eq] exact ⟨SimpleGraph.cycleGraph.isCycle_cycle, by simp⟩
The vertex set V can be identified with Fin (m + 3) for m = |V| - 3, yielding an isomorphism between their complete graphs.
Since |V| ≥ 3, linear arithmetic (`omega`) lets us write |V| = m + 3 with m = |V| - 3. Combining `finCongr` with `Fintype.equivFin V` yields an equivalence φ : Fin (m + 3) ≃ V. We lift φ to a graph homomorphism f : ⊤ →g ⊤ between the respective complete graphs: adjacency in complete graphs is inequality of vertices (`SimpleGraph.top_adj`), which is preserved by φ since φ is injective.
uses
finCongr,Fintype.equivFin,SimpleGraph.top_adjobtain ⟨m, hm⟩ : ∃ m, Fintype.card V = m + 3 := ⟨Fintype.card V - 3, by omega⟩ let φ : Fin (m + 3) ≃ V := (finCongr hm.symm).trans (Fintype.equivFin V).symm let f : (⊤ : SimpleGraph (Fin (m + 3))) →g (⊤ : SimpleGraph V) := ⟨φ, by intro a b hab rw [SimpleGraph.top_adj] at hab ⊢ exact fun h => hab (φ.injective h)⟩
There exists a vertex a₀ and a Hamiltonian cycle p in the complete graph on Fin (m + 3).
Unfolding the definition of Hamiltonicity for the complete graph on V introduces the assumption |V| ≠ 1. Applying the auxiliary lemma `simple_graph_top_is_hamiltonian_fin m` requires showing |Fin (m + 3)| ≠ 1; this follows from `Fintype.card_fin` and linear arithmetic (`omega`) since m + 3 ≥ 3. This produces a vertex a₀ and a Hamiltonian cycle p in ⊤ on Fin (m + 3).
uses
simple_graph_top_is_hamiltonian_fin,Fintype.card_finintro _ obtain ⟨a₀, p, hp⟩ := simple_graph_top_is_hamiltonian_fin m (by have : Fintype.card (Fin (m + 3)) = m + 3 := Fintype.card_fin _; omega)
Pushing the Hamiltonian cycle forward along the isomorphism f yields a Hamiltonian cycle in the complete graph on V, concluding the theorem.
We provide the start vertex φ(a₀) and the walk p.map f. Because φ is a bijection, mapping a Hamiltonian cycle under the graph embedding f preserves the property of being a Hamiltonian cycle (`hp.map φ.bijective`), so p.map f is a Hamiltonian cycle in the complete graph on V.
exact ⟨φ a₀, p.map f, hp.map φ.bijective⟩
SimpleGraph.IsHamiltonian.mono- If a subgraph G ≤ H is Hamiltonian, then the supergraph H is also Hamiltonian.
le_top- In any complete lattice or bounded order, every element is less than or equal to the top element ⊤ (here, every graph on a given vertex set is a subgraph of the complete graph).
SimpleGraph.Walk.isHamiltonianCycle_iff_isCycle_and_length_eq- A walk starting and ending at a vertex is a Hamiltonian cycle if and only if it is a cycle and its length equals the cardinality of the vertex set.
SimpleGraph.cycleGraph.isCycle_cycle- The canonical walk traversing the cycle graph on n + 3 vertices is a cycle.
finCongr- An equality n = m between natural numbers induces an equivalence (bijection) between Fin n and Fin m.
Fintype.equivFin- Every finite type α is equivalent to Fin |α|.
SimpleGraph.top_adj- In a complete graph, two vertices are adjacent if and only if they are distinct.
simple_graph_top_is_hamiltonian_fin- The complete graph on Fin (n + 3) is Hamiltonian (the helper lemma established on lines 2–8).
Fintype.card_fin- The cardinality of the standard finite set Fin n is n.
- In Mathlib, a graph G on a finite type α is defined to be Hamiltonian (`IsHamiltonian`) if `Fintype.card α ≠ 1 → ∃ a p, p.IsHamiltonianCycle`, which requires discharging the condition `Fintype.card α ≠ 1` even though |α| ≥ 3.
- The arithmetic showing that |V| = (|V| - 3) + 3 and that m + 3 ≠ 1 is dispatched automatically by `omega`.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- The complete graph on `Fin (n + 3)` is Hamiltonian, using the Eulerian cycle of `cycleGraph`. -/private theorem simple_graph_top_is_hamiltonian_fin (n : ℕ) : (⊤ : SimpleGraph (Fin (n + 3))).IsHamiltonian := by refine SimpleGraph.IsHamiltonian.mono (G := SimpleGraph.cycleGraph (n + 3)) le_top ?_ intro _ refine ⟨0, SimpleGraph.cycleGraph.cycle n, ?_⟩ rw [SimpleGraph.Walk.isHamiltonianCycle_iff_isCycle_and_length_eq] exact ⟨SimpleGraph.cycleGraph.isCycle_cycle, by simp⟩/-- The complete graph on at least three vertices is Hamiltonian. -/theorem simple_graph_top_is_hamiltonian {V : Type*} [Fintype V] [DecidableEq V] (hV : 3 ≤ Fintype.card V) : (⊤ : SimpleGraph V).IsHamiltonian := by obtain ⟨m, hm⟩ : ∃ m, Fintype.card V = m + 3 := ⟨Fintype.card V - 3, by omega⟩ let φ : Fin (m + 3) ≃ V := (finCongr hm.symm).trans (Fintype.equivFin V).symm let f : (⊤ : SimpleGraph (Fin (m + 3))) →g (⊤ : SimpleGraph V) := ⟨φ, by intro a b hab rw [SimpleGraph.top_adj] at hab ⊢ exact fun h => hab (φ.injective h)⟩ intro _ obtain ⟨a₀, p, hp⟩ := simple_graph_top_is_hamiltonian_fin m (by have : Fintype.card (Fin (m + 3)) = m + 3 := Fintype.card_fin _; omega) exact ⟨φ a₀, p.map f, hp.map φ.bijective⟩