AFTD Auto-Formalizing Theoretical Domains

simple_graph_is_k_connected

def

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