tournament_four_not_near_regular_exists_improving
The m = 2 case of the target, settled by finite computation: a non-near-regular tournament on 4 vertices has at most 9 arborescences while a near-regular one has 10.
Statement
theorem tournament_four_not_near_regular_exists_improving (T : Digraph (Fin 4)) [DecidableRel T.Adj]
(hT : digraph_is_tournament T) (hnr : ¬ tournament_is_near_regular 2 T) :
∃ (T' : Digraph (Fin 4)) (_ : DecidableRel T'.Adj),
digraph_is_tournament T' ∧ digraph_arborescence_count T < digraph_arborescence_count T'- Source
- step towards tournament_not_near_regular_exists_improving_tournament
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- tournament_not_near_regular_exists_arc_degree_gapIn 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…
- tournament_reverse_arc_is_tournamentIf T is a tournament with an arc u → v, reversing that arc gives another tournament.
- digraph_reverse_arcThe digraph obtained from D by reversing the arc between u and v: the two vertices exchange which of them points to the other, and every…
- tournament_is_near_regularA tournament on 2m vertices is near-regular if every vertex has out-degree m - 1 or m.
- digraph_is_tournamentA digraph is a tournament when it has no loops and between any two distinct vertices there is exactly one arc.
- digraph_arborescence_counttau(D): the total number of arborescences of D, the sum of a_r(D) over all roots r.
The proof, explained
The theorem is proved by finite exhaustive computation. Every tournament on 4 vertices is determined by 6 boolean choices orienting its edges, giving $2^6 = 64$ possible configurations. An exhaustive check with `decide` verifies that any non-near-regular tournament on 4 vertices has at most 9 arborescences. An explicit tournament $T'$ (encoded by `b_max`) is verified to have 10 arborescences, which strictly exceeds the count for any non-near-regular tournament.
The adjacency relation on boolean-encoded graphs, the tournament property, and near-regularity for tournaments on 4 vertices are decidable.
Typeclass instances for `DecidableRel` and `Decidable` are registered by unfolding the respective definitions (`tournament_four_not_near_regular_exists_improving_T_of_bools`, `digraph_is_tournament`, and `tournament_is_near_regular`) and inferring decidability from finite quantification and boolean operations.
private instance (b : Fin 6 → Bool) : DecidableRel (tournament_four_not_near_regular_exists_improving_T_of_bools b).Adj := by intro i j; dsimp [tournament_four_not_near_regular_exists_improving_T_of_bools]; infer_instance private instance tournament_four_not_near_regular_exists_improving_dec_tourn (V : Type*) [Fintype V] [DecidableEq V] (D : Digraph V) [DecidableRel D.Adj] : Decidable (digraph_is_tournament D) := by dsimp [digraph_is_tournament]; infer_instance private instance tournament_four_not_near_regular_exists_improving_dec_nr (m : ℕ) (D : Digraph (Fin (2 * m))) [DecidableRel D.Adj] : Decidable (tournament_is_near_regular m D) := by dsimp [tournament_is_near_regular]; infer_instance
Every tournament on 4 vertices encoded by 6 booleans that is not near-regular has at most 9 arborescences. automation
The claim is proven by `decide`, which evaluates all $2^6 = 64$ boolean assignments, checking near-regularity (whether every out-degree is in $\{1, 2\}$) and computing the arborescence count for each instance to confirm the bound.
uses
tournament_four_not_near_regular_exists_improving_check_boolsprivate theorem tournament_four_not_near_regular_exists_improving_check_bools : ∀ b : Fin 6 → Bool, ¬ tournament_is_near_regular 2 (tournament_four_not_near_regular_exists_improving_T_of_bools b) → digraph_arborescence_count (tournament_four_not_near_regular_exists_improving_T_of_bools b) ≤ 9 := by decide
The explicit boolean assignment `b_max` defines a tournament with exactly 10 arborescences. automation
The `decide` tactic checks that the graph defined by `b_max` satisfies the tournament axioms and counts its arborescences, confirming the total is 10.
uses
tournament_four_not_near_regular_exists_improving_b_max_tourn,tournament_four_not_near_regular_exists_improving_b_max_countprivate theorem tournament_four_not_near_regular_exists_improving_b_max_tourn : digraph_is_tournament (tournament_four_not_near_regular_exists_improving_T_of_bools tournament_four_not_near_regular_exists_improving_b_max) := by decide private theorem tournament_four_not_near_regular_exists_improving_b_max_count : digraph_arborescence_count (tournament_four_not_near_regular_exists_improving_T_of_bools tournament_four_not_near_regular_exists_improving_b_max) = 10 := by decide
Any tournament on 4 vertices is identical to the one reconstructed from its 6 edge-direction booleans.
By propositional extensionality (`propext`) and function extensionality, it suffices to show that for every pair of vertices $(i, j) \in \{0, 1, 2, 3\}^2$, adjacency in $T$ matches the boolean definition. The proof performs a case analysis over all 16 pairs using `interval_cases`: diagonal entries are false by the irreflexivity of tournaments (`h_loop`), while off-diagonal entries match the boolean encoding directly (when $i < j$) or by tournament antisymmetry (`h_tourn`, when $i > j$).
uses
propext,tournament_four_not_near_regular_exists_improving_T_eq_T_of_boolsprivate theorem tournament_four_not_near_regular_exists_improving_T_eq_T_of_bools (T : Digraph (Fin 4)) [DecidableRel T.Adj] (hT : digraph_is_tournament T) : T = tournament_four_not_near_regular_exists_improving_T_of_bools (tournament_four_not_near_regular_exists_improving_bools_of_T T) := by cases T with | mk Adj => dsimp [tournament_four_not_near_regular_exists_improving_T_of_bools] congr funext ⟨i, hi⟩ ⟨j, hj⟩ apply propext obtain ⟨h_loop, h_tourn⟩ := hT dsimp at h_loop h_tourn interval_cases i <;> interval_cases j · change Adj 0 0 ↔ tournament_four_not_near_regular_exists_improving_bit_of_fn (tournament_four_not_near_regular_exists_improving_bools_of_T { Adj := Adj }) 0 0 = true dsimp [tournament_four_not_near_regular_exists_improving_bit_of_fn]; simp [h_loop 0] · change Adj 0 1 ↔ tournament_four_not_near_regular_exists_improving_bit_of_fn (tournament_four_not_near_regular_exists_improving_bools_of_T { Adj := Adj }) 0 1 = true dsimp [tournament_four_not_near_regular_exists_improving_bit_of_fn, tournament_four_not_near_regular_exists_improving_bools_of_T]; simp · change Adj 0 2 ↔ tournament_four_not_near_regular_exists_improving_bit_of_fn (tournament_four_not_near_regular_exists_improving_bools_of_T { Adj := Adj }) 0 2 = true dsimp [tournament_four_not_near_regular_exists_improving_bit_of_fn, tournament_four_not_near_regular_exists_improving_bools_of_T]; simp · change Adj 0 3 ↔ tournament_four_not_near_regular_exists_improving_bit_of_fn (tournament_four_not_near_regular_exists_improving_bools_of_T { Adj := Adj }) 0 3 = true dsimp [tournament_four_not_near_regular_exists_improving_bit_of_fn, tournament_four_not_near_regular_exists_improving_bools_of_T]; simp · change Adj 1 0 ↔ tournament_four_not_near_regular_exists_improving_bit_of_fn (tournament_four_not_near_regular_exists_improving_bools_of_T { Adj := Adj }) 1 0 = true rw [h_tourn 1 0 (by decide)]; dsimp [tournament_four_not_near_regular_exists_improving_bit_of_fn, tournament_four_not_near_regular_exists_improving_bools_of_T]; simp · change Adj 1 1 ↔ tournament_four_not_near_regular_exists_improving_bit_of_fn (tournament_four_not_near_regular_exists_improving_bools_of_T { Adj := Adj }) 1 1 = true dsimp [tournament_four_not_near_regular_exists_improving_bit_of_fn]; simp [h_loop 1] · change Adj 1 2 ↔ tournament_four_not_near_regular_exists_improving_bit_of_fn (tournament_four_not_near_regular_exists_improving_bools_of_T { Adj := Adj }) 1 2 = true dsimp [tournament_four_not_near_regular_exists_improving_bit_of_fn, tournament_four_not_near_regular_exists_improving_bools_of_T]; simp · change Adj 1 3 ↔ tournament_four_not_near_regular_exists_improving_bit_of_fn (tournament_four_not_near_regular_exists_improving_bools_of_T { Adj := Adj }) 1 3 = true dsimp [tournament_four_not_near_regular_exists_improving_bit_of_fn, tournament_four_not_near_regular_exists_improving_bools_of_T]; simp · change Adj 2 0 ↔ tournament_four_not_near_regular_exists_improving_bit_of_fn (tournament_four_not_near_regular_exists_improving_bools_of_T { Adj := Adj }) 2 0 = true rw [h_tourn 2 0 (by decide)]; dsimp [tournament_four_not_near_regular_exists_improving_bit_of_fn, tournament_four_not_near_regular_exists_improving_bools_of_T]; simp · change Adj 2 1 ↔ tournament_four_not_near_regular_exists_improving_bit_of_fn (tournament_four_not_near_regular_exists_improving_bools_of_T { Adj := Adj }) 2 1 = true rw [h_tourn 2 1 (by decide)]; dsimp [tournament_four_not_near_regular_exists_improving_bit_of_fn, tournament_four_not_near_regular_exists_improving_bools_of_T]; simp · change Adj 2 2 ↔ tournament_four_not_near_regular_exists_improving_bit_of_fn (tournament_four_not_near_regular_exists_improving_bools_of_T { Adj := Adj }) 2 2 = true dsimp [tournament_four_not_near_regular_exists_improving_bit_of_fn]; simp [h_loop 2] · change Adj 2 3 ↔ tournament_four_not_near_regular_exists_improving_bit_of_fn (tournament_four_not_near_regular_exists_improving_bools_of_T { Adj := Adj }) 2 3 = true dsimp [tournament_four_not_near_regular_exists_improving_bit_of_fn, tournament_four_not_near_regular_exists_improving_bools_of_T]; simp · change Adj 3 0 ↔ tournament_four_not_near_regular_exists_improving_bit_of_fn (tournament_four_not_near_regular_exists_improving_bools_of_T { Adj := Adj }) 3 0 = true rw [h_tourn 3 0 (by decide)]; dsimp [tournament_four_not_near_regular_exists_improving_bit_of_fn, tournament_four_not_near_regular_exists_improving_bools_of_T]; simp · change Adj 3 1 ↔ tournament_four_not_near_regular_exists_improving_bit_of_fn (tournament_four_not_near_regular_exists_improving_bools_of_T { Adj := Adj }) 3 1 = true rw [h_tourn 3 1 (by decide)]; dsimp [tournament_four_not_near_regular_exists_improving_bit_of_fn, tournament_four_not_near_regular_exists_improving_bools_of_T]; simp · change Adj 3 2 ↔ tournament_four_not_near_regular_exists_improving_bit_of_fn (tournament_four_not_near_regular_exists_improving_bools_of_T { Adj := Adj }) 3 2 = true rw [h_tourn 3 2 (by decide)]; dsimp [tournament_four_not_near_regular_exists_improving_bit_of_fn, tournament_four_not_near_regular_exists_improving_bools_of_T]; simp · change Adj 3 3 ↔ tournament_four_not_near_regular_exists_improving_bit_of_fn (tournament_four_not_near_regular_exists_improving_bools_of_T { Adj := Adj }) 3 3 = true dsimp [tournament_four_not_near_regular_exists_improving_bit_of_fn]; simp [h_loop 3]
To show that $T$ is improved by some tournament, it suffices to show that $T$ has strictly fewer than 10 arborescences, using the candidate `b_max`.
We instantiate the existential quantifier with the tournament constructed from `b_max` and provide the proof that it is a tournament (`tournament_four_not_near_regular_exists_improving_b_max_tourn`). Rewriting with `tournament_four_not_near_regular_exists_improving_b_max_count` simplifies the required arborescence inequality to `digraph_arborescence_count T < 10`.
uses
tournament_four_not_near_regular_exists_improving_b_max_tourn,tournament_four_not_near_regular_exists_improving_b_max_countuse tournament_four_not_near_regular_exists_improving_T_of_bools tournament_four_not_near_regular_exists_improving_b_max use inferInstance refine ⟨tournament_four_not_near_regular_exists_improving_b_max_tourn, ?_⟩ rw [tournament_four_not_near_regular_exists_improving_b_max_count]
The boolean representation $b$ of $T$ yields a tournament that is not near-regular.
Using `tournament_four_not_near_regular_exists_improving_T_eq_T_of_bools`, we write $T$ as `T_of_bools b` where $b$ is the 6-bit encoding of $T$. Since $T$ is not near-regular, substituting $T = \text{T\_of\_bools } b$ proves that `T_of_bools b` is also not near-regular.
uses
tournament_four_not_near_regular_exists_improving_T_eq_T_of_boolshave hT_eq := tournament_four_not_near_regular_exists_improving_T_eq_T_of_bools T hT generalize hb : tournament_four_not_near_regular_exists_improving_bools_of_T T = b at hT_eq ⊢ have hnr' : ¬ tournament_is_near_regular 2 (tournament_four_not_near_regular_exists_improving_T_of_bools b) := by intro h apply hnr have h_eq : tournament_is_near_regular 2 T ↔ tournament_is_near_regular 2 (tournament_four_not_near_regular_exists_improving_T_of_bools b) := by subst hT_eq congr! rwa [h_eq]
The arborescence count of $T$ is strictly less than 10, completing the proof.
Applying `tournament_four_not_near_regular_exists_improving_check_bools` to $b$ shows that `T_of_bools b` has at most 9 arborescences, and substituting $T = \text{T\_of\_bools } b$ gives $\text{digraph\_arborescence\_count } T \le 9$. Linear integer arithmetic (`omega`) completes the proof by deducing $\text{digraph\_arborescence\_count } T < 10$.
uses
tournament_four_not_near_regular_exists_improving_check_boolshave hle9 := tournament_four_not_near_regular_exists_improving_check_bools b hnr' have h_count_eq : digraph_arborescence_count T = digraph_arborescence_count (tournament_four_not_near_regular_exists_improving_T_of_bools b) := by subst hT_eq congr omega
propext- Two propositions are equal if and only if they are logically equivalent.
tournament_four_not_near_regular_exists_improving_b_max_tourn- The directed graph on 4 vertices defined by the boolean assignment `b_max` satisfies the tournament axioms (no self-loops and exactly one directed edge between any two distinct vertices).
tournament_four_not_near_regular_exists_improving_b_max_count- The tournament on 4 vertices defined by `b_max` has exactly 10 arborescences.
tournament_four_not_near_regular_exists_improving_T_eq_T_of_bools- Any tournament on 4 vertices is equal to the boolean-encoded tournament reconstructed from its 6 edge orientations.
tournament_four_not_near_regular_exists_improving_check_bools- For any 6-bit boolean encoding, if the resulting 4-vertex tournament is not near-regular, then it has at most 9 arborescences.
- The upper bound of 9 arborescences for all 64 boolean configurations, as well as the tournament property and arborescence count of the candidate `b_max`, are established entirely through computational evaluation using the `decide` tactic.
- The representation lemma `tournament_four_not_near_regular_exists_improving_T_eq_T_of_bools` bridges the abstract `Digraph (Fin 4)` representation with the concrete 6-bit boolean vector representation via an exhaustive 16-case expansion over all vertex pairs.
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.
private def tournament_four_not_near_regular_exists_improving_bit_of_fn (b : Fin 6 → Bool) (i j : Fin 4) : Bool := match i, j with | 0, 1 => b 0 | 0, 2 => b 1 | 0, 3 => b 2 | 1, 2 => b 3 | 1, 3 => b 4 | 2, 3 => b 5 | 1, 0 => !b 0 | 2, 0 => !b 1 | 3, 0 => !b 2 | 2, 1 => !b 3 | 3, 1 => !b 4 | 3, 2 => !b 5 | _, _ => falseprivate def tournament_four_not_near_regular_exists_improving_T_of_bools (b : Fin 6 → Bool) : Digraph (Fin 4) where Adj i j := tournament_four_not_near_regular_exists_improving_bit_of_fn b i j = trueprivate instance (b : Fin 6 → Bool) : DecidableRel (tournament_four_not_near_regular_exists_improving_T_of_bools b).Adj := by intro i j; dsimp [tournament_four_not_near_regular_exists_improving_T_of_bools]; infer_instanceprivate instance tournament_four_not_near_regular_exists_improving_dec_tourn (V : Type*) [Fintype V] [DecidableEq V] (D : Digraph V) [DecidableRel D.Adj] : Decidable (digraph_is_tournament D) := by dsimp [digraph_is_tournament]; infer_instanceprivate instance tournament_four_not_near_regular_exists_improving_dec_nr (m : ℕ) (D : Digraph (Fin (2 * m))) [DecidableRel D.Adj] : Decidable (tournament_is_near_regular m D) := by dsimp [tournament_is_near_regular]; infer_instanceprivate theorem tournament_four_not_near_regular_exists_improving_check_bools : ∀ b : Fin 6 → Bool, ¬ tournament_is_near_regular 2 (tournament_four_not_near_regular_exists_improving_T_of_bools b) → digraph_arborescence_count (tournament_four_not_near_regular_exists_improving_T_of_bools b) ≤ 9 := by decideprivate def tournament_four_not_near_regular_exists_improving_b_max : Fin 6 → Bool | 0 => true | 1 => true | 2 => false | 3 => true | 4 => true | 5 => trueprivate theorem tournament_four_not_near_regular_exists_improving_b_max_tourn : digraph_is_tournament (tournament_four_not_near_regular_exists_improving_T_of_bools tournament_four_not_near_regular_exists_improving_b_max) := by decideprivate theorem tournament_four_not_near_regular_exists_improving_b_max_count : digraph_arborescence_count (tournament_four_not_near_regular_exists_improving_T_of_bools tournament_four_not_near_regular_exists_improving_b_max) = 10 := by decideprivate def tournament_four_not_near_regular_exists_improving_bools_of_T (T : Digraph (Fin 4)) [DecidableRel T.Adj] : Fin 6 → Bool | 0 => decide (T.Adj 0 1) | 1 => decide (T.Adj 0 2) | 2 => decide (T.Adj 0 3) | 3 => decide (T.Adj 1 2) | 4 => decide (T.Adj 1 3) | 5 => decide (T.Adj 2 3)private theorem tournament_four_not_near_regular_exists_improving_T_eq_T_of_bools (T : Digraph (Fin 4)) [DecidableRel T.Adj] (hT : digraph_is_tournament T) : T = tournament_four_not_near_regular_exists_improving_T_of_bools (tournament_four_not_near_regular_exists_improving_bools_of_T T) := by cases T with | mk Adj => dsimp [tournament_four_not_near_regular_exists_improving_T_of_bools] congr funext ⟨i, hi⟩ ⟨j, hj⟩ apply propext obtain ⟨h_loop, h_tourn⟩ := hT dsimp at h_loop h_tourn interval_cases i <;> interval_cases j · change Adj 0 0 ↔ tournament_four_not_near_regular_exists_improving_bit_of_fn (tournament_four_not_near_regular_exists_improving_bools_of_T { Adj := Adj }) 0 0 = true dsimp [tournament_four_not_near_regular_exists_improving_bit_of_fn]; simp [h_loop 0] · change Adj 0 1 ↔ tournament_four_not_near_regular_exists_improving_bit_of_fn (tournament_four_not_near_regular_exists_improving_bools_of_T { Adj := Adj }) 0 1 = true dsimp [tournament_four_not_near_regular_exists_improving_bit_of_fn, tournament_four_not_near_regular_exists_improving_bools_of_T]; simp · change Adj 0 2 ↔ tournament_four_not_near_regular_exists_improving_bit_of_fn (tournament_four_not_near_regular_exists_improving_bools_of_T { Adj := Adj }) 0 2 = true dsimp [tournament_four_not_near_regular_exists_improving_bit_of_fn, tournament_four_not_near_regular_exists_improving_bools_of_T]; simp · change Adj 0 3 ↔ tournament_four_not_near_regular_exists_improving_bit_of_fn (tournament_four_not_near_regular_exists_improving_bools_of_T { Adj := Adj }) 0 3 = true dsimp [tournament_four_not_near_regular_exists_improving_bit_of_fn, tournament_four_not_near_regular_exists_improving_bools_of_T]; simp · change Adj 1 0 ↔ tournament_four_not_near_regular_exists_improving_bit_of_fn (tournament_four_not_near_regular_exists_improving_bools_of_T { Adj := Adj }) 1 0 = true rw [h_tourn 1 0 (by decide)]; dsimp [tournament_four_not_near_regular_exists_improving_bit_of_fn, tournament_four_not_near_regular_exists_improving_bools_of_T]; simp · change Adj 1 1 ↔ tournament_four_not_near_regular_exists_improving_bit_of_fn (tournament_four_not_near_regular_exists_improving_bools_of_T { Adj := Adj }) 1 1 = true dsimp [tournament_four_not_near_regular_exists_improving_bit_of_fn]; simp [h_loop 1] · change Adj 1 2 ↔ tournament_four_not_near_regular_exists_improving_bit_of_fn (tournament_four_not_near_regular_exists_improving_bools_of_T { Adj := Adj }) 1 2 = true dsimp [tournament_four_not_near_regular_exists_improving_bit_of_fn, tournament_four_not_near_regular_exists_improving_bools_of_T]; simp · change Adj 1 3 ↔ tournament_four_not_near_regular_exists_improving_bit_of_fn (tournament_four_not_near_regular_exists_improving_bools_of_T { Adj := Adj }) 1 3 = true dsimp [tournament_four_not_near_regular_exists_improving_bit_of_fn, tournament_four_not_near_regular_exists_improving_bools_of_T]; simp · change Adj 2 0 ↔ tournament_four_not_near_regular_exists_improving_bit_of_fn (tournament_four_not_near_regular_exists_improving_bools_of_T { Adj := Adj }) 2 0 = true rw [h_tourn 2 0 (by decide)]; dsimp [tournament_four_not_near_regular_exists_improving_bit_of_fn, tournament_four_not_near_regular_exists_improving_bools_of_T]; simp · change Adj 2 1 ↔ tournament_four_not_near_regular_exists_improving_bit_of_fn (tournament_four_not_near_regular_exists_improving_bools_of_T { Adj := Adj }) 2 1 = true rw [h_tourn 2 1 (by decide)]; dsimp [tournament_four_not_near_regular_exists_improving_bit_of_fn, tournament_four_not_near_regular_exists_improving_bools_of_T]; simp · change Adj 2 2 ↔ tournament_four_not_near_regular_exists_improving_bit_of_fn (tournament_four_not_near_regular_exists_improving_bools_of_T { Adj := Adj }) 2 2 = true dsimp [tournament_four_not_near_regular_exists_improving_bit_of_fn]; simp [h_loop 2] · change Adj 2 3 ↔ tournament_four_not_near_regular_exists_improving_bit_of_fn (tournament_four_not_near_regular_exists_improving_bools_of_T { Adj := Adj }) 2 3 = true dsimp [tournament_four_not_near_regular_exists_improving_bit_of_fn, tournament_four_not_near_regular_exists_improving_bools_of_T]; simp · change Adj 3 0 ↔ tournament_four_not_near_regular_exists_improving_bit_of_fn (tournament_four_not_near_regular_exists_improving_bools_of_T { Adj := Adj }) 3 0 = true rw [h_tourn 3 0 (by decide)]; dsimp [tournament_four_not_near_regular_exists_improving_bit_of_fn, tournament_four_not_near_regular_exists_improving_bools_of_T]; simp · change Adj 3 1 ↔ tournament_four_not_near_regular_exists_improving_bit_of_fn (tournament_four_not_near_regular_exists_improving_bools_of_T { Adj := Adj }) 3 1 = true rw [h_tourn 3 1 (by decide)]; dsimp [tournament_four_not_near_regular_exists_improving_bit_of_fn, tournament_four_not_near_regular_exists_improving_bools_of_T]; simp · change Adj 3 2 ↔ tournament_four_not_near_regular_exists_improving_bit_of_fn (tournament_four_not_near_regular_exists_improving_bools_of_T { Adj := Adj }) 3 2 = true rw [h_tourn 3 2 (by decide)]; dsimp [tournament_four_not_near_regular_exists_improving_bit_of_fn, tournament_four_not_near_regular_exists_improving_bools_of_T]; simp · change Adj 3 3 ↔ tournament_four_not_near_regular_exists_improving_bit_of_fn (tournament_four_not_near_regular_exists_improving_bools_of_T { Adj := Adj }) 3 3 = true dsimp [tournament_four_not_near_regular_exists_improving_bit_of_fn]; simp [h_loop 3]/-- Small-instance check: every non-near-regular tournament on 4 vertices is strictly improved by some tournament on the same vertex set. -/theorem tournament_four_not_near_regular_exists_improving (T : Digraph (Fin 4)) [DecidableRel T.Adj] (hT : digraph_is_tournament T) (hnr : ¬ tournament_is_near_regular 2 T) : ∃ (T' : Digraph (Fin 4)) (_ : DecidableRel T'.Adj), digraph_is_tournament T' ∧ digraph_arborescence_count T < digraph_arborescence_count T' := by use tournament_four_not_near_regular_exists_improving_T_of_bools tournament_four_not_near_regular_exists_improving_b_max use inferInstance refine ⟨tournament_four_not_near_regular_exists_improving_b_max_tourn, ?_⟩ rw [tournament_four_not_near_regular_exists_improving_b_max_count] have hT_eq := tournament_four_not_near_regular_exists_improving_T_eq_T_of_bools T hT generalize hb : tournament_four_not_near_regular_exists_improving_bools_of_T T = b at hT_eq ⊢ have hnr' : ¬ tournament_is_near_regular 2 (tournament_four_not_near_regular_exists_improving_T_of_bools b) := by intro h apply hnr have h_eq : tournament_is_near_regular 2 T ↔ tournament_is_near_regular 2 (tournament_four_not_near_regular_exists_improving_T_of_bools b) := by subst hT_eq congr! rwa [h_eq] have hle9 := tournament_four_not_near_regular_exists_improving_check_bools b hnr' have h_count_eq : digraph_arborescence_count T = digraph_arborescence_count (tournament_four_not_near_regular_exists_improving_T_of_bools b) := by subst hT_eq congr omega