tournament_reverse_arc_through_root_endpoint_eq
In a tournament T with arc u → v, the number of arborescences rooted at v using u → v equals the number of arborescences of reverse(T, u, v) rooted at u using v → u, via the canonical bijection exchanging root and parent pointer on {u, v}.
Statement
theorem tournament_reverse_arc_through_root_endpoint_eq {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_at_through T v u v =
digraph_arborescence_count_at_through (digraph_reverse_arc T u v) u v u- Source
- step towards tournament_reverse_arc_arborescence_count_lt
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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_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_is_tournamentA digraph is a tournament when it has no loops and between any two distinct vertices there is exactly one arc.
The proof, explained
The theorem is proved by constructing an explicit bijection between the set s of parent-pointer representations of arborescences in T rooted at v containing the arc u → v, and the set t of arborescences in the reversed tournament T' rooted at u containing v → u. The bijection f redirects the reversed arc endpoints by setting f(p)(u) = u (making u the new root) and f(p)(v) = u (directing v to u), while leaving all other parent pointers unchanged; the reverse map g symmetrically exchanges the roles of u and v. The crucial step is proving that f(p) preserves root-reachability in n steps: by the pigeonhole principle, any orbit under p reaches v in fewer than n steps, which implies the modified orbit under f(p) transitions through v to u and remains at u within n steps. Mutual inversion and edge validity are verified by straightforward case analysis on the vertices, completing the equicardinality via Finset.card_bij'.
Once an orbit reaches a fixed point of f at step a, any step b ≥ a also reaches that fixed point.
Writing b = a + k, the iterate f^[b](w) decomposes as f^[k](f^[a](w)) = f^[k](x) = x because x is fixed by f.
uses
Nat.exists_eq_add_of_le,Nat.add_comm,Function.iterate_add_apply,Function.iterate_fixedobtain ⟨k, rfl⟩ := Nat.exists_eq_add_of_le hab rw [Nat.add_comm, Function.iterate_add_apply, hw, Function.iterate_fixed h k]
For any number of steps k, the orbit of w under the modified map p' either matches the original orbit under p or has already reached u.
By induction on k: the base case k = 0 is identity. For the induction step, if the orbit already reached u, it stays at u because p'(u) = u; if it agreed with p, either the current point is u or v (which p' sends to u) or it is another vertex (where p' agrees with p).
uses
Function.iterate_succ_apply'intro p' induction k with | zero => left; rfl | succ k ih => rw [Function.iterate_succ_apply', Function.iterate_succ_apply'] cases ih with | inr h => right have hp'u : p' u = u := by simp [p'] rw [h, hp'u] | inl h => rw [h] dsimp [p'] split_ifs with h1 h2 · right; rfl · right; rfl · left; rfl
If x is periodic with period d under f, then iterating any multiple m * d times fixes x.
By induction on m: m = 0 is trivial, and for m + 1 the exponent decomposes as (m + 1) * d = m * d + d, so f^[(m+1)*d](x) = f^[m*d](f^[d](x)) = f^[m*d](x) = x by the induction hypothesis.
uses
Nat.zero_mul,Function.iterate_zero_apply,Nat.succ_mul,Function.iterate_add_applyinduction m with | zero => rw [Nat.zero_mul, Function.iterate_zero_apply] | succ m ih => rw [Nat.succ_mul, Function.iterate_add_apply, h, ih]
If the orbit of w repeats between steps a < b ≤ n in a map converging globally to v in n steps, then p^[a](w) is already the root v.
With d = b - a > 0, the point p^[a](w) has period d, so p^[n * d](p^[a](w)) = p^[a](w). Writing n * d = (d - 1) * n + n, global convergence in n steps also shows p^[n * d](p^[a](w)) = v. Equating the two gives p^[a](w) = v, with a < b ≤ n implying a < n.
uses
Nat.sub_pos_of_lt,Function.iterate_add_apply,tournament_reverse_arc_iter_mul_cycle,Nat.sub_add_cancel,Nat.left_distrib,Nat.mul_comm,Nat.mul_one,Function.iterate_fixed,lt_of_lt_of_lelet d := b - a have hdpos : 0 < d := Nat.sub_pos_of_lt hlt have hba : b = d + a := by omega have hfeq' : p^[d] (p^[a] w) = p^[a] w := by have h1 : p^[d + a] w = p^[a] w := by rwa [← hba] rwa [Function.iterate_add_apply] at h1 have hcycle : p^[n * d] (p^[a] w) = p^[a] w := tournament_reverse_arc_iter_mul_cycle p (p^[a] w) d hfeq' n have hnd : n * d = (d - 1) * n + n := by calc n * d = n * ((d - 1) + 1) := by rw [Nat.sub_add_cancel hdpos] _ = n * (d - 1) + n * 1 := Nat.left_distrib n (d - 1) 1 _ = (d - 1) * n + n := by rw [Nat.mul_comm n (d - 1), Nat.mul_one] have hreach : p^[n * d] (p^[a] w) = v := by rw [hnd, Function.iterate_add_apply, hpn, Function.iterate_fixed hpv] have hpav : p^[a] w = v := hcycle.symm.trans hreach exact ⟨a, lt_of_lt_of_le hlt hble, hpav⟩
Every vertex w reaches the root v under p in strictly fewer than n steps.
Considering the n + 1 values p^[0](w), ..., p^[n](w) in the n-element set Fin n, the pigeonhole principle (Fintype.not_injective_of_card_lt) implies two indices i ≠ j produce the same iterate. Applying tournament_reverse_arc_iter_reach_root_lt_aux to min(i, j) < max(i, j) ≤ n gives an index a < n with p^[a](w) = v.
uses
Fintype.card_fin,Nat.lt_succ_self,Fintype.not_injective_of_card_lt,Fin.ext,lt_or_gt_of_ne,tournament_reverse_arc_iter_reach_root_lt_aux,Nat.le_of_lt_succlet f : Fin (n + 1) → Fin n := fun i => p^[i.val] w have hcard : Fintype.card (Fin n) < Fintype.card (Fin (n + 1)) := by simp only [Fintype.card_fin, Nat.lt_succ_self] have hninj := Fintype.not_injective_of_card_lt f hcard simp only [Function.Injective, not_forall] at hninj rcases hninj with ⟨i, j, hfeq, hne⟩ have hneval : i.val ≠ j.val := fun h => hne (Fin.ext h) rcases lt_or_gt_of_ne hneval with hlt | hgt · exact tournament_reverse_arc_iter_reach_root_lt_aux p v hpv hpn w i.val j.val hlt (Nat.le_of_lt_succ j.isLt) hfeq.symm · exact tournament_reverse_arc_iter_reach_root_lt_aux p v hpv hpn w j.val i.val hgt (Nat.le_of_lt_succ i.isLt) hfeq
Iterating the modified map p' (where both u and v map to u) n times from any vertex w reaches u.
The original orbit reaches v at some step a < n. By tournament_reverse_arc_iter_eq_or_eq_u, either p'^[a](w) = v (so the next step hits p'(v) = u, with a + 1 ≤ n) or p'^[a](w) = u (with a ≤ n). In either case, since u is a fixed point of p', iterating up to n steps keeps the value at u.
uses
tournament_reverse_arc_iter_reach_root_lt,tournament_reverse_arc_iter_eq_or_eq_u,Function.iterate_succ_apply',tournament_reverse_arc_iter_ge,Nat.succ_le_of_lt,le_of_ltintro p' have hp'u : p' u = u := by simp [p'] have hp'v : p' v = u := by dsimp [p'] split_ifs with h1 h2 · rfl · rfl · exfalso; exact h2 rfl rcases tournament_reverse_arc_iter_reach_root_lt p v hpv hpn w with ⟨a, han, hpa⟩ have hor := tournament_reverse_arc_iter_eq_or_eq_u p u v w a change p'^[a] w = p^[a] w ∨ p'^[a] w = u at hor rcases hor with h1 | h2 · have hp'a1 : p'^[a + 1] w = u := by rw [Function.iterate_succ_apply', h1, hpa, hp'v] exact tournament_reverse_arc_iter_ge p' u hp'u (Nat.succ_le_of_lt han) hp'a1 · exact tournament_reverse_arc_iter_ge p' u hp'u (le_of_lt han) h2
The endpoints u and v of the tournament arc are distinct.
Since a tournament has no self-loops, the assumption T.Adj u v implies u ≠ v.
have hne : u ≠ v := fun h => hT.1 v (h ▸ huv)
The equality of arborescence counts reduces to showing that the set s of valid parent maps for T has the same cardinality as the set t of valid parent maps for the reversed tournament T'.
Unfolding digraph_arborescence_count_at_through expresses each count as the size of a filtered subset of parent functions: s for T rooted at v with p(u) = v, and t for T' rooted at u with q(v) = u. We define candidate mappings f and g that swap the root and redirect the edge between u and v while leaving all other pointers untouched.
uses
digraph_arborescence_count_at_throughrw [digraph_arborescence_count_at_through, digraph_arborescence_count_at_through] let s : Finset (Fin n → Fin n) := Finset.univ.filter (fun p => p v = v ∧ (∀ w, w ≠ v → T.Adj w (p w)) ∧ (∀ w, p^[n] w = v) ∧ p u = v) let t : Finset (Fin n → Fin n) := Finset.univ.filter (fun q => q u = u ∧ (∀ w, w ≠ u → (digraph_reverse_arc T u v).Adj w (q w)) ∧ (∀ w, q^[n] w = u) ∧ q v = u) change s.card = t.card let f : (Fin n → Fin n) → (Fin n → Fin n) := fun p x => if x = u then u else if x = v then u else p x let g : (Fin n → Fin n) → (Fin n → Fin n) := fun q x => if x = v then v else if x = u then v else q x
The map g is a left inverse to f on s.
For any p in s, evaluating g (f p) at x gives: if x = v, then v = p(v); if x = u, then v = p(u); and if x ∉ {u, v}, then p(x). Hence g (f p) = p.
uses
Finset.mem_filter,Finset.mem_univ,if_neg,if_pos,true_andhave hfg : ∀ p ∈ s, g (f p) = p := by intro p hp simp only [s, Finset.mem_filter, Finset.mem_univ, true_and] at hp ext x dsimp [f, g] by_cases hx_v : x = v · rw [hx_v, if_pos rfl, hp.1] · rw [if_neg hx_v] by_cases hx_u : x = u · rw [hx_u, if_pos rfl, hp.2.2.2] · rw [if_neg hx_u, if_neg hx_u, if_neg hx_v]
The map f is a left inverse to g on t.
Symmetrically, for any q in t, evaluating f (g q) at x gives: if x = u, then u = q(u); if x = v, then u = q(v); and if x ∉ {u, v}, then q(x). Hence f (g q) = q.
uses
Finset.mem_filter,Finset.mem_univ,if_neg,if_pos,true_andhave hgf : ∀ q ∈ t, f (g q) = q := by intro q hq simp only [t, Finset.mem_filter, Finset.mem_univ, true_and] at hq ext x dsimp [f, g] by_cases hx_u : x = u · rw [hx_u, if_pos rfl, hq.1] · rw [if_neg hx_u] by_cases hx_v : x = v · rw [hx_v, if_pos rfl, hq.2.2.2] · rw [if_neg hx_v, if_neg hx_v, if_neg hx_u]
The map f sends valid parent maps in s to valid parent maps in t.
We verify the four defining properties of t for f(p): f(p)(u) = u; for w ≠ u, the parent pointer is an edge in T' (at w = v it is the reversed edge v → u, and at all other vertices the edge is untouched); every orbit under f(p) reaches u in n steps by tournament_reverse_arc_p'_iter_n_eq_u; and f(p)(v) = u.
uses
Finset.mem_filter,Finset.mem_univ,Ne.symm,Or.inl,Or.inr,if_neg,if_pos,tournament_reverse_arc_p'_iter_n_eq_u,true_andhave hfst : ∀ p ∈ s, f p ∈ t := by intro p hp simp only [s, Finset.mem_filter, Finset.mem_univ, true_and] at hp simp only [t, Finset.mem_filter, Finset.mem_univ, true_and] refine ⟨?_, ?_, ?_, ?_⟩ · dsimp [f]; rw [if_pos rfl] · intro w hw by_cases hwv : w = v · rw [hwv] have hfpv : f p v = u := by dsimp [f]; rw [if_neg (Ne.symm hne), if_pos rfl] rw [hfpv] rw [if_pos (Or.inr ⟨rfl, rfl⟩)] exact huv · have hfpw : f p w = p w := by dsimp [f]; rw [if_neg hw, if_neg hwv] rw [hfpw] have hcond : ¬ (w = u ∧ p w = v ∨ w = v ∧ p w = u) := by intro | Or.inl h => exact hw h.1 | Or.inr h => exact hwv h.1 rw [if_neg hcond] exact hp.2.1 w hwv · intro w exact tournament_reverse_arc_p'_iter_n_eq_u p u v hp.1 hp.2.2.1 w · dsimp [f]; rw [if_neg (Ne.symm hne), if_pos rfl]
The map g sends valid parent maps in t to valid parent maps in s.
By symmetric reasoning, g(q) satisfies the four defining properties of s: g(q)(v) = v; for w ≠ v, the parent pointer is an edge in T (at w = u it is the original edge u → v, and at all other vertices the edge is untouched); every orbit under g(q) reaches v in n steps by tournament_reverse_arc_p'_iter_n_eq_u; and g(q)(u) = v.
uses
Finset.mem_filter,Finset.mem_univ,Or.inl,Or.inr,if_neg,if_pos,tournament_reverse_arc_p'_iter_n_eq_u,true_andhave hgts : ∀ q ∈ t, g q ∈ s := by intro q hq simp only [t, Finset.mem_filter, Finset.mem_univ, true_and] at hq simp only [s, Finset.mem_filter, Finset.mem_univ, true_and] refine ⟨?_, ?_, ?_, ?_⟩ · dsimp [g]; rw [if_pos rfl] · intro w hw by_cases hwu : w = u · rw [hwu] have hgqu : g q u = v := by dsimp [g]; rw [if_neg hne, if_pos rfl] rw [hgqu] exact huv · have hgqw : g q w = q w := by dsimp [g]; rw [if_neg hw, if_neg hwu] rw [hgqw] have hqadj := hq.2.1 w hwu have hcond : ¬ (w = u ∧ q w = v ∨ w = v ∧ q w = u) := by intro | Or.inl h => exact hwu h.1 | Or.inr h => exact hw h.1 rwa [if_neg hcond] at hqadj · intro w exact tournament_reverse_arc_p'_iter_n_eq_u q v u hq.1 hq.2.2.1 w · dsimp [g]; rw [if_neg hne, if_pos rfl]
The cardinalities of s and t are equal, proving the theorem.
With mutually inverse mappings f and g established between the finite sets s and t, Finset.card_bij' concludes that s and t have the same cardinality.
uses
Finset.card_bij'exact Finset.card_bij' (fun p hp => f p) (fun q hq => g q) hfst hgts (fun p hp => hfg p hp) (fun q hq => hgf q hq)
Nat.exists_eq_add_of_le- If a ≤ b, then b = a + k for some natural number k.
Nat.add_comm- Addition of natural numbers is commutative: n + m = m + n.
Function.iterate_add_apply- Iterating a function m + n times equals iterating it m times after n iterations: f^[m + n](x) = f^[m](f^[n](x)).
Function.iterate_fixed- Iterating a function any number of times on a fixed point leaves it fixed: if f(x) = x, then f^[n](x) = x.
Function.iterate_succ_apply'- The (n + 1)-st iterate of a function satisfies f^[n + 1](x) = f(f^[n](x)).
Nat.zero_mul- Zero times any natural number is zero: 0 * n = 0.
Function.iterate_zero_apply- Zero iterations of a function is the identity function: f^[0](x) = x.
Nat.succ_mul- Successor multiplication on the left: (n + 1) * m = n * m + m.
Nat.sub_pos_of_lt- If m < n, then n - m > 0.
tournament_reverse_arc_iter_mul_cycle- If x is periodic with period d (f^[d](x) = x), then iterating f any multiple m * d times also fixes x: f^[m * d](x) = x.
Nat.sub_add_cancel- If m ≤ n, then (n - m) + m = n.
Nat.left_distrib- Left distributivity of multiplication over addition: n * (m + k) = n * m + n * k.
Nat.mul_comm- Multiplication of natural numbers is commutative: n * m = m * n.
Nat.mul_one- Multiplying a natural number by one on the right gives the number: n * 1 = n.
lt_of_lt_of_le- Transitivity of strict and non-strict inequality: if a < b and b ≤ c, then a < c.
Fintype.card_fin- The cardinality of Fin n is n.
Nat.lt_succ_self- Every natural number is strictly less than its successor: n < n + 1.
Fintype.not_injective_of_card_lt- By the pigeonhole principle, any function between finite types where the target has strictly smaller cardinality cannot be injective.
Fin.ext- Two elements of Fin n are equal if and only if their underlying natural values are equal.
lt_or_gt_of_ne- In a linear order, if two elements are distinct, then one is strictly less than the other.
tournament_reverse_arc_iter_reach_root_lt_aux- If all orbits under p on Fin n reach v in n steps, and the orbit of w repeats between steps a < b ≤ n, then p^[a](w) = v.
Nat.le_of_lt_succ- If m < n + 1, then m ≤ n.
tournament_reverse_arc_iter_reach_root_lt- In any functional digraph on Fin n converging to a root v in n steps, every vertex reaches v in strictly fewer than n steps.
tournament_reverse_arc_iter_eq_or_eq_u- For the modified map p' where both u and v map to u, the k-th iterate on any vertex either equals the k-th iterate under p or has reached u.
tournament_reverse_arc_iter_ge- Once a fixed point x of f is reached at iteration a, any larger number of iterations b ≥ a also yields x.
Nat.succ_le_of_lt- If n < m, then n + 1 ≤ m.
le_of_lt- If a < b, then a ≤ b.
digraph_arborescence_count_at_through- The count of arborescences rooted at r using arc a → b, defined as the number of parent functions p with p(r) = r, p(a) = b, edges in the graph, and reaching r in n steps.
Finset.mem_filter- An element belongs to a filtered set if and only if it belongs to the ambient set and satisfies the predicate.
Finset.mem_univ- Every element of a finite type belongs to its universal finset.
true_and- Propositional conjunction with True simplifies: (True ∧ p) ↔ p.
if_pos- An if-then-else expression evaluates to the 'then' branch when the condition is true.
if_neg- An if-then-else expression evaluates to the 'else' branch when the condition is false.
Ne.symm- Inequality is symmetric: if a ≠ b, then b ≠ a.
Or.inr- Introduction rule for disjunction on the right: if B holds, then A ∨ B holds.
Or.inl- Introduction rule for disjunction on the left: if A holds, then A ∨ B holds.
tournament_reverse_arc_p'_iter_n_eq_u- In an arborescence rooted at v reaching v in n steps, modifying parent pointers so that both u and v map to u results in all orbits reaching u in n steps.
Finset.card_bij'- A function between two finite sets that has a two-sided inverse on those sets is a bijection, so the sets have equal cardinality.
- In the auxiliary lemma tournament_reverse_arc_iter_reach_root_lt_aux (line 41), the arithmetic relation b = d + a is discharged by the omega tactic.
- The proof formalizes an arborescence rooted at r via a parent pointer function p satisfying p(r) = r and p^[n](w) = r for all w, ensuring that every vertex reaches the root in at most n steps without cycles.
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.
lemma tournament_reverse_arc_iter_ge {α : Type*} (f : α → α) (x : α) (h : f x = x) {a b : ℕ} (hab : a ≤ b) {w : α} (hw : f^[a] w = x) : f^[b] w = x := by obtain ⟨k, rfl⟩ := Nat.exists_eq_add_of_le hab rw [Nat.add_comm, Function.iterate_add_apply, hw, Function.iterate_fixed h k]lemma tournament_reverse_arc_iter_eq_or_eq_u {n : ℕ} (p : Fin n → Fin n) (u v : Fin n) (w : Fin n) (k : ℕ) : let p' : Fin n → Fin n := fun x => if x = u then u else if x = v then u else p x p'^[k] w = p^[k] w ∨ p'^[k] w = u := by intro p' induction k with | zero => left; rfl | succ k ih => rw [Function.iterate_succ_apply', Function.iterate_succ_apply'] cases ih with | inr h => right have hp'u : p' u = u := by simp [p'] rw [h, hp'u] | inl h => rw [h] dsimp [p'] split_ifs with h1 h2 · right; rfl · right; rfl · left; rfllemma tournament_reverse_arc_iter_mul_cycle {α : Type*} (f : α → α) (x : α) (d : ℕ) (h : f^[d] x = x) (m : ℕ) : f^[m * d] x = x := by induction m with | zero => rw [Nat.zero_mul, Function.iterate_zero_apply] | succ m ih => rw [Nat.succ_mul, Function.iterate_add_apply, h, ih]lemma tournament_reverse_arc_iter_reach_root_lt_aux {n : ℕ} (p : Fin n → Fin n) (v : Fin n) (hpv : p v = v) (hpn : ∀ w, p^[n] w = v) (w : Fin n) (a b : ℕ) (hlt : a < b) (hble : b ≤ n) (heq : p^[b] w = p^[a] w) : ∃ c < n, p^[c] w = v := by let d := b - a have hdpos : 0 < d := Nat.sub_pos_of_lt hlt have hba : b = d + a := by omega have hfeq' : p^[d] (p^[a] w) = p^[a] w := by have h1 : p^[d + a] w = p^[a] w := by rwa [← hba] rwa [Function.iterate_add_apply] at h1 have hcycle : p^[n * d] (p^[a] w) = p^[a] w := tournament_reverse_arc_iter_mul_cycle p (p^[a] w) d hfeq' n have hnd : n * d = (d - 1) * n + n := by calc n * d = n * ((d - 1) + 1) := by rw [Nat.sub_add_cancel hdpos] _ = n * (d - 1) + n * 1 := Nat.left_distrib n (d - 1) 1 _ = (d - 1) * n + n := by rw [Nat.mul_comm n (d - 1), Nat.mul_one] have hreach : p^[n * d] (p^[a] w) = v := by rw [hnd, Function.iterate_add_apply, hpn, Function.iterate_fixed hpv] have hpav : p^[a] w = v := hcycle.symm.trans hreach exact ⟨a, lt_of_lt_of_le hlt hble, hpav⟩lemma tournament_reverse_arc_iter_reach_root_lt {n : ℕ} (p : Fin n → Fin n) (v : Fin n) (hpv : p v = v) (hpn : ∀ w, p^[n] w = v) (w : Fin n) : ∃ a < n, p^[a] w = v := by let f : Fin (n + 1) → Fin n := fun i => p^[i.val] w have hcard : Fintype.card (Fin n) < Fintype.card (Fin (n + 1)) := by simp only [Fintype.card_fin, Nat.lt_succ_self] have hninj := Fintype.not_injective_of_card_lt f hcard simp only [Function.Injective, not_forall] at hninj rcases hninj with ⟨i, j, hfeq, hne⟩ have hneval : i.val ≠ j.val := fun h => hne (Fin.ext h) rcases lt_or_gt_of_ne hneval with hlt | hgt · exact tournament_reverse_arc_iter_reach_root_lt_aux p v hpv hpn w i.val j.val hlt (Nat.le_of_lt_succ j.isLt) hfeq.symm · exact tournament_reverse_arc_iter_reach_root_lt_aux p v hpv hpn w j.val i.val hgt (Nat.le_of_lt_succ i.isLt) hfeqlemma tournament_reverse_arc_p'_iter_n_eq_u {n : ℕ} (p : Fin n → Fin n) (u v : Fin n) (hpv : p v = v) (hpn : ∀ w, p^[n] w = v) (w : Fin n) : let p' : Fin n → Fin n := fun x => if x = u then u else if x = v then u else p x p'^[n] w = u := by intro p' have hp'u : p' u = u := by simp [p'] have hp'v : p' v = u := by dsimp [p'] split_ifs with h1 h2 · rfl · rfl · exfalso; exact h2 rfl rcases tournament_reverse_arc_iter_reach_root_lt p v hpv hpn w with ⟨a, han, hpa⟩ have hor := tournament_reverse_arc_iter_eq_or_eq_u p u v w a change p'^[a] w = p^[a] w ∨ p'^[a] w = u at hor rcases hor with h1 | h2 · have hp'a1 : p'^[a + 1] w = u := by rw [Function.iterate_succ_apply', h1, hpa, hp'v] exact tournament_reverse_arc_iter_ge p' u hp'u (Nat.succ_le_of_lt han) hp'a1 · exact tournament_reverse_arc_iter_ge p' u hp'u (le_of_lt han) h2/-- In a tournament T with arc u → v, the number of arborescences rooted at v using u → v equals the number of arborescences of T' = reverse(T, u, v) rooted at u using v → u. -/theorem tournament_reverse_arc_through_root_endpoint_eq {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_at_through T v u v = digraph_arborescence_count_at_through (digraph_reverse_arc T u v) u v u := by have hne : u ≠ v := fun h => hT.1 v (h ▸ huv) rw [digraph_arborescence_count_at_through, digraph_arborescence_count_at_through] let s : Finset (Fin n → Fin n) := Finset.univ.filter (fun p => p v = v ∧ (∀ w, w ≠ v → T.Adj w (p w)) ∧ (∀ w, p^[n] w = v) ∧ p u = v) let t : Finset (Fin n → Fin n) := Finset.univ.filter (fun q => q u = u ∧ (∀ w, w ≠ u → (digraph_reverse_arc T u v).Adj w (q w)) ∧ (∀ w, q^[n] w = u) ∧ q v = u) change s.card = t.card let f : (Fin n → Fin n) → (Fin n → Fin n) := fun p x => if x = u then u else if x = v then u else p x let g : (Fin n → Fin n) → (Fin n → Fin n) := fun q x => if x = v then v else if x = u then v else q x have hfg : ∀ p ∈ s, g (f p) = p := by intro p hp simp only [s, Finset.mem_filter, Finset.mem_univ, true_and] at hp ext x dsimp [f, g] by_cases hx_v : x = v · rw [hx_v, if_pos rfl, hp.1] · rw [if_neg hx_v] by_cases hx_u : x = u · rw [hx_u, if_pos rfl, hp.2.2.2] · rw [if_neg hx_u, if_neg hx_u, if_neg hx_v] have hgf : ∀ q ∈ t, f (g q) = q := by intro q hq simp only [t, Finset.mem_filter, Finset.mem_univ, true_and] at hq ext x dsimp [f, g] by_cases hx_u : x = u · rw [hx_u, if_pos rfl, hq.1] · rw [if_neg hx_u] by_cases hx_v : x = v · rw [hx_v, if_pos rfl, hq.2.2.2] · rw [if_neg hx_v, if_neg hx_v, if_neg hx_u] have hfst : ∀ p ∈ s, f p ∈ t := by intro p hp simp only [s, Finset.mem_filter, Finset.mem_univ, true_and] at hp simp only [t, Finset.mem_filter, Finset.mem_univ, true_and] refine ⟨?_, ?_, ?_, ?_⟩ · dsimp [f]; rw [if_pos rfl] · intro w hw by_cases hwv : w = v · rw [hwv] have hfpv : f p v = u := by dsimp [f]; rw [if_neg (Ne.symm hne), if_pos rfl] rw [hfpv] rw [if_pos (Or.inr ⟨rfl, rfl⟩)] exact huv · have hfpw : f p w = p w := by dsimp [f]; rw [if_neg hw, if_neg hwv] rw [hfpw] have hcond : ¬ (w = u ∧ p w = v ∨ w = v ∧ p w = u) := by intro | Or.inl h => exact hw h.1 | Or.inr h => exact hwv h.1 rw [if_neg hcond] exact hp.2.1 w hwv · intro w exact tournament_reverse_arc_p'_iter_n_eq_u p u v hp.1 hp.2.2.1 w · dsimp [f]; rw [if_neg (Ne.symm hne), if_pos rfl] have hgts : ∀ q ∈ t, g q ∈ s := by intro q hq simp only [t, Finset.mem_filter, Finset.mem_univ, true_and] at hq simp only [s, Finset.mem_filter, Finset.mem_univ, true_and] refine ⟨?_, ?_, ?_, ?_⟩ · dsimp [g]; rw [if_pos rfl] · intro w hw by_cases hwu : w = u · rw [hwu] have hgqu : g q u = v := by dsimp [g]; rw [if_neg hne, if_pos rfl] rw [hgqu] exact huv · have hgqw : g q w = q w := by dsimp [g]; rw [if_neg hw, if_neg hwu] rw [hgqw] have hqadj := hq.2.1 w hwu have hcond : ¬ (w = u ∧ q w = v ∨ w = v ∧ q w = u) := by intro | Or.inl h => exact hwu h.1 | Or.inr h => exact hw h.1 rwa [if_neg hcond] at hqadj · intro w exact tournament_reverse_arc_p'_iter_n_eq_u q v u hq.1 hq.2.2.1 w · dsimp [g]; rw [if_neg hne, if_pos rfl] exact Finset.card_bij' (fun p hp => f p) (fun q hq => g q) hfst hgts (fun p hp => hfg p hp) (fun q hq => hgf q hq)