AFTD Auto-Formalizing Theoretical Domains

tournament_exists_decycling_family

theoremverified

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 than LinearOrder — it does NOT require antisymmetry or…
  • digraph_invert_is_tournamentInverting a vertex set of a tournament gives a tournament.
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
Used by 4

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.

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

    lines 4–10

    uses Fintype.equivFin

      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
  2. 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) = ∅.

    lines 11–30

    uses Finset.card_eq_zero, digraph_is_acyclic_of_rank, lt_trichotomy, Finset.mem_filter, Finset.mem_univ, true_and

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

    lines 31–38

    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' hba
  4. Inverting 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.

    lines 39–65

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

        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⟩⟩
  5. 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.

    lines 66–69

    uses Finset.card_erase_of_mem, digraph_invert_is_tournament

        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⟩
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

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