AFTD Auto-Formalizing Theoretical Domains

tournament_exists_covering_realization

theoremverifiedformalization

Let d be a realizable degree vector of an n-vertex tournament, and let v, w be vertices satisfying d v < d w. Then there exists a tournament T realizing d in which w covers v (that is, w -> v and w -> x for every out-neighbor x of v).

Statement

open Classical in
theorem tournament_exists_covering_realization {n : ℕ} (d : Fin n → ℕ)
    (hd : ∃ T : Digraph (Fin n), digraph_is_tournament T ∧ ∀ i : Fin n, digraph_out_count T i = d i)
    (v w : Fin n) (hvw : d v < d w) :
    ∃ T : Digraph (Fin n), (digraph_is_tournament T ∧ ∀ i : Fin n, digraph_out_count T i = d i) ∧
      (T.Adj w v ∧ ∀ x, T.Adj v x → T.Adj w x)
Formalizes
arXiv:2610.40521 Lemma 6
Verified
31 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • 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_out_countThe out-degree of the vertex v of a digraph on Fin n.
  • digraph_is_tournamentA digraph is a tournament when it has no loops and between any two distinct vertices there is exactly one arc.
Used by 2

Read back from the Lean

Let $n$ be a natural number and let $d : \text{Fin } n \to \mathbb{N}$ be a function. Assume that there exists a directed graph $T$ on vertex set $\text{Fin } n$ such that $T$ is a tournament and for every $i \in \text{Fin } n$, the out-degree of $i$ in $T$ is $d(i)$. Let $v, w \in \text{Fin } n$ be two vertices such that $d(v) < d(w)$. Then there exists a directed graph $T$ on $\text{Fin } n$ such that: 1. $T$ is a tournament; 2. For every $i \in \text{Fin } n$, the out-degree of $i$ in $T$ is $d(i)$; 3. There is a directed edge from $w$ to $v$ in $T$ ($T.\text{Adj } w\ v$); and 4. For every vertex $x \in \text{Fin } n$, if there is a directed edge from $v$ to $x$ in $T$, then there is also a directed edge from $w$ to $x$ in $T$ (i.e., the out-neighborhood of $v$ is contained in the out-neighborhood of $w$).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

