AFTD Auto-Formalizing Theoretical Domains

tournament_four_arborescence_maximizer_is_near_regular

theoremverifiedoriginal

Every tournament on 4 vertices maximizing the total number of spanning arborescences among all tournaments on 4 vertices is near-regular.

Statement

theorem tournament_four_arborescence_maximizer_is_near_regular
    (T : Digraph (Fin 4)) [DecidableRel T.Adj] (hT : digraph_is_tournament T)
    (hmax : ∀ (T' : Digraph (Fin 4)) [DecidableRel T'.Adj],
      digraph_is_tournament T' → digraph_arborescence_count T' ≤ digraph_arborescence_count T) :
    tournament_is_near_regular 2 T
Related work
arXiv:2610.25886
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3

Read back from the Lean

Let $T$ be a directed graph on the vertex set $\text{Fin } 4$ with decidable adjacency relation. Assume that: 1. $T$ is a tournament (it has no self-loops, and for all distinct vertices $x \ne y$, exactly one of the directed edges $(x, y)$ or $(y, x)$ is in $T$). 2. $T$ maximizes the total number of arborescences among all tournaments on $\text{Fin } 4$: for every directed graph $T'$ on $\text{Fin } 4$ with decidable adjacency, if $T'$ is a tournament, then the total arborescence count of $T'$ is at most that of $T$. Then $T$ is near-regular with parameter $2$, meaning that for every vertex $v \in \text{Fin } 4$, the out-degree of $v$ in $T$ is either $1$ or $2$.

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

The proof, explained

