AFTD Auto-Formalizing Theoretical Domains

digraph_is_co_bipartite

def

A digraph D is co-bipartite if it is loopless and its vertex set can be partitioned into two disjoint subsets each of which induces a semicomplete subdigraph.

Statement

def digraph_is_co_bipartite {V : Type*} (D : Digraph V) : Prop
Defined in
arXiv:2610.36895 Sec. 6
Verified
28 Oct 2026
Axioms
none listed
Built on 1
  • digraph_is_semicompleteA digraph D is semicomplete if it is loopless and for every pair of distinct vertices u and v, at least one directed edge exists between…
Used by 1

Read back from the Lean

For a vertex type V and a directed graph D on V, digraph_is_co_bipartite D asserts that: 1. D has no self-loops: for every vertex v : V, ¬ D.Adj v v. 2. There exists a partition of V into two disjoint subsets V₁ and V₂ (that is, every v : V is in V₁ or V₂, and Disjoint V₁ V₂) such that: - for any two distinct vertices u, v ∈ V₁, there is a directed edge between them in at least one direction (D.Adj u v ∨ D.Adj v u); and - for any two distinct vertices u, v ∈ V₂, there is a directed edge between them in at least one direction (D.Adj u v ∨ D.Adj v u).

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 digraph is co-bipartite if its vertex set can be partitioned into two induced semicomplete subdigraphs. -/
def digraph_is_co_bipartite {V : Type*} (D : Digraph V) : Prop :=
  (∀ v : V, ¬ D.Adj v v) ∧
  ∃ (V₁ V₂ : Set V), (∀ v, v ∈ V₁ ∨ v ∈ V₂) ∧ Disjoint V₁ V₂ ∧
    (∀ u ∈ V₁, ∀ v ∈ V₁, u ≠ v → D.Adj u v ∨ D.Adj v u) ∧
    (∀ u ∈ V₂, ∀ v ∈ V₂, u ≠ v → D.Adj u v ∨ D.Adj v u)
See it in the graphDiscuss this resultChallenge it