AFTD Auto-Formalizing Theoretical Domains

tournament_not_near_regular_exists_arc_degree_gap

theoremverified

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
Used by 1

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.

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

    lines 1–15

    uses Finset.disjoint_left, Finset.mem_filter, Finset.mem_univ, true_and, Ne.symm

    open 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
  2. 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$.

    lines 16–25

    uses Finset.mem_union, Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_erase, Or.inl, Or.inr, Ne.symm

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

    lines 26–28

    uses Finset.card_union_of_disjoint, Finset.card_erase_of_mem, Finset.mem_univ

      rw [← Finset.card_union_of_disjoint hdisj, hunion, Finset.card_erase_of_mem (Finset.mem_univ x)]
      simp
    
  4. 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.

    lines 29–42

    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]
  5. 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$.

    lines 43–60

    uses mul_le_mul_of_nonneg_left

      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
  6. 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$.

    lines 61–75

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

    lines 76–87

    /-- 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
  8. 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.

    lines 88–100

    uses Finset.exists_min_image, Finset.univ, Finset.mem_univ, Finset.exists_max_image, Or.inl, Or.inr

      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))
  9. 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$.

    lines 101–145

    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_singleton

      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
  10. 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`.

    lines 146–177

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

      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))
  11. 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)$.

    lines 178–244

    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
  12. 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`.

    lines 245–305

    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_arith

        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
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)$.

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

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