simple_graph_is_k_connected
A finite simple graph G is k-connected if its order is strictly greater than k and the deletion of any subset of strictly fewer than k vertices leaves a connected graph.
Statement
def simple_graph_is_k_connected {V : Type*} [Fintype V] (G : SimpleGraph V) (k : ℕ) : Prop
- Defined in
- arXiv:2611.07145 Sec. 1
- Verified
- 08 Nov 2026
- Axioms
- none listed
Read back from the Lean
Given a finite type V, a simple graph G on V, and a natural number k, simple_graph_is_k_connected G k is defined as the conjunction of two conditions:
1. k is strictly less than the cardinality of V (k < Fintype.card V), and
2. For every subset s : Finset V, if s.card < k, then the induced subgraph on the complement of s (G.induce (s : Set V)ᶜ) is connected (SimpleGraph.Connected, meaning it has at least one vertex and any two vertices in the complement of s are joined by a path within that induced subgraph).
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
/-- A finite simple graph G is k-connected if its order is strictly greater than k and deleting strictly fewer than k vertices leaves a connected graph. -/ def simple_graph_is_k_connected {V : Type*} [Fintype V] (G : SimpleGraph V) (k : ℕ) : Prop := k < Fintype.card V ∧ ∀ (s : Finset V), s.card < k → (G.induce (s : Set V)ᶜ).Connected