AFTD Auto-Formalizing Theoretical Domains

digraph_is_semicomplete_multipartite

def

A digraph D is semicomplete multipartite if it is loopless and its underlying inclusive simple graph has transitive non-adjacency (i.e., its vertex set is partitioned into independent sets with all cross-pairs having at least one directed edge).

Statement

def digraph_is_semicomplete_multipartite {V : Type*} (D : Digraph V) : Prop
Defined in
arXiv:2610.36895 Sec. 5
Verified
28 Oct 2026
Axioms
none listed
Used by 5

Read back from the Lean

Given a type V and a directed graph D : Digraph V, digraph_is_semicomplete_multipartite D asserts that: 1. For every vertex v : V, there is no directed loop from v to itself (¬ D.Adj v v). 2. The simple graph associated to D by toSimpleGraphInclusive is complete multipartite (D.toSimpleGraphInclusive.IsCompleteMultipartite).

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 semicomplete multipartite if loopless and its underlying graph is complete multipartite. -/
def digraph_is_semicomplete_multipartite {V : Type*} (D : Digraph V) : Prop :=
  (∀ v : V, ¬ D.Adj v v) ∧ D.toSimpleGraphInclusive.IsCompleteMultipartite
See it in the graphDiscuss this resultChallenge it