ghz_graph_vertex_connectivity
The vertex connectivity κ(G) of a finite simple graph G = (V, E) is |V| - 1 if G is the complete graph, and otherwise the minimum cardinality of a vertex set T ⊆ V such that the induced subgraph on V \ T is disconnected (not preconnected).
Statement
noncomputable def ghz_graph_vertex_connectivity {V : Type*} [Fintype V] (G : SimpleGraph V) : ℕ
- Defined in
- arXiv:2610.22190 Section 1.1
- Verified
- 20 Oct 2026
- Axioms
- none listed
- Used by 5
- ghz_vertex_connectivity_le_card_of_cutIf a finite vertex set T has G − T not preconnected, then the vertex connectivity κ(G) is at most |T|.
- 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_connectivity_two_le_imp_two_connectedA finite simple graph with vertex connectivity at least 2 is 2-connected: it is preconnected, and deleting any single vertex leaves it…
- 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…
- 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…
Read back from the Lean
For a finite type V and a simple graph G on V, ghz_graph_vertex_connectivity G is the natural number defined by cases:
- If G is the complete graph ⊤, it evaluates to Fintype.card V - 1 (using natural number subtraction, so 0 if |V| = 0).
- Otherwise, it evaluates to the infimum in ℕ (the minimum) of the set of natural numbers n such that there exists a finset T : Finset V with n = T.card and such that the induced subgraph of G on the complement Tᶜ (V \ T) is not preconnected (i.e., there exist two vertices in V \ T between which there is no walk entirely within V \ T).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The vertex connectivity κ(G) of a simple graph: the minimum size of a vertex set whose deletion disconnects G, or |V| - 1 for complete graphs. -/ noncomputable def ghz_graph_vertex_connectivity {V : Type*} [Fintype V] (G : SimpleGraph V) : ℕ := open scoped Classical in if G = ⊤ then Fintype.card V - 1 else sInf { n : ℕ | ∃ T : Finset V, ¬ (G.induce (Tᶜ : Set V)).Preconnected ∧ n = T.card }