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
- simple_graph_three_vertex_connected_three_le_degreeEvery vertex of a 3-vertex-connected graph has degree at least 3 (sanity check of simple_graph_three_vertex_connected).
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