digraph_is_co_bipartite
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
- digraph_semicomplete_is_co_bipartiteEvery semicomplete digraph is co-bipartite.
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)