digraph_arborescence_count_reverse_arc_add_through
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
- digraph_arborescence_count_at_reverse_arc_add_throughFor a tournament with an arc u → v and any root r, the number of arborescences towards r grows by exactly (through-count of v → u after…
- digraph_arborescence_count_at_throughthrough_r(D, a → b): the number of spanning arborescences of D directed towards the root r that use the arc a → b, i.e. whose successor…
- digraph_arborescence_counttau(D): the total number of arborescences of D, the sum of a_r(D) over all roots r.
- digraph_is_tournamentA digraph is a tournament when it has no loops and between any two distinct vertices there is exactly one arc.
- 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…
- digraph_arborescence_count_throughthrough(D, a → b): the number of spanning arborescences of D, over all choices of root, that use the arc a → b.
- digraph_arborescence_count_ata_r(D): the number of spanning arborescences of D directed towards the root r. Each is recorded by its successor map p: p r = r, every…
- Used by 1
- tournament_reverse_arc_through_lt_iff_arborescence_ltIn a tournament T with an arc u → v, the total through-count strictly increases upon reversing u → v if and only if the total number of…
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.
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.
uses
Finset.sum_add_distribsimp only [digraph_arborescence_count, digraph_arborescence_count_through] rw [← Finset.sum_add_distrib, ← Finset.sum_add_distrib]
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.
uses
Finset.sum_congr,digraph_arborescence_count_at_reverse_arc_add_throughexact 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
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.
/-- 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)