AFTD Auto-Formalizing Theoretical Domains

digraph_arborescence_count_reverse_arc_add_through

theoremverified

Reversing a single arc u → v of a tournament satisfies tau(T) + through(T', v → u) = tau(T') + through(T, u → v), so the gain in the two-sided arborescence count is exactly the excess of the new through-count over the old one.

Statement

theorem digraph_arborescence_count_reverse_arc_add_through {n : ℕ} (T : Digraph (Fin n))
    [DecidableRel T.Adj] (hT : digraph_is_tournament T) (u v : Fin n) (huv : T.Adj u v) :
    digraph_arborescence_count T + digraph_arborescence_count_through (digraph_reverse_arc T u v) v u =
      digraph_arborescence_count (digraph_reverse_arc T u v) + digraph_arborescence_count_through T u v
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

The total arborescence count and total through-count of a tournament are defined as sums over all possible roots of the corresponding root-specific counts. By linearity of summation, the desired identity reduces to proving equality termwise for each root, which holds by the root-level reversal identity digraph_arborescence_count_at_reverse_arc_add_through.

  1. The identity reduces to an equality between two sums over all root vertices: ∑ r, (τ_r(T) + through_r(T', v → u)) = ∑ r, (τ_r(T') + through_r(T, u → v)), where T' is T with the arc u → v reversed.

    By definition, the total arborescence count and the total through-count are sums of the respective root-specific counts over all vertices r. Unfolding these definitions and rewriting with Finset.sum_add_distrib in reverse merges the two separate sums on each side into a single summation over r.

    lines 6–7

    uses Finset.sum_add_distrib

      simp only [digraph_arborescence_count, digraph_arborescence_count_through]
      rw [← Finset.sum_add_distrib, ← Finset.sum_add_distrib]
  2. The two summations are equal, completing the proof.

    By Finset.sum_congr, it suffices to prove that the summands match for every root r. For each r, the root-level reversal identity digraph_arborescence_count_at_reverse_arc_add_through proves that the summands are indeed equal.

    lines 8–9

    uses Finset.sum_congr, digraph_arborescence_count_at_reverse_arc_add_through

      exact Finset.sum_congr rfl
        (fun r _ => digraph_arborescence_count_at_reverse_arc_add_through T hT u v huv r)
Finset.sum_add_distrib
The sum of a pointwise sum of two functions over a finite set equals the sum of the first function plus the sum of the second: ∑ x ∈ s, (f x + g x) = ∑ x ∈ s, f x + ∑ x ∈ s, g x.
Finset.sum_congr
Two sums over equal finite sets are equal if their summands agree on every element of the index set.
digraph_arborescence_count_at_reverse_arc_add_through
In any tournament D with an arc u → v, for every root vertex r, the count of arborescences in D rooted at r plus the count of arborescences in the arc-reversed tournament D' rooted at r passing through v → u equals the count of arborescences in D' rooted at r plus the count of arborescences in D rooted at r passing through u → v.

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

/-- Summed form of the reversal identity: tau(T) + through(T', v → u) = tau(T') + through(T, u → v). -/theorem digraph_arborescence_count_reverse_arc_add_through {n : ℕ} (T : Digraph (Fin n))    [DecidableRel T.Adj] (hT : digraph_is_tournament T) (u v : Fin n) (huv : T.Adj u v) :    digraph_arborescence_count T + digraph_arborescence_count_through (digraph_reverse_arc T u v) v u =      digraph_arborescence_count (digraph_reverse_arc T u v) + digraph_arborescence_count_through T u v := by  simp only [digraph_arborescence_count, digraph_arborescence_count_through]  rw [← Finset.sum_add_distrib, ← Finset.sum_add_distrib]  exact Finset.sum_congr rfl    (fun r _ => digraph_arborescence_count_at_reverse_arc_add_through T hT u v huv r)
See it in the graphDiscuss this resultChallenge it