empty_graph_has_modulo_orientation
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
- simple_graph_has_modulo_orientationA simple graph G on a finite vertex set V has a modulo-q orientation if there exists an orientation directing each edge such that for…
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.
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.
unfold simple_graph_has_modulo_orientationThe 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`.
uses
isEmptyElimrefine ⟨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
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 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⟩