tournament_exists_decycling_family
Every finite tournament can be made acyclic by finitely many inversions (so its inversion number is attained).
Statement
theorem tournament_exists_decycling_family (V : Type) [Fintype V] (D : Digraph V) (h : digraph_is_tournament D) : ∃ Xs : List (Set V), digraph_is_acyclic (Xs.foldl digraph_invert D)
- Source
- Helper for the bounds on inversion numbers of dijoins in arXiv:2610.13798 (the inversion number of a finite tournament is well defined). Hint: fix a numbering e of V; invert the two-element set {x, y} for each arc y → x with e x < e y; each such inversion reverses exactly that arc, and the result is ordered by e (digraph_is_acyclic_of_rank).
- Verified
- 13 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- 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…
- 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_is_tournamentA digraph is a tournament when it has no loops and between any two distinct vertices there is exactly one arc.
- digraph_is_acyclic_of_rankA digraph with a numbering of the vertices that increases along every arc is acyclic.
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - digraph_invert_is_tournamentInverting a vertex set of a tournament gives a tournament.
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- Used by 4
- tournament_dijoin_inversion_number_le_addFor finite tournaments D₁, D₂: inv(D₁ → D₂) ≤ inv(D₁) + inv(D₂), by inverting an optimal family of D₁ and then one of D₂.
- tournament_dijoin_inversion_number_le_symm_add_twoFor finite tournaments D₁, D₂: inv(D₁ → D₂) ≤ inv(D₂ → D₁) + 2 (with D₁, D₂ swapped this gives |inv(D₁ → D₂) − inv(D₂ → D₁)| ≤ 2): invert…
- tournament_inversion_number_le_dijoinFor finite tournaments D₁, D₂: inv(D₁ → D₂) ≥ max(inv(D₁), inv(D₂)), since D₁ and D₂ are induced subtournaments of the dijoin and a…
- tournament_exists_family_length_eq_inversion_numberFor a finite tournament D, the inversion number is attained: some decycling family of D has exactly inv(D) sets.
The proof, explained
The proof proceeds by induction on the number of backward edges (inversions) relative to a fixed arbitrary numbering of the vertices. When there are no backward edges, the tournament is already acyclic because the vertex numbering serves as a topological sort. When backward edges exist, inverting a two-element subset corresponding to any backward edge reverses that single edge into a forward edge while preserving all other adjacencies. This strictly reduces the count of backward edges by one and preserves the tournament property, allowing the induction hypothesis to complete the decycling process.
It suffices to prove by induction on n that any tournament with n backward edges relative to a fixed vertex ordering can be made acyclic by a sequence of subset inversions.
Fix an arbitrary bijection e : V ≃ Fin (|V|) via Fintype.equivFin to order the vertices. For any digraph D, define S(D) to be the set of backward edges: pairs (u, v) with e(u) < e(v) where the edge in D is directed backwards from v to u. We set up an induction on the number of backward edges n = |S(D)| for all tournaments on V.
uses
Fintype.equivFinclassical let e : V ≃ Fin (Fintype.card V) := Fintype.equivFin V let S : Digraph V → Finset (V × V) := fun D => Finset.univ.filter (fun p => e p.1 < e p.2 ∧ D.Adj p.2 p.1) suffices H : ∀ n, ∀ D : Digraph V, digraph_is_tournament D → (S D).card = n → ∃ Xs : List (Set V), digraph_is_acyclic (Xs.foldl digraph_invert D) from H _ D h rfl
In the base case n = 0, D has no backward edges and is already acyclic.
When |S(D)| = 0, the set of backward edges S(D) is empty by Finset.card_eq_zero. We show the empty sequence of inversions leaves D acyclic. By digraph_is_acyclic_of_rank, it suffices to check that the index function v ↦ e(v) strictly increases along every directed edge x → y in D. By lt_trichotomy on e(x) and e(y): if e(x) < e(y), the rank increases; if e(x) = e(y), injectivity of e implies x = y, contradicting the tournament property that no vertex has a self-loop; and if e(y) < e(x), then (y, x) ∈ S(D), contradicting S(D) = ∅.
uses
Finset.card_eq_zero,digraph_is_acyclic_of_rank,lt_trichotomy,Finset.mem_filter,Finset.mem_univ,true_andintro n induction n with | zero => intro D hD hS refine ⟨[], ?_⟩ apply digraph_is_acyclic_of_rank _ (fun v => (e v : ℕ)) intro x y hxy rw [Finset.card_eq_zero] at hS rcases lt_trichotomy (e x) (e y) with hlt | heq | hgt · exact hlt · exfalso have hxy' : x = y := e.injective heq subst hxy' exact hD.1 x hxy · exfalso have hmem : (y, x) ∈ S D := by simp only [S, Finset.mem_filter, Finset.mem_univ, true_and] exact ⟨hgt, hxy⟩ rw [hS] at hmem simp at hmem
When |S(D)| = n + 1, there exists a backward edge (a, b) ∈ S(D) with e(a) < e(b), directed edge b → a, distinct endpoints a ≠ b, and no edge a → b.
Since |S(D)| = n + 1 > 0, Finset.card_pos.mp shows S(D) is nonempty. Choosing any pair (a, b) ∈ S(D) gives e(a) < e(b) and a directed edge b → a. Strict order irreflexivity (lt_irrefl) ensures a ≠ b. Because D is a tournament, the presence of b → a guarantees that a → b is not an edge.
uses
Finset.card_pos.mp,Finset.mem_filter,Finset.mem_univ,true_and,lt_irrefl| succ n ih => intro D hD hS obtain ⟨⟨a, b⟩, hab⟩ : (S D).Nonempty := Finset.card_pos.mp (by omega) have hab' := hab simp only [S, Finset.mem_filter, Finset.mem_univ, true_and] at hab' obtain ⟨hlt, hba⟩ := hab' have hne : a ≠ b := fun h' => by rw [h'] at hlt; exact lt_irrefl _ hlt have hnab : ¬ D.Adj a b := fun h' => (hD.2 a b hne).1 h' hbaInverting the two-vertex subset {a, b} removes (a, b) from the set of backward edges and leaves all other backward edges unchanged: S(digraph_invert D {a, b}) = S(D) \ {(a, b)}.
Inverting along {a, b} only flips the adjacency between pairs whose endpoints both lie in {a, b}, namely the pair {a, b} itself. For any pair of vertices (u, v): if both lie in {a, b}, the only ordered pair with e(u) < e(v) is (a, b); after inversion, the edge points from a to b, so (a, b) is no longer a backward edge. If at least one endpoint is outside {a, b}, the edge orientation between u and v is unchanged, so (u, v) is a backward edge in the inverted graph if and only if it was one in D. Hence the backward set of the inverted tournament is precisely S(D) with (a, b) erased.
uses
Finset.mem_erase,Finset.mem_filter,Finset.mem_univ,true_and,Set.mem_insert_iff,Set.mem_singleton_iff,Prod.mk.injEq,lt_irrefl,not_lt.mprhave hS' : S (digraph_invert D {a, b}) = (S D).erase (a, b) := by ext ⟨u, v⟩ simp only [S, Finset.mem_erase, Finset.mem_filter, Finset.mem_univ, true_and, digraph_invert, Set.mem_insert_iff, Set.mem_singleton_iff, ne_eq, Prod.mk.injEq] by_cases hin : (v = a ∨ v = b) ∧ (u = a ∨ u = b) · have hcase : ¬ (e u < e v) ∨ (u = a ∧ v = b) := by obtain ⟨hv | hv, hu | hu⟩ := hin <;> subst hv <;> subst hu · exact Or.inl (lt_irrefl _) · exact Or.inl (not_lt.mpr hlt.le) · exact Or.inr ⟨rfl, rfl⟩ · exact Or.inl (lt_irrefl _) rcases hcase with hc | ⟨rfl, rfl⟩ · constructor · rintro ⟨h1, _⟩; exact absurd h1 hc · rintro ⟨_, h1, _⟩; exact absurd h1 hc · constructor · rintro ⟨_, ⟨_, _, h1⟩ | ⟨h1, _⟩⟩ · exact absurd h1 hnab · exact absurd ⟨Or.inr rfl, Or.inl rfl⟩ h1 · rintro ⟨h1, _⟩; exact absurd ⟨rfl, rfl⟩ h1 · have hnot : ¬ (u = a ∧ v = b) := fun ⟨h1, h2⟩ => hin ⟨Or.inr h2, Or.inl h1⟩ constructor · rintro ⟨h1, ⟨h2, h3, _⟩ | ⟨_, h2⟩⟩ · exact absurd ⟨h2, h3⟩ hin · exact ⟨hnot, h1, h2⟩ · rintro ⟨_, h1, h2⟩ exact ⟨h1, Or.inr ⟨hin, h2⟩⟩
The inverted tournament has n backward edges and can be decycled by the induction hypothesis; prepending {a, b} yields a decycling sequence for D.
Erasing (a, b) ∈ S(D) decreases the cardinality by 1, so the inverted tournament has exactly n backward edges by Finset.card_erase_of_mem. By digraph_invert_is_tournament, the inverted graph is still a tournament. The induction hypothesis then provides a list of vertex sets Xs that makes it acyclic. Prepending {a, b} to Xs yields the required list of inversions for D.
uses
Finset.card_erase_of_mem,digraph_invert_is_tournamenthave hcard : (S (digraph_invert D {a, b})).card = n := by rw [hS', Finset.card_erase_of_mem hab, hS]; rfl obtain ⟨Xs, hXs⟩ := ih _ (digraph_invert_is_tournament D _ hD) hcard exact ⟨({a, b} : Set V) :: Xs, hXs⟩
Fintype.equivFin- a finite type α is in bijection with the standard finite set Fin (|α|)
digraph_is_acyclic_of_rank- a directed graph is acyclic if there exists a ranking function to ℕ strictly increasing along every edge
Finset.card_eq_zero- a finite set has cardinality zero if and only if it is empty
lt_trichotomy- for any two elements in a linear order, exactly one of a < b, a = b, or b < a holds
Finset.mem_filter- an element belongs to a filtered finset if and only if it belongs to the ambient finset and satisfies the predicate
Finset.mem_univ- every element of a finite type belongs to the universal finset Finset.univ
true_and- the conjunction True ∧ p is equivalent to p
Finset.card_pos.mp- a finite set with strictly positive cardinality is nonempty
lt_irrefl- strict inequality in a preorder is irreflexive: a < a is false
Finset.mem_erase- an element a belongs to s.erase b if and only if a ≠ b and a ∈ s
Set.mem_insert_iff- x belongs to {a} ∪ s if and only if x = a or x ∈ s
Set.mem_singleton_iff- an element a belongs to the singleton {b} if and only if a = b
Prod.mk.injEq- pairs (a, b) and (c, d) are equal if and only if a = c and b = d
not_lt.mpr- in a linear order, if b ≤ a then a < b is false
Finset.card_erase_of_mem- erasing an element that belongs to a finite set decreases its cardinality by 1
digraph_invert_is_tournament- inverting any subset of vertices in a tournament produces another tournament
- In this formalization, inverting a digraph along a subset X flips all edges with both endpoints in X. Applying this to a two-element set {a, b} flips only the single edge between a and b, leaving every other edge untouched.
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 tournament_exists_decycling_family (V : Type) [Fintype V] (D : Digraph V) (h : digraph_is_tournament D) : ∃ Xs : List (Set V), digraph_is_acyclic (Xs.foldl digraph_invert D) := by classical let e : V ≃ Fin (Fintype.card V) := Fintype.equivFin V let S : Digraph V → Finset (V × V) := fun D => Finset.univ.filter (fun p => e p.1 < e p.2 ∧ D.Adj p.2 p.1) suffices H : ∀ n, ∀ D : Digraph V, digraph_is_tournament D → (S D).card = n → ∃ Xs : List (Set V), digraph_is_acyclic (Xs.foldl digraph_invert D) from H _ D h rfl intro n induction n with | zero => intro D hD hS refine ⟨[], ?_⟩ apply digraph_is_acyclic_of_rank _ (fun v => (e v : ℕ)) intro x y hxy rw [Finset.card_eq_zero] at hS rcases lt_trichotomy (e x) (e y) with hlt | heq | hgt · exact hlt · exfalso have hxy' : x = y := e.injective heq subst hxy' exact hD.1 x hxy · exfalso have hmem : (y, x) ∈ S D := by simp only [S, Finset.mem_filter, Finset.mem_univ, true_and] exact ⟨hgt, hxy⟩ rw [hS] at hmem simp at hmem | succ n ih => intro D hD hS obtain ⟨⟨a, b⟩, hab⟩ : (S D).Nonempty := Finset.card_pos.mp (by omega) have hab' := hab simp only [S, Finset.mem_filter, Finset.mem_univ, true_and] at hab' obtain ⟨hlt, hba⟩ := hab' have hne : a ≠ b := fun h' => by rw [h'] at hlt; exact lt_irrefl _ hlt have hnab : ¬ D.Adj a b := fun h' => (hD.2 a b hne).1 h' hba have hS' : S (digraph_invert D {a, b}) = (S D).erase (a, b) := by ext ⟨u, v⟩ simp only [S, Finset.mem_erase, Finset.mem_filter, Finset.mem_univ, true_and, digraph_invert, Set.mem_insert_iff, Set.mem_singleton_iff, ne_eq, Prod.mk.injEq] by_cases hin : (v = a ∨ v = b) ∧ (u = a ∨ u = b) · have hcase : ¬ (e u < e v) ∨ (u = a ∧ v = b) := by obtain ⟨hv | hv, hu | hu⟩ := hin <;> subst hv <;> subst hu · exact Or.inl (lt_irrefl _) · exact Or.inl (not_lt.mpr hlt.le) · exact Or.inr ⟨rfl, rfl⟩ · exact Or.inl (lt_irrefl _) rcases hcase with hc | ⟨rfl, rfl⟩ · constructor · rintro ⟨h1, _⟩; exact absurd h1 hc · rintro ⟨_, h1, _⟩; exact absurd h1 hc · constructor · rintro ⟨_, ⟨_, _, h1⟩ | ⟨h1, _⟩⟩ · exact absurd h1 hnab · exact absurd ⟨Or.inr rfl, Or.inl rfl⟩ h1 · rintro ⟨h1, _⟩; exact absurd ⟨rfl, rfl⟩ h1 · have hnot : ¬ (u = a ∧ v = b) := fun ⟨h1, h2⟩ => hin ⟨Or.inr h2, Or.inl h1⟩ constructor · rintro ⟨h1, ⟨h2, h3, _⟩ | ⟨_, h2⟩⟩ · exact absurd ⟨h2, h3⟩ hin · exact ⟨hnot, h1, h2⟩ · rintro ⟨_, h1, h2⟩ exact ⟨h1, Or.inr ⟨hin, h2⟩⟩ have hcard : (S (digraph_invert D {a, b})).card = n := by rw [hS', Finset.card_erase_of_mem hab, hS]; rfl obtain ⟨Xs, hXs⟩ := ih _ (digraph_invert_is_tournament D _ hD) hcard exact ⟨({a, b} : Set V) :: Xs, hXs⟩