digraph_inversion_number_eq_zero_of_is_acyclic
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
- tournament_dijoin_inversion_number_symm_of_is_acyclic_leftThe symmetry inv(D₁ → D₂) = inv(D₂ → D₁) holds when D₁ is acyclic (a transitive tournament): both sides equal inv(D₂).
- tournament_dijoin_inversion_number_symm_of_is_acyclic_rightThe symmetry inv(D₁ → D₂) = inv(D₂ → D₁) holds when D₂ is acyclic: both sides equal inv(D₁).
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.
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.
uses
Nat.sInf_eq_zero.mprapply Nat.sInf_eq_zero.mpr left
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.
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
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_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⟩