AFTD Auto-Formalizing Theoretical Domains

digraph_inversion_number_eq_zero_of_is_acyclic

theoremverified

An acyclic digraph has inversion number 0.

Statement

theorem digraph_inversion_number_eq_zero_of_is_acyclic {V : Type*} (D : Digraph V)
    (h : digraph_is_acyclic D) : digraph_inversion_number D = 0
Source
Sanity lemma for digraph_inversion_number (arXiv:2610.13798, Sec. 1).
Verified
13 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • digraph_inversion_numberThe inversion number inv(D): the least number p of vertex sets X₁, …, X_p whose successive inversions turn D into an acyclic digraph (0 by…
  • 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…
  • digraph_invertThe inversion of a vertex set X in a digraph D: the digraph obtained by reversing every arc with both endpoints in X and keeping every…
Used by 2

The proof, explained

The inversion number of a directed graph is defined as the infimum of the lengths of sequences of subset inversions that make the graph acyclic. Since D is already acyclic, the empty sequence of inversions has length 0 and leaves D acyclic. Thus 0 belongs to the set of lengths, so the infimum is 0.

  1. To show that the inversion number is 0, it suffices to show that 0 belongs to the set of lengths of inversion sequences yielding an acyclic digraph.

    The inversion number is defined as the infimum (in ℕ) of the lengths of lists of vertex subsets whose successive inversions make the graph acyclic. By Nat.sInf_eq_zero.mpr, this infimum is 0 if 0 belongs to the set (or if the set is empty); we focus on showing that 0 is in the set.

    lines 3–4

    uses Nat.sInf_eq_zero.mpr

      apply Nat.sInf_eq_zero.mpr
      left
  2. 0 belongs to the set of achievable inversion sequence lengths.

    The empty list of inversions has length 0, and folding no inversions over D leaves D unchanged, which is acyclic by the hypothesis h.

    line 5

      exact ⟨[], rfl, h⟩
Nat.sInf_eq_zero.mpr
A set of natural numbers has infimum 0 if 0 is an element of the set or if the set is empty.

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_inversion_number_eq_zero_of_is_acyclic {V : Type*} (D : Digraph V)    (h : digraph_is_acyclic D) : digraph_inversion_number D = 0 := by  apply Nat.sInf_eq_zero.mpr  left  exact ⟨[], rfl, h⟩
See it in the graphDiscuss this resultChallenge it