AFTD Auto-Formalizing Theoretical Domains

simple_graph_has_two_vertex_cut

def

A graph G has a 2-vertex cut if there exist two distinct vertices u, v : V such that the subgraph of G induced on the complement of {u, v} is not preconnected.

Statement

def simple_graph_has_two_vertex_cut {V : Type*} (G : SimpleGraph V) : Prop
Defined in
arXiv:2611.16649 Sec. 1, p. 1
Verified
14 Nov 2026
Axioms
none listed

Read back from the Lean

Given a type V and a simple graph G on V, simple_graph_has_two_vertex_cut G asserts that there exist two distinct vertices u, v : V such that the subgraph induced on the complement of {u, v} is not preconnected.

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 simple graph has a 2-vertex cut if there exist two distinct vertices whose deletion leaves a non-preconnected induced subgraph. -/
def simple_graph_has_two_vertex_cut {V : Type*} (G : SimpleGraph V) : Prop := ∃ u v : V, u ≠ v ∧ ¬ (G.induce ({u, v}ᶜ)).Preconnected
See it in the graphDiscuss this resultChallenge it