digraph_directed_triangle_not_acyclic
The directed triangle 0 → 1 → 2 → 0 is not acyclic.
Statement
theorem digraph_directed_triangle_not_acyclic : ¬ digraph_is_acyclic (⟨fun x y : ZMod 3 => y = x + 1⟩ : Digraph (ZMod 3))
- Source
- Sanity lemma for digraph_is_acyclic (arXiv:2610.13798).
- Verified
- 13 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- digraph_is_acyclicA digraph is acyclic when it has no directed cycle: no vertex reaches itself by a nonempty directed walk. For a tournament this means it…
The proof, explained
The proof proceeds by contradiction: assuming the directed graph on ZMod 3 with edges y = x + 1 is acyclic, no vertex can have a non-empty path to itself. Applying this to vertex 0, it suffices to construct a cycle from 0 to 0. The cycle is explicitly given by the three consecutive edges 0 → 1, 1 → 2, and 2 → 0 in ZMod 3.
To reach a contradiction, it suffices to find a directed walk from 0 to 0.
Assume for contradiction that the graph is acyclic (intro h). By definition, acyclicity means that no vertex admits a non-empty directed walk back to itself. Instantiating this at vertex 0 (apply h 0), producing a walk from 0 to 0 yields False.
intro h apply h 0
There is a directed walk from 0 to 0 in the directed triangle graph.
In ZMod 3 with edges defined by y = x + 1, we build the walk 0 → 1 → 2 → 0 step by step: Relation.TransGen.single rfl establishes the edge 0 → 1, the inner Relation.TransGen.tail extends it with 1 → 2, and the outer Relation.TransGen.tail extends it with 2 → 0 back to 0. Each individual edge holds by reflexivity (rfl).
uses
Relation.TransGen.tail,Relation.TransGen.singleexact Relation.TransGen.tail (Relation.TransGen.tail (Relation.TransGen.single rfl) rfl) rfl
Relation.TransGen.single- A single relation step r a b implies the transitive closure Relation.TransGen r a b.
Relation.TransGen.tail- A path in the transitive closure from a to b extended by a single step r b c yields a path from a to c in the transitive closure.
- The additions 0 + 1 = 1, 1 + 1 = 2, and 2 + 1 = 0 in ZMod 3 hold definitionally, allowing Lean to establish each edge step purely by reflexivity (rfl).
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.
theorem digraph_directed_triangle_not_acyclic : ¬ digraph_is_acyclic (⟨fun x y : ZMod 3 => y = x + 1⟩ : Digraph (ZMod 3)) := by intro h apply h 0 exact Relation.TransGen.tail (Relation.TransGen.tail (Relation.TransGen.single rfl) rfl) rfl