tournament_not_near_regular_exists_arc_degree_gap
In a tournament on 2m vertices with m ≥ 2 that is not near-regular, there are vertices u, v with an arc u → v and out-degree of v at least 2 smaller than the out-degree of u.
Statement
theorem tournament_not_near_regular_exists_arc_degree_gap (m : ℕ) (hm : 2 ≤ m)
(T : Digraph (Fin (2 * m))) [DecidableRel T.Adj] (hT : digraph_is_tournament T)
(hnr : ¬ tournament_is_near_regular m T) :
∃ u v : Fin (2 * m), T.Adj u v ∧ digraph_out_count T v + 2 ≤ digraph_out_count T u- Source
- step towards tournament_not_near_regular_exists_improving_tournament
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- tournament_sum_out_countIn a tournament T on Fin n, the out-degrees sum to the number of unordered pairs: ∑_i d_i = n(n-1)/2.
- tournament_near_regular_of_card_degreesIf a digraph on 2m vertices has exactly m vertices of out-degree m - 1 and exactly m vertices of out-degree m, then it is near-regular.
- digraph_is_tournamentA digraph is a tournament when it has no loops and between any two distinct vertices there is exactly one arc.
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - tournament_is_near_regularA tournament on 2m vertices is near-regular if every vertex has out-degree m - 1 or m.
- digraph_out_countThe out-degree of the vertex v of a digraph on Fin n.
- Used by 1
- tournament_four_not_near_regular_exists_improvingThe m = 2 case of the target, settled by finite computation: a non-near-regular tournament on 4 vertices has at most 9 arborescences while…
The proof, explained
We argue by contradiction, assuming that every arc $u \to v$ in the tournament satisfies $\operatorname{out}(u) \le \operatorname{out}(v) + 1$. A reachability argument shows that the maximum out-degree vertex $v_{\max}$ can reach the minimum out-degree vertex $v_{\min}$ in at most two steps, bounding the degree span by $D_v - d_v \le 2$. If the degree span is at most 1, the total out-degree sum $\binom{2m}{2} = m(2m - 1)$ forces all out-degrees to be $m - 1$ or $m$, which contradicts the assumption that the tournament is not near-regular. If the degree span is 2, partitioning the vertices into the three degree classes yields tight size bounds that contradict the degree sum via an integer arithmetic identity.
In any tournament, the out-neighborhood and in-neighborhood of any vertex $x$ are disjoint.
By definition of a tournament, there are no self-loops, and between any two distinct vertices $x$ and $y$, an arc is directed in at most one direction. Hence, no vertex $y$ can simultaneously be an out-neighbor and an in-neighbor of $x$.
uses
Finset.disjoint_left,Finset.mem_filter,Finset.mem_univ,true_and,Ne.symmopen Classical in lemma tournament_not_near_regular_exists_arc_degree_gap_out_add_in {n : ℕ} (T : Digraph (Fin n)) [DecidableRel T.Adj] (hT : digraph_is_tournament T) (x : Fin n) : digraph_out_count T x + (Finset.univ.filter (fun y => T.Adj y x)).card = n - 1 := by classical unfold digraph_out_count set A := Finset.univ.filter (fun y => T.Adj x y) with hA set B := Finset.univ.filter (fun y => T.Adj y x) with hB have hdisj : Disjoint A B := by rw [Finset.disjoint_left] intro y hyA hyB simp only [hA, hB, Finset.mem_filter, Finset.mem_univ, true_and] at hyA hyB by_cases hyx : y = x · subst hyx; exact hT.1 y hyA · exact (hT.2 x y (Ne.symm hyx)).mp hyA hyB
The union of the out-neighborhood and in-neighborhood of $x$ is $V \setminus \{x\}$.
No vertex is adjacent to itself, so $x$ cannot lie in the union. For any other vertex $y \neq x$, the tournament property guarantees that either $x \to y$ or $y \to x$.
uses
Finset.mem_union,Finset.mem_filter,Finset.mem_univ,true_and,Finset.mem_erase,Or.inl,Or.inr,Ne.symmhave hunion : A ∪ B = Finset.univ.erase x := by ext y simp only [hA, hB, Finset.mem_union, Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_erase] constructor · rintro (h | h) <;> exact ⟨fun e => by subst e; exact hT.1 y h, trivial⟩ · rintro ⟨hyx, _⟩ by_cases h : T.Adj x y · exact Or.inl h · exact Or.inr (by by_contra hc; exact h ((hT.2 x y (Ne.symm hyx)).mpr hc))
For any vertex $x$ in a tournament on $n$ vertices, out-degree plus in-degree equals $n - 1$.
The out-neighborhood and in-neighborhood are disjoint finite sets whose union is $V \setminus \{x\}$, so the sum of their cardinalities equals $|V \setminus \{x\}| = n - 1$.
uses
Finset.card_union_of_disjoint,Finset.card_erase_of_mem,Finset.mem_univrw [← Finset.card_union_of_disjoint hdisj, hunion, Finset.card_erase_of_mem (Finset.mem_univ x)] simp
The difference between the counts $c$ and $a$ satisfies $(c - a) = m(2m - 3 - 2d)$ in $\mathbb{Z}$.
From $a + b + c = 2m$ and $ad + b(d+1) + c(d+2) = m(2m - 1)$, subtracting $(d+1)(a+b+c) = 2m(d+1)$ eliminates $b$, leaving $c - a$ on the left and $m(2m - 1) - 2m(d+1) = m(2m - 3 - 2d)$ on the right.
lemma tournament_not_near_regular_exists_arc_degree_gap_arith (m d a b c : ℕ) (hm : 2 ≤ m) (ha : 1 ≤ a) (hc : 1 ≤ c) (hcd : c ≤ d) (hdm : d ≤ m - 1) (had : a ≤ 2 * m - 3 - d) (hsum : a + b + c = 2 * m) (hdeg : a * d + b * (d + 1) + c * (d + 2) = m * (2 * m - 1)) : False := by have key : (c:ℤ) - (a:ℤ) = (m:ℤ) * (2*(m:ℤ) - 3 - 2*(d:ℤ)) := by have h1 : (a:ℤ) + (b:ℤ) + (c:ℤ) = 2*(m:ℤ) := by exact_mod_cast hsum have h2 : (a:ℤ)*(d:ℤ) + (b:ℤ)*((d:ℤ)+1) + (c:ℤ)*((d:ℤ)+2) = (m:ℤ)*(2*(m:ℤ)-1) := by have h2m : (2*(m:ℤ) - 1) = ((2*m - 1 : ℕ) : ℤ) := by have : 1 ≤ 2*m := by omega omega rw [h2m] exact_mod_cast hdeg nlinarith [h1, h2]
The case $d \le m - 2$ leads to a contradiction.
If $d \le m - 2$, then $2m - 3 - 2d \ge 1$, which forces $c - a = m(2m - 3 - 2d) \ge m$. Since $a \ge 1$, we get $c \ge m + a \ge m + 1$, contradicting the assumption $c \le d \le m - 1$.
uses
mul_le_mul_of_nonneg_leftby_cases hcase : d ≤ m - 2 · have hk : (1:ℤ) ≤ 2*(m:ℤ) - 3 - 2*(d:ℤ) := by have : (d:ℤ) ≤ (m:ℤ) - 2 := by have : d + 2 ≤ m := by omega omega linarith have hm0 : (0:ℤ) ≤ (m:ℤ) := by positivity have hmul : (m:ℤ) ≤ (m:ℤ) * (2*(m:ℤ) - 3 - 2*(d:ℤ)) := by calc (m:ℤ) = (m:ℤ) * 1 := by ring _ ≤ (m:ℤ) * (2*(m:ℤ) - 3 - 2*(d:ℤ)) := by apply mul_le_mul_of_nonneg_left hk hm0 have hca : (m:ℤ) ≤ (c:ℤ) - (a:ℤ) := by rw [key]; exact hmul have hc1 : (1:ℤ) ≤ (a:ℤ) := by exact_mod_cast ha have hcd' : (c:ℤ) ≤ (d:ℤ) := by exact_mod_cast hcd have hdm' : (d:ℤ) ≤ (m:ℤ) - 1 := by have : d + 1 ≤ m := by omega omega omega
The case $d = m - 1$ also leads to a contradiction.
Because $d \le m - 1$ and $d > m - 2$, we have $d = m - 1$. Substituting this into the key identity yields $c - a = -m$, so $a = c + m \ge m$. However, the hypothesis $a \le 2m - 3 - d$ simplifies to $a \le m - 2$, an impossible upper bound for $a \ge m$.
· have hd : d = m - 1 := by omega subst hd have hcm : ((m-1:ℕ):ℤ) = (m:ℤ)-1 := by have : 1 ≤ m := by omega omega have hkey2 : (c:ℤ) - (a:ℤ) = -(m:ℤ) := by rw [key, hcm]; ring have had' : (a:ℤ) ≤ (m:ℤ) - 2 := by have h : 2 * m - 3 - (m - 1) = m - 2 := by omega have := had rw [h] at this exact_mod_cast this have hc0 : (0:ℤ) ≤ (c:ℤ) := by positivity linarith
Assuming for contradiction that no arc has out-degree gap at least 2, every arc $u \to v$ satisfies $\operatorname{out}(u) \le \operatorname{out}(v) + 1$.
We assume for contradiction that there is no arc $u \to v$ with $\operatorname{out}(v) + 2 \le \operatorname{out}(u)$. By contraposition, along every arc the tail's out-degree can exceed the head's out-degree by at most 1.
/-- A non-near-regular tournament on 2m ≥ 4 vertices has an arc whose tail has out-degree exceeding the head's by at least 2. -/ theorem tournament_not_near_regular_exists_arc_degree_gap (m : ℕ) (hm : 2 ≤ m) (T : Digraph (Fin (2 * m))) [DecidableRel T.Adj] (hT : digraph_is_tournament T) (hnr : ¬ tournament_is_near_regular m T) : ∃ u v : Fin (2 * m), T.Adj u v ∧ digraph_out_count T v + 2 ≤ digraph_out_count T u := by classical by_contra hcon have hgap : ∀ u v, T.Adj u v → digraph_out_count T u ≤ digraph_out_count T v + 1 := by intro u v huv have hnv : ¬ (digraph_out_count T v + 2 ≤ digraph_out_count T u) := by intro hB; exact hcon ⟨u, v, huv, hB⟩ omega
There exist vertices $v_{\min}$ and $v_{\max}$ of minimum and maximum out-degrees $d_v$ and $D_v$, and any two distinct vertices are connected by an arc.
Since $2m \ge 4$, the vertex set is finite and nonempty, so the out-degree function attains a minimum value $d_v$ at some vertex $v_{\min}$ and a maximum value $D_v$ at $v_{\max}$. Completeness of the tournament ensures an arc between any distinct pair.
uses
Finset.exists_min_image,Finset.univ,Finset.mem_univ,Finset.exists_max_image,Or.inl,Or.inrobtain ⟨vmin, -, hvmin⟩ := Finset.exists_min_image (Finset.univ : Finset (Fin (2 * m))) (fun x => digraph_out_count T x) ⟨⟨0, by omega⟩, Finset.mem_univ _⟩ obtain ⟨vmax, -, hvmax⟩ := Finset.exists_max_image (Finset.univ : Finset (Fin (2 * m))) (fun x => digraph_out_count T x) ⟨⟨0, by omega⟩, Finset.mem_univ _⟩ set dv := digraph_out_count T vmin with hdv set Dv := digraph_out_count T vmax with hDv have hvmin' : ∀ x, dv ≤ digraph_out_count T x := fun x => hvmin x (Finset.mem_univ x) have hvmax' : ∀ x, digraph_out_count T x ≤ Dv := fun x => hvmax x (Finset.mem_univ x) have hcomplete : ∀ x y : Fin (2 * m), x ≠ y → T.Adj x y ∨ T.Adj y x := by intro x y hne by_cases h : T.Adj x y · exact Or.inl h · exact Or.inr (by by_contra h2; exact h ((hT.2 x y hne).mpr h2))
The maximum out-degree satisfies $D_v \le d_v + 2$.
If $v_{\max} = v_{\min}$, the claim is trivial. Otherwise, if $v_{\max}$ cannot reach $v_{\min}$ in 1 or 2 steps, then $v_{\min} \to v_{\max}$ and every out-neighbor of $v_{\max}$ receives an arc from $v_{\min}$. This forces $N^+(v_{\max}) \cup \{v_{\max}\} \subseteq N^+(v_{\min})$, which implies $D_v + 1 \le d_v$, contradicting $d_v \le D_v$. Therefore, a path of length at most 2 exists from $v_{\max}$ to $v_{\min}$, and the no-gap property along its arcs gives $D_v \le d_v + 2$.
uses
Finset.mem_filter,Finset.mem_univ,true_and,Ne.symm,Finset.disjoint_left,Finset.mem_singleton,Finset.mem_union.mp,Finset.card_le_card,Finset.card_union_of_disjoint,Finset.card_singletonhave hDbound : Dv ≤ dv + 2 := by by_cases hveq : vmin = vmax · have : Dv = dv := by rw [hDv, hdv, hveq] omega · suffices hreach : T.Adj vmax vmin ∨ ∃ w, T.Adj vmax w ∧ T.Adj w vmin by rcases hreach with h | ⟨w, h1, h2⟩ · have := hgap vmax vmin h; omega · have e1 := hgap vmax w h1; have e2 := hgap w vmin h2; omega by_contra hcon2 push_neg at hcon2 obtain ⟨hnotadj, hno3⟩ := hcon2 set Nmax := Finset.univ.filter (fun x => T.Adj vmax x) with hNmax_def set Nmin := Finset.univ.filter (fun x => T.Adj vmin x) with hNmin_def have hsub : Nmax ⊆ Nmin := by intro x hx rw [hNmax_def] at hx; rw [hNmin_def] simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hx ⊢ have hxne : x ≠ vmin := by intro e; subst e; exact hnotadj hx have hnotwx : ¬ T.Adj x vmin := hno3 x hx rcases hcomplete vmin x (Ne.symm hxne) with h | h · exact h · exact absurd h hnotwx have hvmaxin : vmax ∈ Nmin := by rw [hNmin_def] simp only [Finset.mem_filter, Finset.mem_univ, true_and] rcases hcomplete vmin vmax hveq with h | h · exact h · exact absurd h hnotadj have hvmaxnotin : vmax ∉ Nmax := by rw [hNmax_def]; simp only [Finset.mem_filter, Finset.mem_univ, true_and]; exact hT.1 vmax have hdisj : Disjoint Nmax {vmax} := by rw [Finset.disjoint_left]; intro x hx hx' rw [Finset.mem_singleton] at hx'; subst hx'; exact hvmaxnotin hx have hunion_sub : Nmax ∪ {vmax} ⊆ Nmin := by intro x hx rcases Finset.mem_union.mp hx with h | h · exact hsub h · rw [Finset.mem_singleton] at h; subst h; exact hvmaxin have hcardle : (Nmax ∪ {vmax}).card ≤ Nmin.card := Finset.card_le_card hunion_sub rw [Finset.card_union_of_disjoint hdisj, Finset.card_singleton] at hcardle have hNmax : Nmax.card = Dv := by rw [hNmax_def, hDv]; rfl have hNmin : Nmin.card = dv := by rw [hNmin_def, hdv]; rfl rw [hNmax, hNmin] at hcardle have := hvmin' vmax omega
The case $D_v \le d_v + 1$ implies the tournament is near-regular, a contradiction.
If all out-degrees lie in $\{d_v, d_v + 1\}$, bounding the sum of all out-degrees $m(2m - 1)$ between $(2m)d_v$ and $(2m)(d_v + 1)$ implies $2d_v \le 2m - 1 \le 2d_v + 2$. Because $2m - 1$ is odd, this uniquely forces $d_v = m - 1$, so all out-degrees are $m - 1$ or $m$. This makes the tournament near-regular, contradicting `hnr`.
uses
le_trans,tournament_sum_out_count,Finset.sum_const,Finset.card_univ,Finset.sum_le_sum,Nat.le_of_mul_le_mul_left,Or.inl,Or.inrby_cases hDle : Dv ≤ dv + 1 · have hle_all : ∀ x, digraph_out_count T x ≤ dv + 1 := fun x => le_trans (hvmax' x) hDle have hsum_out := tournament_sum_out_count (2 * m) T hT have hsum_eq : ∑ x : Fin (2 * m), digraph_out_count T x = m * (2 * m - 1) := by rw [hsum_out] have : (2 * m) * ((2 * m) - 1) = 2 * (m * (2 * m - 1)) := by ring omega have hsum_const1 : (∑ x : Fin (2 * m), (dv + 1)) = (2 * m) * (dv + 1) := by simp [Finset.sum_const, Finset.card_univ] have hsum_const0 : (∑ x : Fin (2 * m), dv) = (2 * m) * dv := by simp [Finset.sum_const, Finset.card_univ] have hle' : m * (2 * m - 1) ≤ (2 * m) * (dv + 1) := by rw [← hsum_eq, ← hsum_const1] exact Finset.sum_le_sum (fun x _ => hle_all x) have hge' : (2 * m) * dv ≤ m * (2 * m - 1) := by rw [← hsum_eq, ← hsum_const0] exact Finset.sum_le_sum (fun x _ => hvmin' x) have hdvm : dv = m - 1 := by have hmpos : 0 < m := by omega rw [show (2 * m) * (dv + 1) = m * (2 * (dv + 1)) by ring] at hle' have hle2 : 2 * m - 1 ≤ 2 * (dv + 1) := by have := Nat.le_of_mul_le_mul_left hle' hmpos; omega rw [show (2 * m) * dv = m * (2 * dv) by ring] at hge' have hge2 : 2 * dv ≤ 2 * m - 1 := Nat.le_of_mul_le_mul_left hge' hmpos omega exact hnr (fun v => by have a1 := hvmin' v have a2 := hle_all v rw [hdvm] at a1 a2 by_cases hcase : digraph_out_count T v = m - 1 · exact Or.inl hcase · exact Or.inr (by omega))
When $D_v = d_v + 2$, the vertices partition into sets $A, B, C$ of out-degrees $d_v, d_v + 1, d_v + 2$ with total degree sum $m(2m - 1)$.
Since every out-degree lies in $\{d_v, d_v + 1, d_v + 2\}$, the vertices partition into disjoint sets $A, B, C$. Sets $A$ and $C$ contain $v_{\min}$ and $v_{\max}$ respectively and are thus nonempty. Their sizes satisfy $|A| + |B| + |C| = 2m$, and summing their out-degrees matches the total out-degree sum $m(2m - 1)$.
uses
Finset.mem_filter,Finset.mem_univ,true_and,Finset.card_pos.mpr,Finset.mem_union,iff_true,Or.inl,Or.inr,Finset.disjoint_left,Finset.card_union_of_disjoint,Finset.mem_filter.mp,Finset.sum_congr,Finset.sum_const,Finset.sum_union,tournament_sum_out_count· have hDeq : Dv = dv + 2 := by omega exfalso set A : Finset (Fin (2 * m)) := Finset.univ.filter (fun x => digraph_out_count T x = dv) with hA set B : Finset (Fin (2 * m)) := Finset.univ.filter (fun x => digraph_out_count T x = dv + 1) with hB set C : Finset (Fin (2 * m)) := Finset.univ.filter (fun x => digraph_out_count T x = dv + 2) with hC have hmemA : vmin ∈ A := by rw [hA]; simp only [Finset.mem_filter, Finset.mem_univ, true_and]; exact hdv.symm have hmemC : vmax ∈ C := by rw [hC]; simp only [Finset.mem_filter, Finset.mem_univ, true_and] rw [← hDv]; exact hDeq have ha : 1 ≤ A.card := by have := Finset.card_pos.mpr ⟨vmin, hmemA⟩; omega have hc : 1 ≤ C.card := by have := Finset.card_pos.mpr ⟨vmax, hmemC⟩; omega have hmemABC : ∀ x, x ∈ A ∨ x ∈ B ∨ x ∈ C := by intro x rw [hA, hB, hC] simp only [Finset.mem_filter, Finset.mem_univ, true_and] have h1 := hvmin' x have h2 := hvmax' x omega have hABC : (A ∪ B) ∪ C = Finset.univ := by ext x simp only [Finset.mem_union, Finset.mem_univ, iff_true] rcases hmemABC x with h | h | h · exact Or.inl (Or.inl h) · exact Or.inl (Or.inr h) · exact Or.inr h have hdisjAB : Disjoint A B := by rw [Finset.disjoint_left]; intro x hx hy rw [hA] at hx; rw [hB] at hy simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hx hy omega have hdisjAB_C : Disjoint (A ∪ B) C := by rw [Finset.disjoint_left]; intro x hx hy rw [Finset.mem_union] at hx; rw [hC] at hy simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hy rw [hA] at hx; rw [hB] at hx simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hx rcases hx with hx | hx <;> omega have hcard : A.card + B.card + C.card = 2 * m := by have h1 : ((A ∪ B) ∪ C).card = A.card + B.card + C.card := by rw [Finset.card_union_of_disjoint hdisjAB_C, Finset.card_union_of_disjoint hdisjAB] rw [hABC] at h1 rw [← h1]; simp have eA : ∑ x ∈ A, digraph_out_count T x = A.card * dv := by have h : ∀ x ∈ A, digraph_out_count T x = dv := by intro x hx; rw [hA] at hx; exact (Finset.mem_filter.mp hx).2 rw [Finset.sum_congr rfl h]; simp [Finset.sum_const] have eB : ∑ x ∈ B, digraph_out_count T x = B.card * (dv + 1) := by have h : ∀ x ∈ B, digraph_out_count T x = dv + 1 := by intro x hx; rw [hB] at hx; exact (Finset.mem_filter.mp hx).2 rw [Finset.sum_congr rfl h]; simp [Finset.sum_const] have eC : ∑ x ∈ C, digraph_out_count T x = C.card * (dv + 2) := by have h : ∀ x ∈ C, digraph_out_count T x = dv + 2 := by intro x hx; rw [hC] at hx; exact (Finset.mem_filter.mp hx).2 rw [Finset.sum_congr rfl h]; simp [Finset.sum_const] have hdeg_eq : ∑ x : Fin (2 * m), digraph_out_count T x = A.card * dv + B.card * (dv + 1) + C.card * (dv + 2) := by rw [← hABC, Finset.sum_union hdisjAB_C, Finset.sum_union hdisjAB, eA, eB, eC] have hsum_out := tournament_sum_out_count (2 * m) T hT have hsum_eq : ∑ x : Fin (2 * m), digraph_out_count T x = m * (2 * m - 1) := by rw [hsum_out] have : (2 * m) * ((2 * m) - 1) = 2 * (m * (2 * m - 1)) := by ring omega have hdeg : A.card * dv + B.card * (dv + 1) + C.card * (dv + 2) = m * (2 * m - 1) := by rw [← hdeg_eq]; exact hsum_eq
The cardinalities satisfy $|C| \le d_v$, $d_v \le m - 1$, and $|A| \le 2m - 3 - d_v$, leading to a final contradiction via the arithmetic lemma.
No vertex in $C$ can send an arc to $v_{\min}$, else its out-degree gap would be $(d_v + 2) - d_v = 2$; hence $C \subseteq N^+(v_{\min})$ and $|C| \le d_v$. From $(2m)d_v \le m(2m - 1)$, we obtain $d_v \le m - 1$. Similarly, $v_{\max}$ cannot send an arc to any vertex in $A$, so $A \subseteq N^-(v_{\max})$, giving $|A| \le \operatorname{in}(v_{\max}) = 2m - 1 - D_v = 2m - 3 - d_v$. Applying the arithmetic lemma `tournament_not_near_regular_exists_arc_degree_gap_arith` to $m, d_v, |A|, |B|, |C|$ produces `False`.
uses
Finset.mem_filter,Finset.mem_univ,Finset.mem_filter.mp,Ne.symm,Finset.card_le_card,tournament_sum_out_count,Finset.sum_const,Finset.card_univ,Finset.sum_le_sum,Nat.le_of_mul_le_mul_left,tournament_not_near_regular_exists_arc_degree_gap_out_add_in,tournament_not_near_regular_exists_arc_degree_gap_arithhave hcd : C.card ≤ dv := by have hCsub : C ⊆ Finset.univ.filter (fun x => T.Adj vmin x) := by intro x hx rw [Finset.mem_filter] refine ⟨Finset.mem_univ x, ?_⟩ rw [hC] at hx have hdx : digraph_out_count T x = dv + 2 := (Finset.mem_filter.mp hx).2 have hne : x ≠ vmin := by intro hxv have hdx' := hdx rw [hxv, ← hdv] at hdx' omega rcases hcomplete vmin x (Ne.symm hne) with h | h · exact h · exfalso have hh := hgap x vmin h rw [hdx, ← hdv] at hh omega have hc_le := Finset.card_le_card hCsub have hthis : (Finset.univ.filter (fun x => T.Adj vmin x)).card = dv := by rw [hdv]; rfl rwa [hthis] at hc_le have hdm : dv ≤ m - 1 := by have hsum_eq2 : ∑ x : Fin (2 * m), digraph_out_count T x = m * (2 * m - 1) := by rw [hsum_out] have : (2 * m) * ((2 * m) - 1) = 2 * (m * (2 * m - 1)) := by ring omega have hsum_const0 : (∑ x : Fin (2 * m), dv) = (2 * m) * dv := by simp [Finset.sum_const, Finset.card_univ] have hge : (2 * m) * dv ≤ m * (2 * m - 1) := by rw [← hsum_eq2, ← hsum_const0] exact Finset.sum_le_sum (fun x _ => hvmin' x) have hmpos : 0 < m := by omega rw [show (2 * m) * dv = m * (2 * dv) by ring] at hge have := Nat.le_of_mul_le_mul_left hge hmpos omega have had : A.card ≤ 2 * m - 3 - dv := by have hAsub : A ⊆ Finset.univ.filter (fun y => T.Adj y vmax) := by intro x hx rw [Finset.mem_filter] refine ⟨Finset.mem_univ x, ?_⟩ rw [hA] at hx have hdx : digraph_out_count T x = dv := (Finset.mem_filter.mp hx).2 have hne : x ≠ vmax := by intro hxv have hdx' := hdx rw [hxv, ← hDv] at hdx' omega rcases hcomplete x vmax hne with h | h · exact h · exfalso have hh := hgap vmax x h rw [hdx, ← hDv] at hh omega have hoi := tournament_not_near_regular_exists_arc_degree_gap_out_add_in T hT vmax rw [← hDv] at hoi have hincard : (Finset.univ.filter (fun y => T.Adj y vmax)).card = 2 * m - 1 - Dv := by omega have hc_le := Finset.card_le_card hAsub rw [hincard] at hc_le omega exact tournament_not_near_regular_exists_arc_degree_gap_arith m dv A.card B.card C.card hm ha hc hcd hdm had hcard hdeg
Finset.disjoint_left- Two finite sets are disjoint if and only if no element of the first belongs to the second.
Finset.mem_filter- An element belongs to `Finset.filter p s` if and only if it is in $s$ and satisfies $p$.
Finset.mem_univ- Every element of a finite type belongs to its universal set `Finset.univ`.
true_and- `True ∧ p` is logically equivalent to `p`.
Ne.symm- Inequality is symmetric: $a \neq b$ implies $b \neq a$.
Finset.mem_union- An element belongs to $s \cup t$ if and only if it belongs to $s$ or to $t$.
Finset.mem_erase- An element $a$ belongs to $s.\text{erase } b$ if and only if $a \neq b$ and $a \in s$.
Or.inl- Constructs a proof of $A \lor B$ from a proof of $A$.
Or.inr- Constructs a proof of $A \lor B$ from a proof of $B$.
Finset.card_union_of_disjoint- If $s$ and $t$ are disjoint finite sets, then $|s \cup t| = |s| + |t|$.
Finset.card_erase_of_mem- If $a \in s$, the cardinality of $s \setminus \{a\}$ is $|s| - 1$.
mul_le_mul_of_nonneg_left- If $b \le c$ and $0 \le a$, then $a \cdot b \le a \cdot c$.
Finset.exists_min_image- A nonempty finite set contains an element minimizing a given function into a linearly ordered type.
Finset.univ- The finite set containing all terms of a finite type.
Finset.exists_max_image- A nonempty finite set contains an element maximizing a given function into a linearly ordered type.
Finset.mem_singleton- An element $b$ belongs to $\{a\}$ if and only if $b = a$.
Finset.mem_union.mp- If an element is in $s \cup t$, then it is in $s$ or in $t$.
Finset.card_le_card- If $s \subseteq t$ for finite sets, then $|s| \le |t|$.
Finset.card_singleton- The cardinality of a singleton set $\{a\}$ is 1.
le_trans- Transitivity of inequality: $a \le b$ and $b \le c$ imply $a \le c$.
tournament_sum_out_count- In any tournament on $n$ vertices, the sum of all out-degrees is $n(n - 1) / 2$.
Finset.sum_const- The sum of a constant value $b$ over a finite set $s$ is $|s| \cdot b$.
Finset.card_univ- The cardinality of `Finset.univ` for a finite type is the cardinality of that type.
Finset.sum_le_sum- If $f(i) \le g(i)$ for all $i \in s$, then $\sum_{i \in s} f(i) \le \sum_{i \in s} g(i)$.
Nat.le_of_mul_le_mul_left- If $c \cdot a \le c \cdot b$ with $c > 0$ for natural numbers, then $a \le b$.
Finset.card_pos.mpr- A finite set has positive cardinality if it is nonempty.
iff_true- The equivalence $P \leftrightarrow \text{True}$ is equivalent to $P$.
Finset.mem_filter.mp- If $a \in \text{filter } p\ s$, then $a \in s$ and $p(a)$ holds.
Finset.sum_congr- If two index sets are equal and the summands agree pointwise, their sums are equal.
Finset.sum_union- For disjoint finite sets $s_1$ and $s_2$, the sum over $s_1 \cup s_2$ is the sum over $s_1$ plus the sum over $s_2$.
tournament_not_near_regular_exists_arc_degree_gap_out_add_in- In a tournament on $n$ vertices, the out-degree and in-degree of any vertex sum to $n - 1$.
tournament_not_near_regular_exists_arc_degree_gap_arith- No natural numbers $m \ge 2, d, a \ge 1, b, c \ge 1$ can satisfy $c \le d \le m - 1$, $a \le 2m - 3 - d$, $a + b + c = 2m$, and $ad + b(d+1) + c(d+2) = m(2m - 1)$.
- The arithmetic contradiction in Lemma `tournament_not_near_regular_exists_arc_degree_gap_arith` is verified by embedding the natural degree equations into ℤ, eliminating the middle degree class via `nlinarith`, and using `omega` and `linarith` on the two cases $d \le m - 2$ and $d = m - 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
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.
open Classical inlemma tournament_not_near_regular_exists_arc_degree_gap_out_add_in {n : ℕ} (T : Digraph (Fin n)) [DecidableRel T.Adj] (hT : digraph_is_tournament T) (x : Fin n) : digraph_out_count T x + (Finset.univ.filter (fun y => T.Adj y x)).card = n - 1 := by classical unfold digraph_out_count set A := Finset.univ.filter (fun y => T.Adj x y) with hA set B := Finset.univ.filter (fun y => T.Adj y x) with hB have hdisj : Disjoint A B := by rw [Finset.disjoint_left] intro y hyA hyB simp only [hA, hB, Finset.mem_filter, Finset.mem_univ, true_and] at hyA hyB by_cases hyx : y = x · subst hyx; exact hT.1 y hyA · exact (hT.2 x y (Ne.symm hyx)).mp hyA hyB have hunion : A ∪ B = Finset.univ.erase x := by ext y simp only [hA, hB, Finset.mem_union, Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_erase] constructor · rintro (h | h) <;> exact ⟨fun e => by subst e; exact hT.1 y h, trivial⟩ · rintro ⟨hyx, _⟩ by_cases h : T.Adj x y · exact Or.inl h · exact Or.inr (by by_contra hc; exact h ((hT.2 x y (Ne.symm hyx)).mpr hc)) rw [← Finset.card_union_of_disjoint hdisj, hunion, Finset.card_erase_of_mem (Finset.mem_univ x)] simplemma tournament_not_near_regular_exists_arc_degree_gap_arith (m d a b c : ℕ) (hm : 2 ≤ m) (ha : 1 ≤ a) (hc : 1 ≤ c) (hcd : c ≤ d) (hdm : d ≤ m - 1) (had : a ≤ 2 * m - 3 - d) (hsum : a + b + c = 2 * m) (hdeg : a * d + b * (d + 1) + c * (d + 2) = m * (2 * m - 1)) : False := by have key : (c:ℤ) - (a:ℤ) = (m:ℤ) * (2*(m:ℤ) - 3 - 2*(d:ℤ)) := by have h1 : (a:ℤ) + (b:ℤ) + (c:ℤ) = 2*(m:ℤ) := by exact_mod_cast hsum have h2 : (a:ℤ)*(d:ℤ) + (b:ℤ)*((d:ℤ)+1) + (c:ℤ)*((d:ℤ)+2) = (m:ℤ)*(2*(m:ℤ)-1) := by have h2m : (2*(m:ℤ) - 1) = ((2*m - 1 : ℕ) : ℤ) := by have : 1 ≤ 2*m := by omega omega rw [h2m] exact_mod_cast hdeg nlinarith [h1, h2] by_cases hcase : d ≤ m - 2 · have hk : (1:ℤ) ≤ 2*(m:ℤ) - 3 - 2*(d:ℤ) := by have : (d:ℤ) ≤ (m:ℤ) - 2 := by have : d + 2 ≤ m := by omega omega linarith have hm0 : (0:ℤ) ≤ (m:ℤ) := by positivity have hmul : (m:ℤ) ≤ (m:ℤ) * (2*(m:ℤ) - 3 - 2*(d:ℤ)) := by calc (m:ℤ) = (m:ℤ) * 1 := by ring _ ≤ (m:ℤ) * (2*(m:ℤ) - 3 - 2*(d:ℤ)) := by apply mul_le_mul_of_nonneg_left hk hm0 have hca : (m:ℤ) ≤ (c:ℤ) - (a:ℤ) := by rw [key]; exact hmul have hc1 : (1:ℤ) ≤ (a:ℤ) := by exact_mod_cast ha have hcd' : (c:ℤ) ≤ (d:ℤ) := by exact_mod_cast hcd have hdm' : (d:ℤ) ≤ (m:ℤ) - 1 := by have : d + 1 ≤ m := by omega omega omega · have hd : d = m - 1 := by omega subst hd have hcm : ((m-1:ℕ):ℤ) = (m:ℤ)-1 := by have : 1 ≤ m := by omega omega have hkey2 : (c:ℤ) - (a:ℤ) = -(m:ℤ) := by rw [key, hcm]; ring have had' : (a:ℤ) ≤ (m:ℤ) - 2 := by have h : 2 * m - 3 - (m - 1) = m - 2 := by omega have := had rw [h] at this exact_mod_cast this have hc0 : (0:ℤ) ≤ (c:ℤ) := by positivity linarith/-- A non-near-regular tournament on 2m ≥ 4 vertices has an arc whose tail has out-degree exceeding the head's by at least 2. -/theorem tournament_not_near_regular_exists_arc_degree_gap (m : ℕ) (hm : 2 ≤ m) (T : Digraph (Fin (2 * m))) [DecidableRel T.Adj] (hT : digraph_is_tournament T) (hnr : ¬ tournament_is_near_regular m T) : ∃ u v : Fin (2 * m), T.Adj u v ∧ digraph_out_count T v + 2 ≤ digraph_out_count T u := by classical by_contra hcon have hgap : ∀ u v, T.Adj u v → digraph_out_count T u ≤ digraph_out_count T v + 1 := by intro u v huv have hnv : ¬ (digraph_out_count T v + 2 ≤ digraph_out_count T u) := by intro hB; exact hcon ⟨u, v, huv, hB⟩ omega obtain ⟨vmin, -, hvmin⟩ := Finset.exists_min_image (Finset.univ : Finset (Fin (2 * m))) (fun x => digraph_out_count T x) ⟨⟨0, by omega⟩, Finset.mem_univ _⟩ obtain ⟨vmax, -, hvmax⟩ := Finset.exists_max_image (Finset.univ : Finset (Fin (2 * m))) (fun x => digraph_out_count T x) ⟨⟨0, by omega⟩, Finset.mem_univ _⟩ set dv := digraph_out_count T vmin with hdv set Dv := digraph_out_count T vmax with hDv have hvmin' : ∀ x, dv ≤ digraph_out_count T x := fun x => hvmin x (Finset.mem_univ x) have hvmax' : ∀ x, digraph_out_count T x ≤ Dv := fun x => hvmax x (Finset.mem_univ x) have hcomplete : ∀ x y : Fin (2 * m), x ≠ y → T.Adj x y ∨ T.Adj y x := by intro x y hne by_cases h : T.Adj x y · exact Or.inl h · exact Or.inr (by by_contra h2; exact h ((hT.2 x y hne).mpr h2)) have hDbound : Dv ≤ dv + 2 := by by_cases hveq : vmin = vmax · have : Dv = dv := by rw [hDv, hdv, hveq] omega · suffices hreach : T.Adj vmax vmin ∨ ∃ w, T.Adj vmax w ∧ T.Adj w vmin by rcases hreach with h | ⟨w, h1, h2⟩ · have := hgap vmax vmin h; omega · have e1 := hgap vmax w h1; have e2 := hgap w vmin h2; omega by_contra hcon2 push_neg at hcon2 obtain ⟨hnotadj, hno3⟩ := hcon2 set Nmax := Finset.univ.filter (fun x => T.Adj vmax x) with hNmax_def set Nmin := Finset.univ.filter (fun x => T.Adj vmin x) with hNmin_def have hsub : Nmax ⊆ Nmin := by intro x hx rw [hNmax_def] at hx; rw [hNmin_def] simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hx ⊢ have hxne : x ≠ vmin := by intro e; subst e; exact hnotadj hx have hnotwx : ¬ T.Adj x vmin := hno3 x hx rcases hcomplete vmin x (Ne.symm hxne) with h | h · exact h · exact absurd h hnotwx have hvmaxin : vmax ∈ Nmin := by rw [hNmin_def] simp only [Finset.mem_filter, Finset.mem_univ, true_and] rcases hcomplete vmin vmax hveq with h | h · exact h · exact absurd h hnotadj have hvmaxnotin : vmax ∉ Nmax := by rw [hNmax_def]; simp only [Finset.mem_filter, Finset.mem_univ, true_and]; exact hT.1 vmax have hdisj : Disjoint Nmax {vmax} := by rw [Finset.disjoint_left]; intro x hx hx' rw [Finset.mem_singleton] at hx'; subst hx'; exact hvmaxnotin hx have hunion_sub : Nmax ∪ {vmax} ⊆ Nmin := by intro x hx rcases Finset.mem_union.mp hx with h | h · exact hsub h · rw [Finset.mem_singleton] at h; subst h; exact hvmaxin have hcardle : (Nmax ∪ {vmax}).card ≤ Nmin.card := Finset.card_le_card hunion_sub rw [Finset.card_union_of_disjoint hdisj, Finset.card_singleton] at hcardle have hNmax : Nmax.card = Dv := by rw [hNmax_def, hDv]; rfl have hNmin : Nmin.card = dv := by rw [hNmin_def, hdv]; rfl rw [hNmax, hNmin] at hcardle have := hvmin' vmax omega by_cases hDle : Dv ≤ dv + 1 · have hle_all : ∀ x, digraph_out_count T x ≤ dv + 1 := fun x => le_trans (hvmax' x) hDle have hsum_out := tournament_sum_out_count (2 * m) T hT have hsum_eq : ∑ x : Fin (2 * m), digraph_out_count T x = m * (2 * m - 1) := by rw [hsum_out] have : (2 * m) * ((2 * m) - 1) = 2 * (m * (2 * m - 1)) := by ring omega have hsum_const1 : (∑ x : Fin (2 * m), (dv + 1)) = (2 * m) * (dv + 1) := by simp [Finset.sum_const, Finset.card_univ] have hsum_const0 : (∑ x : Fin (2 * m), dv) = (2 * m) * dv := by simp [Finset.sum_const, Finset.card_univ] have hle' : m * (2 * m - 1) ≤ (2 * m) * (dv + 1) := by rw [← hsum_eq, ← hsum_const1] exact Finset.sum_le_sum (fun x _ => hle_all x) have hge' : (2 * m) * dv ≤ m * (2 * m - 1) := by rw [← hsum_eq, ← hsum_const0] exact Finset.sum_le_sum (fun x _ => hvmin' x) have hdvm : dv = m - 1 := by have hmpos : 0 < m := by omega rw [show (2 * m) * (dv + 1) = m * (2 * (dv + 1)) by ring] at hle' have hle2 : 2 * m - 1 ≤ 2 * (dv + 1) := by have := Nat.le_of_mul_le_mul_left hle' hmpos; omega rw [show (2 * m) * dv = m * (2 * dv) by ring] at hge' have hge2 : 2 * dv ≤ 2 * m - 1 := Nat.le_of_mul_le_mul_left hge' hmpos omega exact hnr (fun v => by have a1 := hvmin' v have a2 := hle_all v rw [hdvm] at a1 a2 by_cases hcase : digraph_out_count T v = m - 1 · exact Or.inl hcase · exact Or.inr (by omega)) · have hDeq : Dv = dv + 2 := by omega exfalso set A : Finset (Fin (2 * m)) := Finset.univ.filter (fun x => digraph_out_count T x = dv) with hA set B : Finset (Fin (2 * m)) := Finset.univ.filter (fun x => digraph_out_count T x = dv + 1) with hB set C : Finset (Fin (2 * m)) := Finset.univ.filter (fun x => digraph_out_count T x = dv + 2) with hC have hmemA : vmin ∈ A := by rw [hA]; simp only [Finset.mem_filter, Finset.mem_univ, true_and]; exact hdv.symm have hmemC : vmax ∈ C := by rw [hC]; simp only [Finset.mem_filter, Finset.mem_univ, true_and] rw [← hDv]; exact hDeq have ha : 1 ≤ A.card := by have := Finset.card_pos.mpr ⟨vmin, hmemA⟩; omega have hc : 1 ≤ C.card := by have := Finset.card_pos.mpr ⟨vmax, hmemC⟩; omega have hmemABC : ∀ x, x ∈ A ∨ x ∈ B ∨ x ∈ C := by intro x rw [hA, hB, hC] simp only [Finset.mem_filter, Finset.mem_univ, true_and] have h1 := hvmin' x have h2 := hvmax' x omega have hABC : (A ∪ B) ∪ C = Finset.univ := by ext x simp only [Finset.mem_union, Finset.mem_univ, iff_true] rcases hmemABC x with h | h | h · exact Or.inl (Or.inl h) · exact Or.inl (Or.inr h) · exact Or.inr h have hdisjAB : Disjoint A B := by rw [Finset.disjoint_left]; intro x hx hy rw [hA] at hx; rw [hB] at hy simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hx hy omega have hdisjAB_C : Disjoint (A ∪ B) C := by rw [Finset.disjoint_left]; intro x hx hy rw [Finset.mem_union] at hx; rw [hC] at hy simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hy rw [hA] at hx; rw [hB] at hx simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hx rcases hx with hx | hx <;> omega have hcard : A.card + B.card + C.card = 2 * m := by have h1 : ((A ∪ B) ∪ C).card = A.card + B.card + C.card := by rw [Finset.card_union_of_disjoint hdisjAB_C, Finset.card_union_of_disjoint hdisjAB] rw [hABC] at h1 rw [← h1]; simp have eA : ∑ x ∈ A, digraph_out_count T x = A.card * dv := by have h : ∀ x ∈ A, digraph_out_count T x = dv := by intro x hx; rw [hA] at hx; exact (Finset.mem_filter.mp hx).2 rw [Finset.sum_congr rfl h]; simp [Finset.sum_const] have eB : ∑ x ∈ B, digraph_out_count T x = B.card * (dv + 1) := by have h : ∀ x ∈ B, digraph_out_count T x = dv + 1 := by intro x hx; rw [hB] at hx; exact (Finset.mem_filter.mp hx).2 rw [Finset.sum_congr rfl h]; simp [Finset.sum_const] have eC : ∑ x ∈ C, digraph_out_count T x = C.card * (dv + 2) := by have h : ∀ x ∈ C, digraph_out_count T x = dv + 2 := by intro x hx; rw [hC] at hx; exact (Finset.mem_filter.mp hx).2 rw [Finset.sum_congr rfl h]; simp [Finset.sum_const] have hdeg_eq : ∑ x : Fin (2 * m), digraph_out_count T x = A.card * dv + B.card * (dv + 1) + C.card * (dv + 2) := by rw [← hABC, Finset.sum_union hdisjAB_C, Finset.sum_union hdisjAB, eA, eB, eC] have hsum_out := tournament_sum_out_count (2 * m) T hT have hsum_eq : ∑ x : Fin (2 * m), digraph_out_count T x = m * (2 * m - 1) := by rw [hsum_out] have : (2 * m) * ((2 * m) - 1) = 2 * (m * (2 * m - 1)) := by ring omega have hdeg : A.card * dv + B.card * (dv + 1) + C.card * (dv + 2) = m * (2 * m - 1) := by rw [← hdeg_eq]; exact hsum_eq have hcd : C.card ≤ dv := by have hCsub : C ⊆ Finset.univ.filter (fun x => T.Adj vmin x) := by intro x hx rw [Finset.mem_filter] refine ⟨Finset.mem_univ x, ?_⟩ rw [hC] at hx have hdx : digraph_out_count T x = dv + 2 := (Finset.mem_filter.mp hx).2 have hne : x ≠ vmin := by intro hxv have hdx' := hdx rw [hxv, ← hdv] at hdx' omega rcases hcomplete vmin x (Ne.symm hne) with h | h · exact h · exfalso have hh := hgap x vmin h rw [hdx, ← hdv] at hh omega have hc_le := Finset.card_le_card hCsub have hthis : (Finset.univ.filter (fun x => T.Adj vmin x)).card = dv := by rw [hdv]; rfl rwa [hthis] at hc_le have hdm : dv ≤ m - 1 := by have hsum_eq2 : ∑ x : Fin (2 * m), digraph_out_count T x = m * (2 * m - 1) := by rw [hsum_out] have : (2 * m) * ((2 * m) - 1) = 2 * (m * (2 * m - 1)) := by ring omega have hsum_const0 : (∑ x : Fin (2 * m), dv) = (2 * m) * dv := by simp [Finset.sum_const, Finset.card_univ] have hge : (2 * m) * dv ≤ m * (2 * m - 1) := by rw [← hsum_eq2, ← hsum_const0] exact Finset.sum_le_sum (fun x _ => hvmin' x) have hmpos : 0 < m := by omega rw [show (2 * m) * dv = m * (2 * dv) by ring] at hge have := Nat.le_of_mul_le_mul_left hge hmpos omega have had : A.card ≤ 2 * m - 3 - dv := by have hAsub : A ⊆ Finset.univ.filter (fun y => T.Adj y vmax) := by intro x hx rw [Finset.mem_filter] refine ⟨Finset.mem_univ x, ?_⟩ rw [hA] at hx have hdx : digraph_out_count T x = dv := (Finset.mem_filter.mp hx).2 have hne : x ≠ vmax := by intro hxv have hdx' := hdx rw [hxv, ← hDv] at hdx' omega rcases hcomplete x vmax hne with h | h · exact h · exfalso have hh := hgap vmax x h rw [hdx, ← hDv] at hh omega have hoi := tournament_not_near_regular_exists_arc_degree_gap_out_add_in T hT vmax rw [← hDv] at hoi have hincard : (Finset.univ.filter (fun y => T.Adj y vmax)).card = 2 * m - 1 - Dv := by omega have hc_le := Finset.card_le_card hAsub rw [hincard] at hc_le omega exact tournament_not_near_regular_exists_arc_degree_gap_arith m dv A.card B.card C.card hm ha hc hcd hdm had hcard hdeg