AFTD Auto-Formalizing Theoretical Domains

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

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