AFTD Auto-Formalizing Theoretical Domains

simple_graph_vertex_connectivity_two_card_three_eq_top

theoremverified

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
Used by 1

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 = ⊤.

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

    lines 3–4

    uses ghz_graph_vertex_connectivity_le_card_sub_two

      by_contra hne
      have h := ghz_graph_vertex_connectivity_le_card_sub_two G hne
  2. 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.

    line 5

      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

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