AFTD Auto-Formalizing Theoretical Domains

empty_graph_has_modulo_orientation

theoremverified

For every natural number q, the empty simple graph on the empty type Empty has a modulo-q orientation.

Statement

theorem empty_graph_has_modulo_orientation (q : ℕ) : simple_graph_has_modulo_orientation (⊥ : SimpleGraph Empty) q
Source
folklore
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1

Read back from the Lean

For every natural number $q$, the empty graph on the empty vertex type Empty has a modulo-$q$ orientation: there exists a binary relation $R$ on Empty such that: 1. for all $u, v : \text{Empty}$, $R(u, v)$ implies $u$ and $v$ are adjacent in the bottom graph (which is never); 2. for all $u, v : \text{Empty}$, adjacency implies that exactly one of $R(u, v)$ or $R(v, u)$ holds; and 3. for every vertex $v : \text{Empty}$, the out-degree $|\{w : \text{Empty} \mid R(v, w)\}|$ modulo $q$ equals the in-degree $|\{w : \text{Empty} \mid R(w, v)\}|$ modulo $q$.

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

The theorem states that the empty graph on the empty vertex type has a modulo-q orientation for any modulus q. Unfolding the definition requires finding an edge orientation where each vertex has balanced in- and out-degrees modulo q. Choosing the empty relation trivially satisfies all conditions because the vertex set is empty, rendering all universal quantifications vacuously true.

  1. Reduce to finding a binary relation that orients the graph with balanced degrees modulo q

    Unfolding the definition of `simple_graph_has_modulo_orientation` shows that we must construct a binary relation R on `Empty` that orients each edge in exactly one direction such that at every vertex, the out-degree and in-degree are congruent modulo q.

    line 3

      unfold simple_graph_has_modulo_orientation
  2. The empty relation vacuously satisfies all orientation and degree-balance conditions

    We choose the empty relation (identically false for all pairs of vertices) as the witness. Because the vertex type `Empty` has no elements, the conditions—that R is a subgraph, that each edge has a unique direction, and that degrees balance at every vertex—are universal quantifications over an empty domain, all proved vacuously by `isEmptyElim`.

    line 4

    uses isEmptyElim

      refine ⟨fun _ _ => False, ⟨fun u => isEmptyElim u, fun u => isEmptyElim u⟩, fun v => isEmptyElim v⟩
isEmptyElim
from an element of an empty type, anything follows (principle of explosion / vacuous truth)

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 graph on the empty vertex type has a modulo-q orientation for every modulus q. -/theorem empty_graph_has_modulo_orientation (q : ℕ) : simple_graph_has_modulo_orientation (⊥ : SimpleGraph Empty) q := by  unfold simple_graph_has_modulo_orientation  refine ⟨fun _ _ => False, ⟨fun u => isEmptyElim u, fun u => isEmptyElim u⟩, fun v => isEmptyElim v⟩
See it in the graphDiscuss this resultChallenge it