AFTD Auto-Formalizing Theoretical Domains

simple_graph_top_is_hamiltonian

theoremverified

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

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.

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

    lines 4–5

    uses SimpleGraph.IsHamiltonian.mono, le_top

      refine SimpleGraph.IsHamiltonian.mono (G := SimpleGraph.cycleGraph (n + 3)) le_top ?_
      intro _
  2. 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.

    lines 6–8

    uses SimpleGraph.Walk.isHamiltonianCycle_iff_isCycle_and_length_eq, SimpleGraph.cycleGraph.isCycle_cycle

      refine ⟨0, SimpleGraph.cycleGraph.cycle n, ?_⟩
      rw [SimpleGraph.Walk.isHamiltonianCycle_iff_isCycle_and_length_eq]
      exact ⟨SimpleGraph.cycleGraph.isCycle_cycle, by simp⟩
  3. 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.

    lines 12–18

    uses finCongr, Fintype.equivFin, SimpleGraph.top_adj

      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)⟩
  4. 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).

    lines 19–21

    uses simple_graph_top_is_hamiltonian_fin, Fintype.card_fin

      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)
  5. 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.

    line 22

      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.

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

/-- 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⟩
See it in the graphDiscuss this resultChallenge it