simple_graph_vertex_connectivity_two_card_three_eq_top
If 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 = 1, contradicting κ(G) ≥ 2. Hence G = ⊤.
Statement
theorem simple_graph_vertex_connectivity_two_card_three_eq_top {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (hcard : Fintype.card V = 3) (hκ : 2 ≤ ghz_graph_vertex_connectivity G) : G = ⊤
- Source
- step towards radius_independence_connectivity_hamiltonian_interpolation
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- ghz_graph_vertex_connectivity_le_card_sub_twoIf G is not the complete graph, there exist two distinct non-adjacent vertices u and v. Setting T = (V \ {u, v}) yields an induced…
- 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…
- 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 proof is by contradiction. If G were not the complete graph ⊤, then by ghz_graph_vertex_connectivity_le_card_sub_two its vertex connectivity would be at most |V| - 2 = 3 - 2 = 1. This contradicts the hypothesis that the vertex connectivity is at least 2, forcing G = ⊤.
Assuming G ≠ ⊤, the vertex connectivity κ(G) is at most |V| - 2
We argue by contradiction, assuming that G is not the complete graph (G ≠ ⊤). By `ghz_graph_vertex_connectivity_le_card_sub_two`, the vertex connectivity of any non-complete graph G is at most |V| - 2.
uses
ghz_graph_vertex_connectivity_le_card_sub_twoby_contra hne have h := ghz_graph_vertex_connectivity_le_card_sub_two G hne
Contradiction, establishing G = ⊤
Since |V| = 3, the bound from the previous step gives κ(G) ≤ 3 - 2 = 1. However, by assumption κ(G) ≥ 2. Linear integer arithmetic (`omega`) recognises that 2 ≤ κ(G) ≤ 1 is impossible and closes the goal.
omega
ghz_graph_vertex_connectivity_le_card_sub_two- For any simple graph G on a finite type V, if G is not the complete graph (G ≠ ⊤), its vertex connectivity is at most |V| - 2.
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.
/-- Any 2-connected simple graph on 3 vertices is the complete graph K_3. -/theorem simple_graph_vertex_connectivity_two_card_three_eq_top {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (hcard : Fintype.card V = 3) (hκ : 2 ≤ ghz_graph_vertex_connectivity G) : G = ⊤ := by by_contra hne have h := ghz_graph_vertex_connectivity_le_card_sub_two G hne omega