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
- simple_graph_triangle_cover_reduces_to_separator_freeGiven the two-vertex separator induction step, the triangle packing-cover inequality for all separator-free finite graphs implies it for…
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