AFTD Auto-Formalizing Theoretical Domains

digraph_is_acyclic_of_rank

theoremverified

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

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.

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

    line 3

      intro x hx
  2. Along 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)$.

    lines 4–8

    uses Relation.TransGen, lt_trans

      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)
  3. 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.

    line 9

    uses lt_irrefl

      exact 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

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