AFTD Auto-Formalizing Theoretical Domains

digraph_bot_is_semicomplete_multipartite

theoremverified

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

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.

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

    line 4

      refine ⟨fun v => by simp, ?_⟩
  2. 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.

    lines 5–6

      unfold SimpleGraph.IsCompleteMultipartite
      refine ⟨fun a b c hab _ => ?_⟩
  3. 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.

    line 7

      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

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