AFTD Auto-Formalizing Theoretical Domains

ghz_graph_vertex_connectivity

def

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

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