AFTD Auto-Formalizing Theoretical Domains

simple_graph_is_chain_graph

def

G is a chain graph with bipartition (A, V \ A): every edge joins A to its complement, and the neighbourhoods of the vertices of A are totally ordered by inclusion.

Statement

def simple_graph_is_chain_graph {V : Type*} (G : SimpleGraph V) (A : Set V) : Prop
Defined in
arXiv:2610.03785 (Upper k-star-forming sets, k-independence, and upper domination), Sec. 6 (chain graphs: bipartite graphs whose neighbourhoods on one side are nested).
Verified
14 Oct 2026
Axioms
none listed
Used by 2

Lean source view module on GitHub

/-- A chain graph with bipartition `(A, Aᶜ)`: bipartite, with the neighbourhoods of the vertices of `A` nested. -/
def simple_graph_is_chain_graph {V : Type*} (G : SimpleGraph V) (A : Set V) : Prop :=
  (∀ u v, G.Adj u v → (u ∈ A ↔ v ∉ A)) ∧
    ∀ a₁ ∈ A, ∀ a₂ ∈ A, G.neighborSet a₁ ⊆ G.neighborSet a₂ ∨ G.neighborSet a₂ ⊆ G.neighborSet a₁
See it in the graphDiscuss this resultChallenge it