The theorem is proved by finite computational exhaustion and comparison with an explicit witness. First, a concrete tournament on 4 vertices (`tournament_four_b_max`) is exhibited and verified by computation to have 10 spanning arborescences, establishing that any arborescence maximizer must have at least 10 arborescences. Next, any tournament on 4 vertices is shown to be completely determined by a 6-bit vector encoding its edge orientations, and an exhaustive verification (`decide`) over all $2^6 = 64$ configurations shows that every 4-vertex tournament that fails to be near-regular has at most 9 spanning arborescences. A maximizer that is not near-regular would therefore have at most 9 arborescences, contradicting the lower bound of 10.

  1. Adjacency in the graph reconstructed from a 6-tuple of booleans is decidable.

    Given vertices $i, j \in \operatorname{Fin} 4$, adjacency in `tournament_four_T_of_bools b` is defined by the boolean equality `tournament_four_bit_of_fn b i j = true`, which is decidable by typeclass synthesis.

    lines 21–23

      intro i j
      dsimp [tournament_four_T_of_bools]
      infer_instance
  2. The tournament property is decidable for any finite digraph with decidable adjacency.

    The definition `digraph_is_tournament` consists of universally quantified conditions over finite sets (no self-loops and tournament antisymmetry between distinct vertices), which Lean synthesizes as decidable via `infer_instance`.

    lines 27–28

      dsimp [digraph_is_tournament]
      infer_instance
  3. Near-regularity is decidable for finite digraphs with decidable adjacency.

    The property `tournament_is_near_regular m D` asserts that the out-degree of every vertex is $m - 1$ or $m$, which is a bounded universal quantification over a finite set and hence decidable.

    lines 32–33

      dsimp [tournament_is_near_regular]
      infer_instance
  4. Every 4-vertex tournament encoded by 6 booleans that is not near-regular has at most 9 spanning arborescences. automation

    Because there are only $2^6 = 64$ functions $b : \operatorname{Fin} 6 \to \operatorname{Bool}$, the universal claim is verified by exhaustive computation using `decide`.

    line 38

      decide
  5. The explicit configuration `tournament_four_b_max` defines a tournament with exactly 10 spanning arborescences. automation

    By exhaustive evaluation (`decide`), the concrete 6-bit vector `tournament_four_b_max` defines a valid tournament (`tournament_four_b_max_tourn`) whose spanning arborescence count is 10 (`tournament_four_b_max_count`).

    lines 48–49

    private theorem tournament_four_b_max_tourn : digraph_is_tournament (tournament_four_T_of_bools tournament_four_b_max) := by decide
    private theorem tournament_four_b_max_count : digraph_arborescence_count (tournament_four_T_of_bools tournament_four_b_max) = 10 := by decide
  6. Reducing the equality of $T$ and its boolean reconstruction to the 16 pairs of vertices.

    To prove $T = \operatorname{tournament\_four\_T\_of\_bools}(\operatorname{tournament\_four\_bools\_of\_T}(T))$, we unpack the digraph structure and apply functional and propositional extensionality (`propext`). We then unpack the tournament hypotheses (irreflexivity $h\_loop$ and antisymmetry $h\_tourn$) and split into 16 cases for $(i, j) \in \operatorname{Fin} 4 \times \operatorname{Fin} 4$ using `interval_cases`.

    lines 61–68

    uses propext

      cases T with | mk Adj =>
      dsimp [tournament_four_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
  7. In all 16 vertex-pair cases, the adjacency relation of $T$ coincides with that of the reconstructed graph.

    For diagonal entries ($i = j$), both relations are false because tournaments have no self-loops ($h\_loop$). For $i < j$, adjacency matches the stored bit directly. For $i > j$, tournament antisymmetry ($h\_tourn$) rewrites $T.\operatorname{Adj}(i, j)$ to $\neg T.\operatorname{Adj}(j, i)$, matching the negated bit $!b$ in `tournament_four_bit_of_fn`. Each case simplifies to true.

    lines 69–100

      · change Adj 0 0 ↔ tournament_four_bit_of_fn (tournament_four_bools_of_T { Adj := Adj }) 0 0 = true
        dsimp [tournament_four_bit_of_fn]; simp [h_loop 0]
      · change Adj 0 1 ↔ tournament_four_bit_of_fn (tournament_four_bools_of_T { Adj := Adj }) 0 1 = true
        dsimp [tournament_four_bit_of_fn, tournament_four_bools_of_T]; simp
      · change Adj 0 2 ↔ tournament_four_bit_of_fn (tournament_four_bools_of_T { Adj := Adj }) 0 2 = true
        dsimp [tournament_four_bit_of_fn, tournament_four_bools_of_T]; simp
      · change Adj 0 3 ↔ tournament_four_bit_of_fn (tournament_four_bools_of_T { Adj := Adj }) 0 3 = true
        dsimp [tournament_four_bit_of_fn, tournament_four_bools_of_T]; simp
      · change Adj 1 0 ↔ tournament_four_bit_of_fn (tournament_four_bools_of_T { Adj := Adj }) 1 0 = true
        rw [h_tourn 1 0 (by decide)]; dsimp [tournament_four_bit_of_fn, tournament_four_bools_of_T]; simp
      · change Adj 1 1 ↔ tournament_four_bit_of_fn (tournament_four_bools_of_T { Adj := Adj }) 1 1 = true
        dsimp [tournament_four_bit_of_fn]; simp [h_loop 1]
      · change Adj 1 2 ↔ tournament_four_bit_of_fn (tournament_four_bools_of_T { Adj := Adj }) 1 2 = true
        dsimp [tournament_four_bit_of_fn, tournament_four_bools_of_T]; simp
      · change Adj 1 3 ↔ tournament_four_bit_of_fn (tournament_four_bools_of_T { Adj := Adj }) 1 3 = true
        dsimp [tournament_four_bit_of_fn, tournament_four_bools_of_T]; simp
      · change Adj 2 0 ↔ tournament_four_bit_of_fn (tournament_four_bools_of_T { Adj := Adj }) 2 0 = true
        rw [h_tourn 2 0 (by decide)]; dsimp [tournament_four_bit_of_fn, tournament_four_bools_of_T]; simp
      · change Adj 2 1 ↔ tournament_four_bit_of_fn (tournament_four_bools_of_T { Adj := Adj }) 2 1 = true
        rw [h_tourn 2 1 (by decide)]; dsimp [tournament_four_bit_of_fn, tournament_four_bools_of_T]; simp
      · change Adj 2 2 ↔ tournament_four_bit_of_fn (tournament_four_bools_of_T { Adj := Adj }) 2 2 = true
        dsimp [tournament_four_bit_of_fn]; simp [h_loop 2]
      · change Adj 2 3 ↔ tournament_four_bit_of_fn (tournament_four_bools_of_T { Adj := Adj }) 2 3 = true
        dsimp [tournament_four_bit_of_fn, tournament_four_bools_of_T]; simp
      · change Adj 3 0 ↔ tournament_four_bit_of_fn (tournament_four_bools_of_T { Adj := Adj }) 3 0 = true
        rw [h_tourn 3 0 (by decide)]; dsimp [tournament_four_bit_of_fn, tournament_four_bools_of_T]; simp
      · change Adj 3 1 ↔ tournament_four_bit_of_fn (tournament_four_bools_of_T { Adj := Adj }) 3 1 = true
        rw [h_tourn 3 1 (by decide)]; dsimp [tournament_four_bit_of_fn, tournament_four_bools_of_T]; simp
      · change Adj 3 2 ↔ tournament_four_bit_of_fn (tournament_four_bools_of_T { Adj := Adj }) 3 2 = true
        rw [h_tourn 3 2 (by decide)]; dsimp [tournament_four_bit_of_fn, tournament_four_bools_of_T]; simp
      · change Adj 3 3 ↔ tournament_four_bit_of_fn (tournament_four_bools_of_T { Adj := Adj }) 3 3 = true
        dsimp [tournament_four_bit_of_fn]; simp [h_loop 3]
  8. The maximizing tournament $T$ has at least 10 spanning arborescences.

    By the maximality assumption `hmax`, $T$ has at least as many spanning arborescences as any other 4-vertex tournament. Evaluating at the tournament defined by `tournament_four_b_max`, which is a tournament by `tournament_four_b_max_tourn` with 10 arborescences by `tournament_four_b_max_count`, we obtain $\operatorname{digraph\_arborescence\_count}(T) \ge 10$.

    lines 108–111

    uses tournament_four_b_max_tourn, tournament_four_b_max_count

      have h10 : 10 ≤ digraph_arborescence_count T := by
        have hle := hmax (tournament_four_T_of_bools tournament_four_b_max) tournament_four_b_max_tourn
        rw [tournament_four_b_max_count] at hle
        exact hle
  9. $T$ is equal to the tournament reconstructed from its 6 edge bits.

    Applying `tournament_four_T_eq_T_of_bools` to $T$ and the tournament assumption shows that $T$ equals `tournament_four_T_of_bools (tournament_four_bools_of_T T)`.

    line 112

    uses tournament_four_T_eq_T_of_bools

      have hT_eq := tournament_four_T_eq_T_of_bools T hT
  10. Assume for contradiction that $T$ is not near-regular, and name $b$ as its 6-bit encoding.

    We assume $\neg \operatorname{tournament\_is\_near\_regular}(2, T)$ for contradiction (`by_contra hnr`) and generalize the extracted edge bits to a variable $b$.

    lines 113–114

      by_contra hnr
      generalize hb : tournament_four_bools_of_T T = b at hT_eq ⊢
  11. The reconstructed tournament $\operatorname{tournament\_four\_T\_of\_bools}(b)$ is not near-regular.

    Since $T = \operatorname{tournament\_four\_T\_of\_bools}(b)$, near-regularity of $T$ is equivalent to near-regularity of the reconstructed tournament, so the failure of near-regularity transfers to `tournament_four_T_of_bools b`.

    lines 115–121

      have hnr' : ¬ tournament_is_near_regular 2 (tournament_four_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_T_of_bools b) := by
          subst hT_eq
          congr!
        rwa [h_eq]
  12. The reconstructed tournament has at most 9 spanning arborescences.

    Applying the exhaustive check `tournament_four_check_bools` to $b$ and the fact that it is not near-regular yields that its arborescence count is at most 9.

    line 122

    uses tournament_four_check_bools

      have hle9 := tournament_four_check_bools b hnr'
  13. The arborescence count of $T$ equals that of the reconstructed tournament.

    Since $T$ is equal to `tournament_four_T_of_bools b`, their spanning arborescence counts are identical.

    lines 123–125

      have h_count_eq : digraph_arborescence_count T = digraph_arborescence_count (tournament_four_T_of_bools b) := by
        subst hT_eq
        congr
  14. Contradiction, completing the proof that $T$ is near-regular.

    We have $\operatorname{digraph\_arborescence\_count}(T) \ge 10$ and $\operatorname{digraph\_arborescence\_count}(T) \le 9$, which contradicts linear arithmetic over $\mathbb{N}$ (`omega`).

    line 126

      omega
propext
Propositional extensionality: logically equivalent propositions are equal ($a \leftrightarrow b \implies a = b$).
tournament_four_b_max_count
The 4-vertex tournament defined by the boolean vector `tournament_four_b_max` has exactly 10 spanning arborescences.
tournament_four_b_max_tourn
The 4-vertex directed graph defined by `tournament_four_b_max` satisfies the tournament axioms (no self-loops and exactly one directed edge between any pair of distinct vertices).
tournament_four_check_bools
Every 4-vertex tournament encoded by a 6-tuple of booleans that is not near-regular has at most 9 spanning arborescences.
tournament_four_T_eq_T_of_bools
Every tournament on 4 vertices is equal to the tournament reconstructed from the 6 boolean edge orientations extracted from it.

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

private def tournament_four_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_T_of_bools (b : Fin 6 → Bool) : Digraph (Fin 4) where  Adj i j := tournament_four_bit_of_fn b i j = trueprivate instance (b : Fin 6 → Bool) : DecidableRel (tournament_four_T_of_bools b).Adj := by  intro i j  dsimp [tournament_four_T_of_bools]  infer_instanceprivate instance tournament_four_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_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_check_bools :    ∀ b : Fin 6 → Bool, ¬ tournament_is_near_regular 2 (tournament_four_T_of_bools b) →      digraph_arborescence_count (tournament_four_T_of_bools b) ≤ 9 := by  decideprivate def tournament_four_b_max : Fin 6 → Bool  | 0 => true  | 1 => true  | 2 => false  | 3 => true  | 4 => true  | 5 => trueprivate theorem tournament_four_b_max_tourn : digraph_is_tournament (tournament_four_T_of_bools tournament_four_b_max) := by decideprivate theorem tournament_four_b_max_count : digraph_arborescence_count (tournament_four_T_of_bools tournament_four_b_max) = 10 := by decideprivate def tournament_four_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_T_eq_T_of_bools (T : Digraph (Fin 4)) [DecidableRel T.Adj] (hT : digraph_is_tournament T) :    T = tournament_four_T_of_bools (tournament_four_bools_of_T T) := by  cases T with | mk Adj =>  dsimp [tournament_four_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_bit_of_fn (tournament_four_bools_of_T { Adj := Adj }) 0 0 = true    dsimp [tournament_four_bit_of_fn]; simp [h_loop 0]  · change Adj 0 1 ↔ tournament_four_bit_of_fn (tournament_four_bools_of_T { Adj := Adj }) 0 1 = true    dsimp [tournament_four_bit_of_fn, tournament_four_bools_of_T]; simp  · change Adj 0 2 ↔ tournament_four_bit_of_fn (tournament_four_bools_of_T { Adj := Adj }) 0 2 = true    dsimp [tournament_four_bit_of_fn, tournament_four_bools_of_T]; simp  · change Adj 0 3 ↔ tournament_four_bit_of_fn (tournament_four_bools_of_T { Adj := Adj }) 0 3 = true    dsimp [tournament_four_bit_of_fn, tournament_four_bools_of_T]; simp  · change Adj 1 0 ↔ tournament_four_bit_of_fn (tournament_four_bools_of_T { Adj := Adj }) 1 0 = true    rw [h_tourn 1 0 (by decide)]; dsimp [tournament_four_bit_of_fn, tournament_four_bools_of_T]; simp  · change Adj 1 1 ↔ tournament_four_bit_of_fn (tournament_four_bools_of_T { Adj := Adj }) 1 1 = true    dsimp [tournament_four_bit_of_fn]; simp [h_loop 1]  · change Adj 1 2 ↔ tournament_four_bit_of_fn (tournament_four_bools_of_T { Adj := Adj }) 1 2 = true    dsimp [tournament_four_bit_of_fn, tournament_four_bools_of_T]; simp  · change Adj 1 3 ↔ tournament_four_bit_of_fn (tournament_four_bools_of_T { Adj := Adj }) 1 3 = true    dsimp [tournament_four_bit_of_fn, tournament_four_bools_of_T]; simp  · change Adj 2 0 ↔ tournament_four_bit_of_fn (tournament_four_bools_of_T { Adj := Adj }) 2 0 = true    rw [h_tourn 2 0 (by decide)]; dsimp [tournament_four_bit_of_fn, tournament_four_bools_of_T]; simp  · change Adj 2 1 ↔ tournament_four_bit_of_fn (tournament_four_bools_of_T { Adj := Adj }) 2 1 = true    rw [h_tourn 2 1 (by decide)]; dsimp [tournament_four_bit_of_fn, tournament_four_bools_of_T]; simp  · change Adj 2 2 ↔ tournament_four_bit_of_fn (tournament_four_bools_of_T { Adj := Adj }) 2 2 = true    dsimp [tournament_four_bit_of_fn]; simp [h_loop 2]  · change Adj 2 3 ↔ tournament_four_bit_of_fn (tournament_four_bools_of_T { Adj := Adj }) 2 3 = true    dsimp [tournament_four_bit_of_fn, tournament_four_bools_of_T]; simp  · change Adj 3 0 ↔ tournament_four_bit_of_fn (tournament_four_bools_of_T { Adj := Adj }) 3 0 = true    rw [h_tourn 3 0 (by decide)]; dsimp [tournament_four_bit_of_fn, tournament_four_bools_of_T]; simp  · change Adj 3 1 ↔ tournament_four_bit_of_fn (tournament_four_bools_of_T { Adj := Adj }) 3 1 = true    rw [h_tourn 3 1 (by decide)]; dsimp [tournament_four_bit_of_fn, tournament_four_bools_of_T]; simp  · change Adj 3 2 ↔ tournament_four_bit_of_fn (tournament_four_bools_of_T { Adj := Adj }) 3 2 = true    rw [h_tourn 3 2 (by decide)]; dsimp [tournament_four_bit_of_fn, tournament_four_bools_of_T]; simp  · change Adj 3 3 ↔ tournament_four_bit_of_fn (tournament_four_bools_of_T { Adj := Adj }) 3 3 = true    dsimp [tournament_four_bit_of_fn]; simp [h_loop 3]/-- Total arborescence maximizers on 4 vertices are near-regular (m = 2 base case of OP-545). -/theorem tournament_four_arborescence_maximizer_is_near_regular    (T : Digraph (Fin 4)) [DecidableRel T.Adj] (hT : digraph_is_tournament T)    (hmax : ∀ (T' : Digraph (Fin 4)) [DecidableRel T'.Adj],      digraph_is_tournament T' → digraph_arborescence_count T' ≤ digraph_arborescence_count T) :    tournament_is_near_regular 2 T := by  have h10 : 10 ≤ digraph_arborescence_count T := by    have hle := hmax (tournament_four_T_of_bools tournament_four_b_max) tournament_four_b_max_tourn    rw [tournament_four_b_max_count] at hle    exact hle  have hT_eq := tournament_four_T_eq_T_of_bools T hT  by_contra hnr  generalize hb : tournament_four_bools_of_T T = b at hT_eq ⊢  have hnr' : ¬ tournament_is_near_regular 2 (tournament_four_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_T_of_bools b) := by      subst hT_eq      congr!    rwa [h_eq]  have hle9 := tournament_four_check_bools b hnr'  have h_count_eq : digraph_arborescence_count T = digraph_arborescence_count (tournament_four_T_of_bools b) := by    subst hT_eq    congr  omega
See it in the graphDiscuss this resultChallenge it