AFTD Auto-Formalizing Theoretical Domains

simple_graph_three_vertex_connected

def

A simple graph on Fin n is 3-vertex-connected if it has at least 4 vertices and deleting any set of at most 2 vertices leaves a connected graph.

Statement

def simple_graph_three_vertex_connected {n : ℕ} (G : SimpleGraph (Fin n)) : Prop
Defined in
Standard k-connectivity (Diestel, Graph Theory, Sec. 1.4) with k = 3, as used in OP-541; arXiv:2610.25886 (Extremal arborescences in graph orientations)
Verified
27 Oct 2026
Axioms
none listed
Used by 1

Read back from the Lean

Given a natural number $n$ and a simple graph $G$ on the vertex type Fin n, simple_graph_three_vertex_connected G asserts that $4 \le n$, and for every finite subset $X$ of Fin n of cardinality at most $2$, the subgraph of $G$ induced on the complement of $X$ (i.e., all vertices not in $X$) is connected.

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

/-- G is 3-vertex-connected: at least 4 vertices, and connected after deleting any at most 2 vertices. -/
def simple_graph_three_vertex_connected {n : ℕ} (G : SimpleGraph (Fin n)) : Prop :=
  4 ≤ n ∧ ∀ X : Finset (Fin n), X.card ≤ 2 → (G.induce ((X : Set (Fin n))ᶜ)).Connected
See it in the graphDiscuss this resultChallenge it