simple_graph_vertex_connectivity_two_card_three_hamiltonian
For card V = 3 and κ(G) ≥ 2, simple_graph_vertex_connectivity_two_card_three_eq_top forces G = ⊤. Then simple_graph_top_is_hamiltonian yields G.IsHamiltonian.
Statement
theorem simple_graph_vertex_connectivity_two_card_three_hamiltonian {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (hcard : Fintype.card V = 3) (hκ : 2 ≤ ghz_graph_vertex_connectivity G) : G.IsHamiltonian
- Source
- step towards radius_independence_connectivity_hamiltonian_interpolation
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- simple_graph_vertex_connectivity_two_card_three_eq_topIf a graph G on 3 vertices had G ≠ ⊤, then by ghz_graph_vertex_connectivity_le_card_sub_two its vertex connectivity would be at most 3 - 2…
- simple_graph_top_is_hamiltonianThe complete graph on at least three vertices contains a Hamilton cycle.
- ghz_graph_vertex_connectivityThe vertex connectivity κ(G) of a finite simple graph G = (V, E) is |V| - 1 if G is the complete graph, and otherwise the minimum…
The proof, explained
The proof shows that any 2-connected simple graph on 3 vertices is Hamiltonian by reducing it to the complete graph. Because the graph has 3 vertices and vertex connectivity at least 2, it must be the complete graph ⊤. Complete graphs on at least 3 vertices are known to be Hamiltonian, so the result follows immediately.
G = ⊤
By simple_graph_vertex_connectivity_two_card_three_eq_top, any simple graph on 3 vertices with vertex connectivity at least 2 must be the complete graph ⊤.
uses
simple_graph_vertex_connectivity_two_card_three_eq_tophave h : G = ⊤ := simple_graph_vertex_connectivity_two_card_three_eq_top G hcard hκG is Hamiltonian
Substituting ⊤ for G, it remains to show that the complete graph on V is Hamiltonian. By simple_graph_top_is_hamiltonian, the complete graph on any finite vertex set with at least 3 vertices has a Hamiltonian cycle, and the requirement 3 ≤ |V| follows immediately from |V| = 3 by linear arithmetic (omega).
uses
simple_graph_top_is_hamiltonianrw [h] exact simple_graph_top_is_hamiltonian (by omega : 3 ≤ Fintype.card V)
simple_graph_vertex_connectivity_two_card_three_eq_top- A simple graph on 3 vertices with vertex connectivity at least 2 is the complete graph (⊤).
simple_graph_top_is_hamiltonian- The complete graph on a finite vertex set with at least 3 vertices is Hamiltonian.
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.
/-- Every 2-connected simple graph on 3 vertices contains a Hamilton cycle. -/theorem simple_graph_vertex_connectivity_two_card_three_hamiltonian {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (hcard : Fintype.card V = 3) (hκ : 2 ≤ ghz_graph_vertex_connectivity G) : G.IsHamiltonian := by have h : G = ⊤ := simple_graph_vertex_connectivity_two_card_three_eq_top G hcard hκ rw [h] exact simple_graph_top_is_hamiltonian (by omega : 3 ≤ Fintype.card V)