digraph_is_acyclic_of_rank
A digraph with a numbering of the vertices that increases along every arc is acyclic.
Statement
theorem digraph_is_acyclic_of_rank {V : Type*} (D : Digraph V) (f : V → ℕ) (hf : ∀ x y, D.Adj x y → f x < f y) : digraph_is_acyclic D
- Source
- Sanity lemma for digraph_is_acyclic (arXiv:2610.13798).
- Verified
- 13 Oct 2026
- Axioms
- none — Lean reports it depends on no axioms
- 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…
- Used by 3
- tournament_exists_decycling_matrixEvery finite tournament has a symmetric decycling matrix over F₂ (so its minimum rank is attained).
- tournament_exists_decycling_familyEvery finite tournament can be made acyclic by finitely many inversions (so its inversion number is attained).
- tournament_min_rank_dijoin_le_of_symm_invLet B be an invertible symmetric n × n matrix over F₂, L the lower triangular all-ones matrix, and A = L B⁻¹ Lᵀ. Then the tournaments D₁ =…
The proof, explained
The proof proceeds by contradiction. Suppose the digraph has a cycle from some vertex $x$ to itself. By induction on the path length, the vertex ranking $f$ strictly increases along any directed path, which implies $f(x) < f(x)$ along the cycle. This contradicts the irreflexivity of strict inequality on the natural numbers.
Assume, for contradiction, that there exists a directed cycle from some vertex $x$ to itself.
By definition, a directed graph is acyclic if no vertex can reach itself via a non-empty path. We introduce a vertex $x$ and the hypothesis $hx$ that $x$ reaches itself in the transitive closure of the adjacency relation, leaving the goal of deriving a contradiction.
intro x hxAlong any directed path from $a$ to $b$, the vertex ranking strictly increases, so $f(a) < f(b)$.
We establish this key property by induction on the path (`hab`), which is an element of the transitive closure `Relation.TransGen`. In the base case of a single arc $a \to b$, the rank increases directly by the hypothesis $hf$. In the inductive step where an arc $b \to c$ is appended to a path from $a$ to $b$, the induction hypothesis gives $f(a) < f(b)$ and the edge gives $f(b) < f(c)$; by transitivity of strict inequality (`lt_trans`), we conclude $f(a) < f(c)$.
uses
Relation.TransGen,lt_transhave key : ∀ a b, Relation.TransGen D.Adj a b → f a < f b := by intro a b hab induction hab with | single h => exact hf _ _ h | tail _ h ih => exact lt_trans ih (hf _ _ h)
The cycle at $x$ implies $f(x) < f(x)$, which contradicts the irreflexivity of strict inequality.
Applying the key property to the cycle from $x$ to $x$ (`hx`) yields $f(x) < f(x)$. Strict inequality on natural numbers is irreflexive (`lt_irrefl`), completing the proof by contradiction.
uses
lt_irreflexact lt_irrefl _ (key x x hx)
Relation.TransGen- The transitive closure of a relation: `Relation.TransGen R a b` asserts that $b$ can be reached from $a$ by a chain of one or more $R$-steps.
lt_trans- Strict inequality is transitive: if $a < b$ and $b < c$, then $a < c$.
lt_irrefl- Strict inequality is irreflexive: $a < a$ never holds for any $a$.
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_is_acyclic_of_rank {V : Type*} (D : Digraph V) (f : V → ℕ) (hf : ∀ x y, D.Adj x y → f x < f y) : digraph_is_acyclic D := by intro x hx have key : ∀ a b, Relation.TransGen D.Adj a b → f a < f b := by intro a b hab induction hab with | single h => exact hf _ _ h | tail _ h ih => exact lt_trans ih (hf _ _ h) exact lt_irrefl _ (key x x hx)