AFTD Auto-Formalizing Theoretical Domains

digraph_semicomplete_is_co_bipartite

theoremverified

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.

  1. 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.

    lines 4–5

    uses Set.univ

      obtain ⟨hloop, hsemi⟩ := h
      refine ⟨hloop, Set.univ, ∅, ?_, ?_, ?_, ?_⟩
  2. 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.

    line 6

    uses Or.inl

      · intro v; exact Or.inl trivial
  3. 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.

    line 7

      · simp
  4. The 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.

    line 8

      · intro u _ v _ huv; exact hsemi u v huv
  5. 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.

    line 9

      · 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.

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

/-- 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
See it in the graphDiscuss this resultChallenge it