digraph_semicomplete_is_co_bipartite
Every semicomplete digraph is co-bipartite.
Statement
theorem digraph_semicomplete_is_co_bipartite {V : Type*} (D : Digraph V) (h : digraph_is_semicomplete D) : digraph_is_co_bipartite D
- Source
- arXiv:2610.36895 Sec. 6
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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…
- digraph_is_co_bipartiteA 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…
Read back from the Lean
Let V be a type and D be a directed graph on V. If D is semicomplete (meaning D has no self-loops and for every pair of distinct vertices u, v : V, there is an edge from u to v or from v to u), then D is co-bipartite (meaning D has no self-loops and the vertices of V can be partitioned into two disjoint sets V₁ and V₂ such that both V₁ and V₂ induce semicomplete subdigraphs: any two distinct vertices within V₁ have an edge between them in at least one direction, and likewise for any two distinct vertices within V₂).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
A digraph is co-bipartite if its vertices can be partitioned into two disjoint subsets, each inducing a loopless semicomplete subdigraph. Because the definition does not require the parts to be non-empty and the given digraph D is already semicomplete and loopless, we can choose the trivial partition where one part is the entire vertex set and the other is empty. The partition requirements then hold immediately: every vertex is in the full set, the two sets are disjoint, and the empty part satisfies the semicompleteness condition vacuously.
To show D is co-bipartite, it suffices to verify the partition conditions for V₁ = Set.univ and V₂ = ∅.
We decompose the semicompleteness assumption on D into looplessness (hloop) and the requirement that every pair of distinct vertices has an edge between them (hsemi). We instantiate the existential quantifier in the co-bipartiteness definition with the trivial partition V₁ = Set.univ (the entire vertex set) and V₂ = ∅, leaving four conditions to verify: covering, disjointness, and semicompleteness on each part.
uses
Set.univobtain ⟨hloop, hsemi⟩ := h refine ⟨hloop, Set.univ, ∅, ?_, ?_, ?_, ?_⟩
Every vertex belongs to the union of the two parts.
For any vertex v, the disjunction v ∈ Set.univ ∨ v ∈ ∅ holds via Or.inl because v is trivially an element of the universal set.
uses
Or.inl· intro v; exact Or.inl trivial
The two sets Set.univ and ∅ are disjoint. automation
The empty set is disjoint from any set, so Disjoint Set.univ ∅ is closed by standard set simplification.
· simpThe induced subdigraph on the first part is semicomplete.
For any two distinct vertices u, v in Set.univ, the semicompleteness hypothesis hsemi of D directly guarantees that there is an edge from u to v or from v to u.
· intro u _ v _ huv; exact hsemi u v huv
The condition on the second part holds vacuously. automation
Given any vertex u assumed to belong to ∅, simplification recognizes that membership in the empty set is false, closing the goal by contradiction.
· intro u hu; simp at hu
Set.univ- The universal set containing every term of a given type.
Or.inl- Constructs a disjunction a ∨ b from a proof of the left disjunct a.
- The definition of co-bipartite digraph in this formalisation does not require the two parts of the partition to be non-empty, which allows the trivial partition into the whole vertex set and the empty set.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Every semicomplete digraph is co-bipartite. -/theorem digraph_semicomplete_is_co_bipartite {V : Type*} (D : Digraph V) (h : digraph_is_semicomplete D) : digraph_is_co_bipartite D := by obtain ⟨hloop, hsemi⟩ := h refine ⟨hloop, Set.univ, ∅, ?_, ?_, ?_, ?_⟩ · intro v; exact Or.inl trivial · simp · intro u _ v _ huv; exact hsemi u v huv · intro u hu; simp at hu