digraph_is_semicomplete
def
A 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 them (u → v or v → u).
Statement
def digraph_is_semicomplete {V : Type*} (D : Digraph V) : Prop
- Defined in
- arXiv:2610.36895 Sec. 1
- Verified
- 28 Oct 2026
- Axioms
- none listed
- Used by 2
- digraph_semicomplete_is_co_bipartiteEvery semicomplete digraph is co-bipartite.
- 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
Given a type V and a directed graph D : Digraph V, digraph_is_semicomplete D is defined as the proposition that:
1. For every vertex v : V, there is no directed edge from v to itself (¬ D.Adj v v), and
2. For all vertices u, v : V, if u ≠ v, then there is a directed edge from u to v or from v to u (or both).
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 if it is loopless and has at least one arc between every distinct pair of vertices. -/ def digraph_is_semicomplete {V : Type*} (D : Digraph V) : Prop := (∀ v : V, ¬ D.Adj v v) ∧ ∀ u v : V, u ≠ v → D.Adj u v ∨ D.Adj v u