We define a discrepancy measure μ(T) = |{x : v -> x, w ¬-> x}| + [v -> w], which is zero if and only if w covers v, and proceed by strong induction on μ(T). When μ(T) > 0, the degree inequality d(v) < d(w) implies that the set of out-neighbors of w that are not out-neighbors of v is strictly larger than {x : v -> x, w ¬-> x}, which ensures the existence of an intermediate vertex z ≠ v with w -> z -> v. Depending on the orientation between z and an uncovered out-neighbor x of v, we identify a directed 3-cycle (either w -> z -> x -> w, v -> x -> z -> v, or v -> w -> z -> v) and reverse its edges. Reversing a 3-cycle preserves all vertex out-degrees by `tecx_flip` while strictly reducing the discrepancy measure, which completes the inductive step.

  1. Inverting the orientation of all edges within a subset X preserves the tournament property.

    To show that `digraph_invert T X` is a tournament, we verify irreflexivity (no vertex has a self-loop, since either the loop was unchanged or inverted, both contradicting the irreflexivity of T) and completeness (for distinct vertices x ≠ y, exactly one directed edge exists between them, verified by case analysis on whether x and y belong to X).

    lines 1–8

    theorem tecx_invert_tournament {n : ℕ} (T : Digraph (Fin n)) (hT : digraph_is_tournament T)
        (X : Set (Fin n)) : digraph_is_tournament (digraph_invert T X) := by
      refine ⟨fun x h => ?_, fun x y hxy => ?_⟩
      · rcases h with ⟨-, -, h⟩ | ⟨-, h⟩ <;> exact hT.1 x h
      · have h1 := hT.2 x y hxy
        have h2 := hT.2 y x hxy.symm
        simp only [digraph_invert]
        by_cases hx : x ∈ X <;> by_cases hy : y ∈ X <;> simp [hx, hy] <;> tauto
  2. Inverting a directed 3-cycle a -> b -> c -> a preserves the out-degree of vertex a.

    Under inversion of the 3-cycle {a, b, c}, the out-neighbors of a change only within the cycle: the outgoing edge a -> b is reversed to b -> a (removing b from the out-neighborhood), while the edge c -> a is reversed to a -> c (inserting c into the out-neighborhood). All out-neighbors outside {a, b, c} remain unchanged. Thus the new out-neighborhood equals (N(a) \ {b}) ∪ {c}. Using `Finset.card_insert_of_notMem` and `Finset.card_erase_of_mem`, the out-degree of a is unchanged.

    lines 9–37

    uses Finset.card_insert_of_notMem, Finset.card_erase_of_mem

    open Classical in
    theorem tecx_first {n : ℕ} (T : Digraph (Fin n)) (hT : digraph_is_tournament T) (a b c : Fin n)
        (hab : T.Adj a b) (hbc : T.Adj b c) (hca : T.Adj c a) :
        (Finset.univ.filter (fun y => (digraph_invert T {a, b, c}).Adj a y)).card =
          (Finset.univ.filter (fun y => T.Adj a y)).card := by
      have hne_ab : a ≠ b := fun h => hT.1 a (h ▸ hab)
      have hne_bc : b ≠ c := fun h => hT.1 b (h ▸ hbc)
      have hne_ca : c ≠ a := fun h => hT.1 c (h ▸ hca)
      have hba : ¬ T.Adj b a := (hT.2 a b hne_ab).1 hab
      have hac : ¬ T.Adj a c := (hT.2 c a hne_ca).1 hca
      have hirr := hT.1
      have e : Finset.univ.filter (fun y => (digraph_invert T {a, b, c}).Adj a y) =
          insert c ((Finset.univ.filter (fun y => T.Adj a y)).erase b) := by
        ext y
        simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_insert, Finset.mem_erase,
          digraph_invert, Set.mem_insert_iff, Set.mem_singleton_iff]
        by_cases h1 : y = a
        · subst h1; simp [hirr, hne_ca.symm]
        by_cases h2 : y = b
        · subst h2; simp [hba, hne_bc]
        by_cases h3 : y = c
        · subst h3; simp [hca]
        simp [h1, h2, h3]
      rw [e, Finset.card_insert_of_notMem (by simp [hac]), Finset.card_erase_of_mem (by simp [hab])]
      have : 0 < (Finset.univ.filter (fun y => T.Adj a y)).card :=
        Finset.card_pos.2 ⟨b, by simp [hab]⟩
      omega
    
  3. Inverting a directed 3-cycle preserves the tournament property and preserves the out-degree of every vertex in the tournament.

    By `tecx_invert_tournament`, inverting the subset {a, b, c} produces a tournament. For any vertex i, if i = a, its out-degree is preserved by `tecx_first`. If i = b or i = c, cyclically permuting the vertices of the 3-cycle and applying `tecx_first` shows its out-degree is also preserved. If i ∉ {a, b, c}, no edges incident to i are modified, so its out-degree is unchanged.

    lines 38–58

    uses tecx_invert_tournament, tecx_first

    open Classical in
    theorem tecx_flip {n : ℕ} (T : Digraph (Fin n)) (hT : digraph_is_tournament T) (a b c : Fin n)
        (hab : T.Adj a b) (hbc : T.Adj b c) (hca : T.Adj c a) :
        digraph_is_tournament (digraph_invert T {a, b, c}) ∧
          ∀ i, digraph_out_count (digraph_invert T {a, b, c}) i = digraph_out_count T i := by
      refine ⟨tecx_invert_tournament T hT _, fun i => ?_⟩
      unfold digraph_out_count
      by_cases hia : i = a
      · subst hia; exact tecx_first T hT i b c hab hbc hca
      by_cases hib : i = b
      · subst hib
        have hs : ({a, i, c} : Set (Fin n)) = {i, c, a} := by ext; simp; tauto
        rw [hs]; exact tecx_first T hT i c a hbc hca hab
      by_cases hic : i = c
      · subst hic
        have hs : ({a, b, i} : Set (Fin n)) = {i, a, b} := by ext; simp; tauto
        rw [hs]; exact tecx_first T hT i a b hca hab hbc
      congr 1
      ext y
      simp [digraph_invert, hia, hib, hic]
    
  4. Edge orientations between vertices are affected by inverting X if and only if both endpoints lie in X.

    Unfolding `digraph_invert`, if the source vertex u ∉ X (`tecx_adj_out`) or the target vertex y ∉ X (`tecx_adj_out'`), the adjacency u -> y is unchanged. If both endpoints u, y ∈ X (`tecx_adj_in`), the edge direction is reversed.

    lines 59–70

    theorem tecx_adj_out {n : ℕ} (T : Digraph (Fin n)) (X : Set (Fin n)) {u y : Fin n} (hu : u ∉ X) :
        (digraph_invert T X).Adj u y ↔ T.Adj u y := by
      simp only [digraph_invert]; tauto
    
    theorem tecx_adj_out' {n : ℕ} (T : Digraph (Fin n)) (X : Set (Fin n)) {u y : Fin n} (hy : y ∉ X) :
        (digraph_invert T X).Adj u y ↔ T.Adj u y := by
      simp only [digraph_invert]; tauto
    
    theorem tecx_adj_in {n : ℕ} (T : Digraph (Fin n)) (X : Set (Fin n)) {u y : Fin n} (hu : u ∈ X)
        (hy : y ∈ X) : (digraph_invert T X).Adj u y ↔ T.Adj y u := by
      simp only [digraph_invert]; tauto
    
  5. The problem reduces to showing by strong induction on discrepancy that any tournament realizing d can be converted to one where w covers v.

    We obtain an initial tournament T₀ realizing the degree vector d. Since d(v) < d(w), we have v ≠ w by irreflexivity of < (`lt_irrefl`). We define a discrepancy measure μ(T) as the number of vertices x where v -> x and w ¬-> x, plus 1 if v -> w (and 0 otherwise). When μ(T) = 0, w -> v and every out-neighbor of v is an out-neighbor of w, so w covers v. It therefore suffices to prove by strong induction on k = μ(T) that any realization T with μ(T) = k can be transformed into a covering realization.

    lines 71–85

    uses lt_irrefl

    open Classical in
    /-- For any realizable degree vector d and vertices v, w with d(v) < d(w), there is a realization of d where w covers v. -/
    theorem tournament_exists_covering_realization {n : ℕ} (d : Fin n → ℕ)
        (hd : ∃ T : Digraph (Fin n), digraph_is_tournament T ∧ ∀ i : Fin n, digraph_out_count T i = d i)
        (v w : Fin n) (hvw : d v < d w) :
        ∃ T : Digraph (Fin n), (digraph_is_tournament T ∧ ∀ i : Fin n, digraph_out_count T i = d i) ∧
          (T.Adj w v ∧ ∀ x, T.Adj v x → T.Adj w x) := by
      obtain ⟨T0, hT0⟩ := hd
      have hvw' : v ≠ w := fun h => by rw [h] at hvw; exact lt_irrefl _ hvw
      let μ : Digraph (Fin n) → ℕ := fun T =>
        (Finset.univ.filter (fun x => T.Adj v x ∧ ¬ T.Adj w x)).card + (if T.Adj v w then 1 else 0)
      suffices H : ∀ k, ∀ T : Digraph (Fin n),
          (digraph_is_tournament T ∧ ∀ i : Fin n, digraph_out_count T i = d i) → μ T = k →
          ∃ T : Digraph (Fin n), (digraph_is_tournament T ∧ ∀ i : Fin n, digraph_out_count T i = d i) ∧
            (T.Adj w v ∧ ∀ x, T.Adj v x → T.Adj w x) from H _ T0 hT0 rfl
  6. Set up strong induction on the discrepancy k = μ(T).

    We induct on k using `Nat.strong_induction_on`. In the inductive step, we consider a tournament T realizing d with μ(T) = k, with the induction hypothesis that the theorem holds for any tournament realizing d with smaller discrepancy.

    lines 86–90

    uses Nat.strong_induction_on

      intro k
      induction k using Nat.strong_induction_on with
      | _ k ih =>
      intro T hT hk
      obtain ⟨hTt, hTd⟩ := hT
  7. If no vertex x satisfies v -> x and w ¬-> x, then w already covers v in T, so T itself is the desired tournament.

    If the set of non-covered out-neighbors {x : v -> x ∧ ¬(w -> x)} is empty, substituting x = w implies ¬(v -> w), since otherwise w would belong to this set as tournaments have no self-loops. By tournament trichotomy on v ≠ w, this gives w -> v. Furthermore, any out-neighbor of v is an out-neighbor of w by assumption, so w covers v in T, completing the proof for this case.

    lines 91–95

      by_cases hA : ∀ x, ¬ (T.Adj v x ∧ ¬ T.Adj w x)
      · refine ⟨T, ⟨hTt, hTd⟩, ?_, fun x hx => ?_⟩
        · have : ¬ T.Adj v w := fun h => hA w ⟨h, hTt.1 w⟩
          exact (hTt.2 w v hvw'.symm).2 this
        · by_contra h; exact hA x ⟨hx, h⟩
  8. The set A of vertices x with v -> x and w ¬-> x is non-empty, and |A| is strictly less than |B|, where B = {x : w -> x ∧ ¬(v -> x)}.

    When the previous case fails, there exists an element x₀ ∈ A. We partition the out-neighborhoods of v and w into vertices adjacent to both and vertices adjacent to only one using `Finset.card_filter_add_card_filter_not` and `Finset.filter_filter`. The intersection terms coincide by `and_comm`. Because d(v) < d(w), linear arithmetic (`omega`) implies |A| < |B|.

    lines 96–113

    uses Finset.card_filter_add_card_filter_not, Finset.filter_filter, and_comm

      push Not at hA
      obtain ⟨x0, hvx0, hwx0⟩ := hA
      have hx0A : x0 ∈ Finset.univ.filter (fun x => T.Adj v x ∧ ¬ T.Adj w x) := by simp [hvx0, hwx0]
      have hcount : (Finset.univ.filter (fun x => T.Adj v x ∧ ¬ T.Adj w x)).card <
          (Finset.univ.filter (fun x => T.Adj w x ∧ ¬ T.Adj v x)).card := by
        have hv := hTd v
        have hw := hTd w
        unfold digraph_out_count at hv hw
        have e1 := Finset.card_filter_add_card_filter_not
          (s := Finset.univ.filter (fun y => T.Adj v y)) (fun y => T.Adj w y)
        have e2 := Finset.card_filter_add_card_filter_not
          (s := Finset.univ.filter (fun y => T.Adj w y)) (fun y => T.Adj v y)
        simp only [Finset.filter_filter] at e1 e2
        have e3 : (Finset.univ.filter (fun y => T.Adj v y ∧ T.Adj w y)) =
            Finset.univ.filter (fun y => T.Adj w y ∧ T.Adj v y) := by
          ext y; simp [and_comm]
        rw [e3] at e1
        omega
  9. There exists a vertex z distinct from v such that w -> z and z -> v.

    Since x₀ ∈ A, we have |B| > |A| ≥ 1, so |B| ≥ 2. By `Finset.exists_mem_ne`, B contains an element z with z ≠ v. By definition of B, w -> z and ¬(v -> z), which in a tournament with z ≠ v implies z -> v. Also z ≠ w because w -> z and tournaments are loopless.

    lines 114–120

    uses Finset.exists_mem_ne

      obtain ⟨z, hzB, hzv⟩ := Finset.exists_mem_ne
        (s := Finset.univ.filter (fun x => T.Adj w x ∧ ¬ T.Adj v x))
        (by have := Finset.card_pos.2 ⟨x0, hx0A⟩; omega) v
      simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hzB
      obtain ⟨hwz, hvz⟩ := hzB
      have hzv' : T.Adj z v := (hTt.2 z v hzv).2 hvz
      have hzw : z ≠ w := fun h => hTt.1 w (h ▸ hwz)
  10. To complete the step, it suffices to find a tournament T' realizing d with μ(T') < μ(T); we begin by analyzing the case where A contains an element x ≠ w.

    We split on whether there exists x ∈ A with x ≠ w. If such an x exists, then x ≠ v and x ≠ z (since v -> x while ¬(v -> z)). Since x ≠ w and ¬(w -> x), the tournament property gives x -> w.

    lines 121–128

      have hlt : ∃ T', (digraph_is_tournament T' ∧ ∀ i : Fin n, digraph_out_count T' i = d i) ∧
          μ T' < μ T := by
        by_cases hx1 : ∃ x, T.Adj v x ∧ ¬ T.Adj w x ∧ x ≠ w
        · obtain ⟨x, hvx, hwx, hxw⟩ := hx1
          have hxv : x ≠ v := fun h => hTt.1 v (h ▸ hvx)
          have hxz : x ≠ z := fun h => hvz (h ▸ hvx)
          have hxw' : T.Adj x w := (hTt.2 x w hxw).2 hwx
          have hxA : x ∈ Finset.univ.filter (fun x => T.Adj v x ∧ ¬ T.Adj w x) := by simp [hvx, hwx]
  11. If z -> x, inverting the directed 3-cycle w -> z -> x -> w yields a realization T' with μ(T') < μ(T).

    When z -> x, the vertices w, z, x form a directed 3-cycle w -> z -> x -> w. Inverting this cycle preserves tournamenthood and vertex out-degrees by `tecx_flip`. Since v ∉ {w, z, x}, edges from v are unaffected by `tecx_adj_out`. The inverted edge w -> x removes x from A, and checking cases with `tecx_adj_in` and `tecx_adj_out'` confirms no new vertices enter A. Thus the new set A' is a subset of A \ {x}. By `Finset.card_le_card` and `Finset.card_erase_of_mem`, |A'| decreases by at least 1, while the v-w edge is unchanged by `tecx_adj_out`, strictly decreasing μ.

    lines 129–158

    uses tecx_flip, tecx_adj_out, tecx_adj_in, tecx_adj_out', Finset.card_le_card, Finset.card_erase_of_mem

          by_cases hzx : T.Adj z x
          · -- reverse the cycle w → z → x → w
            obtain ⟨h1, h2⟩ := tecx_flip T hTt w z x hwz hzx hxw'
            refine ⟨_, ⟨h1, fun i => (h2 i).trans (hTd i)⟩, ?_⟩
            have hvX : v ∉ ({w, z, x} : Set (Fin n)) := by
              simp only [Set.mem_insert_iff, Set.mem_singleton_iff]; push Not
              exact ⟨hvw', hzv.symm, hxv.symm⟩
            have hsub : Finset.univ.filter (fun y => (digraph_invert T {w, z, x}).Adj v y ∧
                ¬ (digraph_invert T {w, z, x}).Adj w y) ⊆
                (Finset.univ.filter (fun x => T.Adj v x ∧ ¬ T.Adj w x)).erase x := by
              intro y hy
              simp only [Finset.mem_filter, Finset.mem_univ, true_and, tecx_adj_out T _ hvX] at hy
              simp only [Finset.mem_erase, Finset.mem_filter, Finset.mem_univ, true_and]
              have hwX : w ∈ ({w, z, x} : Set (Fin n)) := by simp
              by_cases hyx : y = x
              · subst hyx
                exact absurd ((tecx_adj_in T _ hwX (by simp)).2 hxw') hy.2
              by_cases hyz : y = z
              · subst hyz; exact absurd hy.1 hvz
              by_cases hyw : y = w
              · subst hyw; exact ⟨hyx, hy.1, hTt.1 _⟩
              have hyX : y ∉ ({w, z, x} : Set (Fin n)) := by
                simp only [Set.mem_insert_iff, Set.mem_singleton_iff]; push Not; exact ⟨hyw, hyz, hyx⟩
              exact ⟨hyx, hy.1, fun h => hy.2 ((tecx_adj_out' T _ hyX).2 h)⟩
            have hc := Finset.card_le_card hsub
            rw [Finset.card_erase_of_mem hxA] at hc
            have hpos := Finset.card_pos.2 ⟨x, hxA⟩
            have hind : (digraph_invert T {w, z, x}).Adj v w ↔ T.Adj v w := tecx_adj_out T _ hvX
            simp only [μ, hind]
            omega
  12. If x -> z, inverting the directed 3-cycle v -> x -> z -> v yields a realization T' with μ(T') < μ(T).

    When ¬(z -> x), the tournament property gives x -> z, forming the directed 3-cycle v -> x -> z -> v. Inverting this cycle preserves tournamenthood and out-degrees by `tecx_flip`. Since w ∉ {v, x, z}, edges from w are unaffected by `tecx_adj_out`. The reversed edge x -> v removes x from A, and no new vertices enter A (using `tecx_adj_in`, `tecx_invert_tournament`, and `tecx_adj_out'`). Thus A' ⊆ A \ {x}, so by `Finset.card_le_card` and `Finset.card_erase_of_mem` its cardinality decreases, while the v-w edge is unchanged by `tecx_adj_out'`, strictly decreasing μ.

    lines 159–188

    uses tecx_flip, tecx_adj_out, tecx_adj_in, tecx_invert_tournament, tecx_adj_out', Finset.card_le_card, Finset.card_erase_of_mem

          · -- reverse the cycle v → x → z → v
            have hxz' : T.Adj x z := (hTt.2 x z hxz).2 hzx
            obtain ⟨h1, h2⟩ := tecx_flip T hTt v x z hvx hxz' hzv'
            refine ⟨_, ⟨h1, fun i => (h2 i).trans (hTd i)⟩, ?_⟩
            have hwX : w ∉ ({v, x, z} : Set (Fin n)) := by
              simp only [Set.mem_insert_iff, Set.mem_singleton_iff]; push Not
              exact ⟨hvw'.symm, fun h => hxw h.symm, hzw.symm⟩
            have hvX : v ∈ ({v, x, z} : Set (Fin n)) := by simp
            have hsub : Finset.univ.filter (fun y => (digraph_invert T {v, x, z}).Adj v y ∧
                ¬ (digraph_invert T {v, x, z}).Adj w y) ⊆
                (Finset.univ.filter (fun x => T.Adj v x ∧ ¬ T.Adj w x)).erase x := by
              intro y hy
              simp only [Finset.mem_filter, Finset.mem_univ, true_and, tecx_adj_out T _ hwX] at hy
              simp only [Finset.mem_erase, Finset.mem_filter, Finset.mem_univ, true_and]
              by_cases hyx : y = x
              · subst hyx
                exact absurd ((tecx_adj_in T _ hvX (by simp)).1 hy.1) ((hTt.2 v y hxv.symm).1 hvx)
              by_cases hyz : y = z
              · subst hyz; exact absurd hwz hy.2
              by_cases hyv : y = v
              · subst hyv; exact absurd hy.1 ((tecx_invert_tournament T hTt _).1 y)
              have hyX : y ∉ ({v, x, z} : Set (Fin n)) := by
                simp only [Set.mem_insert_iff, Set.mem_singleton_iff]; push Not; exact ⟨hyv, hyx, hyz⟩
              exact ⟨hyx, (tecx_adj_out' T _ hyX).1 hy.1, hy.2⟩
            have hc := Finset.card_le_card hsub
            rw [Finset.card_erase_of_mem hxA] at hc
            have hpos := Finset.card_pos.2 ⟨x, hxA⟩
            have hind : (digraph_invert T {v, x, z}).Adj v w ↔ T.Adj v w := tecx_adj_out' T _ hwX
            simp only [μ, hind]
            omega
  13. If no x ∈ A satisfies x ≠ w, then v -> w, and inverting the 3-cycle v -> w -> z -> v yields a realization T' with μ(T') < μ(T).

    If no such x exists, the non-empty set A is the singleton {w}, which implies v -> w and μ(T) = 1 + 1 = 2. Together with w -> z and z -> v, this forms the 3-cycle v -> w -> z -> v. Inverting it via `tecx_flip` turns v -> w into w -> v, eliminating the indicator term [v -> w]. The new set A' is contained in {z} (by `tecx_invert_tournament`, `tecx_adj_in`, and `tecx_adj_out'`), so by `Finset.card_le_card` and `Finset.card_singleton`, |A'| ≤ 1. Hence μ(T') ≤ 1 + 0 < 2 = μ(T).

    lines 189–218

    uses tecx_flip, tecx_invert_tournament, tecx_adj_in, tecx_adj_out', Finset.card_le_card, Finset.card_singleton

        · push Not at hx1
          have hvw2 : T.Adj v w := by
            have := hx1 x0 hvx0 hwx0; rw [← this]; exact hvx0
          -- reverse the cycle v → w → z → v
          obtain ⟨h1, h2⟩ := tecx_flip T hTt v w z hvw2 hwz hzv'
          refine ⟨_, ⟨h1, fun i => (h2 i).trans (hTd i)⟩, ?_⟩
          have hvX : v ∈ ({v, w, z} : Set (Fin n)) := by simp
          have hwX : w ∈ ({v, w, z} : Set (Fin n)) := by simp
          have hsub : Finset.univ.filter (fun y => (digraph_invert T {v, w, z}).Adj v y ∧
              ¬ (digraph_invert T {v, w, z}).Adj w y) ⊆ {z} := by
            intro y hy
            simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hy
            simp only [Finset.mem_singleton]
            by_contra hyz
            by_cases hyv : y = v
            · subst hyv; exact absurd hy.1 ((tecx_invert_tournament T hTt _).1 y)
            by_cases hyw : y = w
            · subst hyw
              exact absurd ((tecx_adj_in T _ hvX hwX).1 hy.1) ((hTt.2 v y hvw').1 hvw2)
            have hyX : y ∉ ({v, w, z} : Set (Fin n)) := by
              simp only [Set.mem_insert_iff, Set.mem_singleton_iff]; push Not; exact ⟨hyv, hyw, hyz⟩
            exact hyw (hx1 y ((tecx_adj_out' T _ hyX).1 hy.1)
              (fun h => hy.2 ((tecx_adj_out' T _ hyX).2 h)))
          have hc := Finset.card_le_card hsub
          rw [Finset.card_singleton] at hc
          have hpos := Finset.card_pos.2 ⟨x0, hx0A⟩
          have hind : ¬ (digraph_invert T {v, w, z}).Adj v w := fun h =>
            (hTt.2 v w hvw').1 hvw2 ((tecx_adj_in T _ hvX hwX).1 h)
          simp only [μ, hind, hvw2, if_true, if_false]
          omega
  14. Applying the induction hypothesis to T' produces the desired covering tournament.

    With T' realizing the degree vector d and having strictly smaller discrepancy μ(T') < k, the strong induction hypothesis produces a tournament realizing d in which w covers v.

    lines 219–220

      obtain ⟨T', hT', hlt'⟩ := hlt
      exact ih (μ T') (hk ▸ hlt') T' hT' rfl
Finset.card_insert_of_notMem
Inserting an element into a finite set that does not contain it increases the cardinality by 1.
Finset.card_erase_of_mem
Removing an element from a finite set containing it decreases its cardinality by 1.
tecx_invert_tournament
Inverting the edges between vertices in an arbitrary subset of a tournament preserves the tournament property.
tecx_first
Inverting a directed 3-cycle a -> b -> c -> a preserves the out-degree of vertex a.
lt_irrefl
Strict inequality is irreflexive: no element is strictly less than itself.
Nat.strong_induction_on
Strong induction principle for natural numbers: to prove a property holds for all n, it suffices to prove it for n assuming it holds for all m < n.
Finset.card_filter_add_card_filter_not
For any finite set and predicate, the number of elements satisfying the predicate plus the number of elements not satisfying it equals the cardinality of the set.
Finset.filter_filter
Filtering a finite set successively by two predicates is equivalent to filtering by their conjunction.
and_comm
Conjunction of two propositions is commutative.
Finset.exists_mem_ne
Any finite set with cardinality greater than 1 contains an element distinct from any specified element.
tecx_flip
Inverting a directed 3-cycle in a tournament preserves the tournament property and preserves the out-degree of every vertex.
tecx_adj_out
Inverting edges within a vertex subset X does not change the outgoing edges from any vertex outside X.
tecx_adj_in
Inverting edges within a vertex subset X reverses the direction of every edge between two vertices in X.
tecx_adj_out'
Inverting edges within a vertex subset X does not change the incoming edges to any vertex outside X.
Finset.card_le_card
If a finite set s is a subset of t, then the cardinality of s is at most that of t.
Finset.card_singleton
A singleton set has cardinality 1.

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 tecx_invert_tournament {n : ℕ} (T : Digraph (Fin n)) (hT : digraph_is_tournament T)    (X : Set (Fin n)) : digraph_is_tournament (digraph_invert T X) := by  refine ⟨fun x h => ?_, fun x y hxy => ?_⟩  · rcases h with ⟨-, -, h⟩ | ⟨-, h⟩ <;> exact hT.1 x h  · have h1 := hT.2 x y hxy    have h2 := hT.2 y x hxy.symm    simp only [digraph_invert]    by_cases hx : x ∈ X <;> by_cases hy : y ∈ X <;> simp [hx, hy] <;> tautoopen Classical intheorem tecx_first {n : ℕ} (T : Digraph (Fin n)) (hT : digraph_is_tournament T) (a b c : Fin n)    (hab : T.Adj a b) (hbc : T.Adj b c) (hca : T.Adj c a) :    (Finset.univ.filter (fun y => (digraph_invert T {a, b, c}).Adj a y)).card =      (Finset.univ.filter (fun y => T.Adj a y)).card := by  have hne_ab : a ≠ b := fun h => hT.1 a (h ▸ hab)  have hne_bc : b ≠ c := fun h => hT.1 b (h ▸ hbc)  have hne_ca : c ≠ a := fun h => hT.1 c (h ▸ hca)  have hba : ¬ T.Adj b a := (hT.2 a b hne_ab).1 hab  have hac : ¬ T.Adj a c := (hT.2 c a hne_ca).1 hca  have hirr := hT.1  have e : Finset.univ.filter (fun y => (digraph_invert T {a, b, c}).Adj a y) =      insert c ((Finset.univ.filter (fun y => T.Adj a y)).erase b) := by    ext y    simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_insert, Finset.mem_erase,      digraph_invert, Set.mem_insert_iff, Set.mem_singleton_iff]    by_cases h1 : y = a    · subst h1; simp [hirr, hne_ca.symm]    by_cases h2 : y = b    · subst h2; simp [hba, hne_bc]    by_cases h3 : y = c    · subst h3; simp [hca]    simp [h1, h2, h3]  rw [e, Finset.card_insert_of_notMem (by simp [hac]), Finset.card_erase_of_mem (by simp [hab])]  have : 0 < (Finset.univ.filter (fun y => T.Adj a y)).card :=    Finset.card_pos.2 ⟨b, by simp [hab]⟩  omegaopen Classical intheorem tecx_flip {n : ℕ} (T : Digraph (Fin n)) (hT : digraph_is_tournament T) (a b c : Fin n)    (hab : T.Adj a b) (hbc : T.Adj b c) (hca : T.Adj c a) :    digraph_is_tournament (digraph_invert T {a, b, c}) ∧      ∀ i, digraph_out_count (digraph_invert T {a, b, c}) i = digraph_out_count T i := by  refine ⟨tecx_invert_tournament T hT _, fun i => ?_⟩  unfold digraph_out_count  by_cases hia : i = a  · subst hia; exact tecx_first T hT i b c hab hbc hca  by_cases hib : i = b  · subst hib    have hs : ({a, i, c} : Set (Fin n)) = {i, c, a} := by ext; simp; tauto    rw [hs]; exact tecx_first T hT i c a hbc hca hab  by_cases hic : i = c  · subst hic    have hs : ({a, b, i} : Set (Fin n)) = {i, a, b} := by ext; simp; tauto    rw [hs]; exact tecx_first T hT i a b hca hab hbc  congr 1  ext y  simp [digraph_invert, hia, hib, hic]theorem tecx_adj_out {n : ℕ} (T : Digraph (Fin n)) (X : Set (Fin n)) {u y : Fin n} (hu : u ∉ X) :    (digraph_invert T X).Adj u y ↔ T.Adj u y := by  simp only [digraph_invert]; tautotheorem tecx_adj_out' {n : ℕ} (T : Digraph (Fin n)) (X : Set (Fin n)) {u y : Fin n} (hy : y ∉ X) :    (digraph_invert T X).Adj u y ↔ T.Adj u y := by  simp only [digraph_invert]; tautotheorem tecx_adj_in {n : ℕ} (T : Digraph (Fin n)) (X : Set (Fin n)) {u y : Fin n} (hu : u ∈ X)    (hy : y ∈ X) : (digraph_invert T X).Adj u y ↔ T.Adj y u := by  simp only [digraph_invert]; tautoopen Classical in/-- For any realizable degree vector d and vertices v, w with d(v) < d(w), there is a realization of d where w covers v. -/theorem tournament_exists_covering_realization {n : ℕ} (d : Fin n → ℕ)    (hd : ∃ T : Digraph (Fin n), digraph_is_tournament T ∧ ∀ i : Fin n, digraph_out_count T i = d i)    (v w : Fin n) (hvw : d v < d w) :    ∃ T : Digraph (Fin n), (digraph_is_tournament T ∧ ∀ i : Fin n, digraph_out_count T i = d i) ∧      (T.Adj w v ∧ ∀ x, T.Adj v x → T.Adj w x) := by  obtain ⟨T0, hT0⟩ := hd  have hvw' : v ≠ w := fun h => by rw [h] at hvw; exact lt_irrefl _ hvw  let μ : Digraph (Fin n) → ℕ := fun T =>    (Finset.univ.filter (fun x => T.Adj v x ∧ ¬ T.Adj w x)).card + (if T.Adj v w then 1 else 0)  suffices H : ∀ k, ∀ T : Digraph (Fin n),      (digraph_is_tournament T ∧ ∀ i : Fin n, digraph_out_count T i = d i) → μ T = k →      ∃ T : Digraph (Fin n), (digraph_is_tournament T ∧ ∀ i : Fin n, digraph_out_count T i = d i) ∧        (T.Adj w v ∧ ∀ x, T.Adj v x → T.Adj w x) from H _ T0 hT0 rfl  intro k  induction k using Nat.strong_induction_on with  | _ k ih =>  intro T hT hk  obtain ⟨hTt, hTd⟩ := hT  by_cases hA : ∀ x, ¬ (T.Adj v x ∧ ¬ T.Adj w x)  · refine ⟨T, ⟨hTt, hTd⟩, ?_, fun x hx => ?_⟩    · have : ¬ T.Adj v w := fun h => hA w ⟨h, hTt.1 w⟩      exact (hTt.2 w v hvw'.symm).2 this    · by_contra h; exact hA x ⟨hx, h⟩  push Not at hA  obtain ⟨x0, hvx0, hwx0⟩ := hA  have hx0A : x0 ∈ Finset.univ.filter (fun x => T.Adj v x ∧ ¬ T.Adj w x) := by simp [hvx0, hwx0]  have hcount : (Finset.univ.filter (fun x => T.Adj v x ∧ ¬ T.Adj w x)).card <      (Finset.univ.filter (fun x => T.Adj w x ∧ ¬ T.Adj v x)).card := by    have hv := hTd v    have hw := hTd w    unfold digraph_out_count at hv hw    have e1 := Finset.card_filter_add_card_filter_not      (s := Finset.univ.filter (fun y => T.Adj v y)) (fun y => T.Adj w y)    have e2 := Finset.card_filter_add_card_filter_not      (s := Finset.univ.filter (fun y => T.Adj w y)) (fun y => T.Adj v y)    simp only [Finset.filter_filter] at e1 e2    have e3 : (Finset.univ.filter (fun y => T.Adj v y ∧ T.Adj w y)) =        Finset.univ.filter (fun y => T.Adj w y ∧ T.Adj v y) := by      ext y; simp [and_comm]    rw [e3] at e1    omega  obtain ⟨z, hzB, hzv⟩ := Finset.exists_mem_ne    (s := Finset.univ.filter (fun x => T.Adj w x ∧ ¬ T.Adj v x))    (by have := Finset.card_pos.2 ⟨x0, hx0A⟩; omega) v  simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hzB  obtain ⟨hwz, hvz⟩ := hzB  have hzv' : T.Adj z v := (hTt.2 z v hzv).2 hvz  have hzw : z ≠ w := fun h => hTt.1 w (h ▸ hwz)  have hlt : ∃ T', (digraph_is_tournament T' ∧ ∀ i : Fin n, digraph_out_count T' i = d i) ∧      μ T' < μ T := by    by_cases hx1 : ∃ x, T.Adj v x ∧ ¬ T.Adj w x ∧ x ≠ w    · obtain ⟨x, hvx, hwx, hxw⟩ := hx1      have hxv : x ≠ v := fun h => hTt.1 v (h ▸ hvx)      have hxz : x ≠ z := fun h => hvz (h ▸ hvx)      have hxw' : T.Adj x w := (hTt.2 x w hxw).2 hwx      have hxA : x ∈ Finset.univ.filter (fun x => T.Adj v x ∧ ¬ T.Adj w x) := by simp [hvx, hwx]      by_cases hzx : T.Adj z x      · -- reverse the cycle w → z → x → w        obtain ⟨h1, h2⟩ := tecx_flip T hTt w z x hwz hzx hxw'        refine ⟨_, ⟨h1, fun i => (h2 i).trans (hTd i)⟩, ?_⟩        have hvX : v ∉ ({w, z, x} : Set (Fin n)) := by          simp only [Set.mem_insert_iff, Set.mem_singleton_iff]; push Not          exact ⟨hvw', hzv.symm, hxv.symm⟩        have hsub : Finset.univ.filter (fun y => (digraph_invert T {w, z, x}).Adj v y ∧            ¬ (digraph_invert T {w, z, x}).Adj w y) ⊆            (Finset.univ.filter (fun x => T.Adj v x ∧ ¬ T.Adj w x)).erase x := by          intro y hy          simp only [Finset.mem_filter, Finset.mem_univ, true_and, tecx_adj_out T _ hvX] at hy          simp only [Finset.mem_erase, Finset.mem_filter, Finset.mem_univ, true_and]          have hwX : w ∈ ({w, z, x} : Set (Fin n)) := by simp          by_cases hyx : y = x          · subst hyx            exact absurd ((tecx_adj_in T _ hwX (by simp)).2 hxw') hy.2          by_cases hyz : y = z          · subst hyz; exact absurd hy.1 hvz          by_cases hyw : y = w          · subst hyw; exact ⟨hyx, hy.1, hTt.1 _⟩          have hyX : y ∉ ({w, z, x} : Set (Fin n)) := by            simp only [Set.mem_insert_iff, Set.mem_singleton_iff]; push Not; exact ⟨hyw, hyz, hyx⟩          exact ⟨hyx, hy.1, fun h => hy.2 ((tecx_adj_out' T _ hyX).2 h)⟩        have hc := Finset.card_le_card hsub        rw [Finset.card_erase_of_mem hxA] at hc        have hpos := Finset.card_pos.2 ⟨x, hxA⟩        have hind : (digraph_invert T {w, z, x}).Adj v w ↔ T.Adj v w := tecx_adj_out T _ hvX        simp only [μ, hind]        omega      · -- reverse the cycle v → x → z → v        have hxz' : T.Adj x z := (hTt.2 x z hxz).2 hzx        obtain ⟨h1, h2⟩ := tecx_flip T hTt v x z hvx hxz' hzv'        refine ⟨_, ⟨h1, fun i => (h2 i).trans (hTd i)⟩, ?_⟩        have hwX : w ∉ ({v, x, z} : Set (Fin n)) := by          simp only [Set.mem_insert_iff, Set.mem_singleton_iff]; push Not          exact ⟨hvw'.symm, fun h => hxw h.symm, hzw.symm⟩        have hvX : v ∈ ({v, x, z} : Set (Fin n)) := by simp        have hsub : Finset.univ.filter (fun y => (digraph_invert T {v, x, z}).Adj v y ∧            ¬ (digraph_invert T {v, x, z}).Adj w y) ⊆            (Finset.univ.filter (fun x => T.Adj v x ∧ ¬ T.Adj w x)).erase x := by          intro y hy          simp only [Finset.mem_filter, Finset.mem_univ, true_and, tecx_adj_out T _ hwX] at hy          simp only [Finset.mem_erase, Finset.mem_filter, Finset.mem_univ, true_and]          by_cases hyx : y = x          · subst hyx            exact absurd ((tecx_adj_in T _ hvX (by simp)).1 hy.1) ((hTt.2 v y hxv.symm).1 hvx)          by_cases hyz : y = z          · subst hyz; exact absurd hwz hy.2          by_cases hyv : y = v          · subst hyv; exact absurd hy.1 ((tecx_invert_tournament T hTt _).1 y)          have hyX : y ∉ ({v, x, z} : Set (Fin n)) := by            simp only [Set.mem_insert_iff, Set.mem_singleton_iff]; push Not; exact ⟨hyv, hyx, hyz⟩          exact ⟨hyx, (tecx_adj_out' T _ hyX).1 hy.1, hy.2⟩        have hc := Finset.card_le_card hsub        rw [Finset.card_erase_of_mem hxA] at hc        have hpos := Finset.card_pos.2 ⟨x, hxA⟩        have hind : (digraph_invert T {v, x, z}).Adj v w ↔ T.Adj v w := tecx_adj_out' T _ hwX        simp only [μ, hind]        omega    · push Not at hx1      have hvw2 : T.Adj v w := by        have := hx1 x0 hvx0 hwx0; rw [← this]; exact hvx0      -- reverse the cycle v → w → z → v      obtain ⟨h1, h2⟩ := tecx_flip T hTt v w z hvw2 hwz hzv'      refine ⟨_, ⟨h1, fun i => (h2 i).trans (hTd i)⟩, ?_⟩      have hvX : v ∈ ({v, w, z} : Set (Fin n)) := by simp      have hwX : w ∈ ({v, w, z} : Set (Fin n)) := by simp      have hsub : Finset.univ.filter (fun y => (digraph_invert T {v, w, z}).Adj v y ∧          ¬ (digraph_invert T {v, w, z}).Adj w y) ⊆ {z} := by        intro y hy        simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hy        simp only [Finset.mem_singleton]        by_contra hyz        by_cases hyv : y = v        · subst hyv; exact absurd hy.1 ((tecx_invert_tournament T hTt _).1 y)        by_cases hyw : y = w        · subst hyw          exact absurd ((tecx_adj_in T _ hvX hwX).1 hy.1) ((hTt.2 v y hvw').1 hvw2)        have hyX : y ∉ ({v, w, z} : Set (Fin n)) := by          simp only [Set.mem_insert_iff, Set.mem_singleton_iff]; push Not; exact ⟨hyv, hyw, hyz⟩        exact hyw (hx1 y ((tecx_adj_out' T _ hyX).1 hy.1)          (fun h => hy.2 ((tecx_adj_out' T _ hyX).2 h)))      have hc := Finset.card_le_card hsub      rw [Finset.card_singleton] at hc      have hpos := Finset.card_pos.2 ⟨x0, hx0A⟩      have hind : ¬ (digraph_invert T {v, w, z}).Adj v w := fun h =>        (hTt.2 v w hvw').1 hvw2 ((tecx_adj_in T _ hvX hwX).1 h)      simp only [μ, hind, hvw2, if_true, if_false]      omega  obtain ⟨T', hT', hlt'⟩ := hlt  exact ih (μ T') (hk ▸ hlt') T' hT' rfl
See it in the graphDiscuss this resultChallenge it