tournament_reverse_arc_through_lt_iff_arborescence_lt
In 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 spanning arborescences strictly increases.
Statement
theorem tournament_reverse_arc_through_lt_iff_arborescence_lt {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_through T u v <
digraph_arborescence_count_through (digraph_reverse_arc T u v) v u ↔
digraph_arborescence_count T <
digraph_arborescence_count (digraph_reverse_arc T u v)- Source
- step towards tournament_reverse_arc_through_count_lt
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- digraph_arborescence_count_reverse_arc_add_throughReversing 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…
- 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_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…
The proof, explained
The equivalence follows from a conservation identity relating total arborescence counts to the counts of arborescences containing the reversed arc. When an arc u → v in tournament T is reversed to obtain T', the identity τ(T) + through(T', v → u) = τ(T') + through(T, u → v) holds. From this linear equality over ℕ, linear arithmetic immediately implies that through(T, u → v) < through(T', v → u) if and only if τ(T) < τ(T').
The arborescence counts satisfy τ(T) + through(T', v → u) = τ(T') + through(T, u → v), where T' denotes the tournament obtained by reversing the arc u → v.
Applying the lemma digraph_arborescence_count_reverse_arc_add_through to the tournament T and the arc u → v yields this conservation equation relating the total arborescence counts and the through-arc counts before and after the reversal.
uses
digraph_arborescence_count_reverse_arc_add_throughhave h := digraph_arborescence_count_reverse_arc_add_through T hT u v huvthrough(T, u → v) < through(T', v → u) ↔ τ(T) < τ(T')
Splitting the equivalence into both forward and backward implications (constructor) and assuming the antecedent in each direction (intro hlt), linear arithmetic on natural numbers (omega) concludes the strict inequality from the identity A + D = B + C, where A = τ(T), B = τ(T'), C = through(T, u → v), and D = through(T', v → u).
constructor <;> intro hlt <;> omega
digraph_arborescence_count_reverse_arc_add_through- In a tournament T with an arc u → v, the total number of spanning arborescences in T plus the number of arborescences in the reversed tournament containing v → u equals the total number of arborescences in the reversed tournament plus the number of arborescences in T containing 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.
/-- In a tournament T with arc u → v, the through-count inequality through(T, u → v) < through(reverse(T, u, v), v → u) is equivalent to the total arborescence count inequality tau(T) < tau(reverse(T, u, v)). -/theorem tournament_reverse_arc_through_lt_iff_arborescence_lt {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_through T u v < digraph_arborescence_count_through (digraph_reverse_arc T u v) v u ↔ digraph_arborescence_count T < digraph_arborescence_count (digraph_reverse_arc T u v) := by have h := digraph_arborescence_count_reverse_arc_add_through T hT u v huv constructor <;> intro hlt <;> omega