digraph_bot_is_semicomplete_multipartite
The empty digraph on any vertex type is semicomplete multipartite.
Statement
theorem digraph_bot_is_semicomplete_multipartite {V : Type*} : digraph_is_semicomplete_multipartite (⊥ : Digraph V)
- Source
- folklore
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- digraph_is_semicomplete_multipartiteA digraph D is semicomplete multipartite if it is loopless and its underlying inclusive simple graph has transitive non-adjacency (i.e.,…
Read back from the Lean
For any type V, the bottom (empty) directed graph ⊥ : Digraph V is semicomplete multipartite (satisfies digraph_is_semicomplete_multipartite).
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 semicomplete multipartite if it has no self-loops and non-adjacency in its underlying simple graph is an equivalence relation (specifically, transitive). For the empty digraph, both conditions are trivial: it has no edges whatsoever, so it has no loops, and non-adjacency holds between every pair of vertices, making transitivity hold vacuously.
The empty digraph has no self-loops, leaving only the complete multipartite condition to be verified.
By definition, a digraph is semicomplete multipartite if it is loopless (no vertex has an edge to itself) and its underlying simple graph is complete multipartite. For any vertex v, the empty digraph ⊥ has no edges at all, so ¬ ⊥.Adj v v holds trivially, which simp proves.
refine ⟨fun v => by simp, ?_⟩
To show that the underlying graph is complete multipartite, it suffices to show that non-adjacency is transitive.
Unfolding SimpleGraph.IsCompleteMultipartite expresses the condition as transitivity of the non-adjacency relation (IsTrans). We introduce vertices a, b, c and assume that a is not adjacent to b (hab) and b is not adjacent to c.
unfold SimpleGraph.IsCompleteMultipartite refine ⟨fun a b c hab _ => ?_⟩
Vertices a and c are not adjacent, completing the transitivity check.
Because the underlying graph of the empty digraph has no edges between any vertices, the statement that a and c are not adjacent is trivially true; simpa simplifies this and closes the goal.
simpa using hab
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.
/-- The empty digraph is semicomplete multipartite. -/theorem digraph_bot_is_semicomplete_multipartite {V : Type*} : digraph_is_semicomplete_multipartite (⊥ : Digraph V) := by refine ⟨fun v => by simp, ?_⟩ unfold SimpleGraph.IsCompleteMultipartite refine ⟨fun a b c hab _ => ?_⟩ simpa using hab