AFTD Auto-Formalizing Theoretical Domains

simple_graph_has_separator_of_order_two

def

A finite graph has a proper vertex separation of order at most two when its vertices split between two proper sets with no edges between their exclusive parts.

Statement

def simple_graph_has_separator_of_order_two (V : Type) [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) : Prop
Source
Published separator reduction, https://www.cs.tau.ac.il/~krivelev/2.pdf, Lemma 5.
Verified
03 Nov 2026
Axioms
none listed
Used by 1

Lean source view module on GitHub

def simple_graph_has_separator_of_order_two (V : Type) [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) : Prop :=
  ∃ A B : Finset V, A ∪ B = Finset.univ ∧
    A.card < Fintype.card V ∧ B.card < Fintype.card V ∧ (A ∩ B).card ≤ 2 ∧
    ∀ x ∈ A \ B, ∀ y ∈ B \ A, ¬ G.Adj x y
See it in the graphDiscuss this resultChallenge it