tournament_exists_covering_realization
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
- tournament_universal_kings_iff_max_outdegreeFor every realizable degree vector d of an n-vertex tournament and every vertex v, v is a king in every tournament realizing d if and only…
- tournament_exists_covering_realization_of_realizesLet d be a degree vector on Fin n realized by a tournament T, and let v, w be vertices in Fin n satisfying d v < d w. Then there exists a…
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.
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).
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
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.
uses
Finset.card_insert_of_notMem,Finset.card_erase_of_memopen 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
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.
uses
tecx_invert_tournament,tecx_firstopen 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]
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.
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
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.
uses
lt_irreflopen 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
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.
uses
Nat.strong_induction_onintro k induction k using Nat.strong_induction_on with | _ k ih => intro T hT hk obtain ⟨hTt, hTd⟩ := hT
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.
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⟩
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|.
uses
Finset.card_filter_add_card_filter_not,Finset.filter_filter,and_commpush 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
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.
uses
Finset.exists_mem_neobtain ⟨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)
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.
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]
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 μ.
uses
tecx_flip,tecx_adj_out,tecx_adj_in,tecx_adj_out',Finset.card_le_card,Finset.card_erase_of_memby_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
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 μ.
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
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).
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
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.
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.
- Linear integer arithmetic (`omega`) is used to close the inequalities comparing set cardinalities and verifying that the discrepancy measure strictly decreases.
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 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