AFTD Auto-Formalizing Theoretical Domains

tournament_reverse_arc_through_root_endpoint_eq

theoremverified

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'.

  1. 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.

    lines 3–4

    uses Nat.exists_eq_add_of_le, Nat.add_comm, Function.iterate_add_apply, Function.iterate_fixed

      obtain ⟨k, rfl⟩ := Nat.exists_eq_add_of_le hab
      rw [Nat.add_comm, Function.iterate_add_apply, hw, Function.iterate_fixed h k]
  2. 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).

    lines 10–26

    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
  3. 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.

    lines 30–33

    uses Nat.zero_mul, Function.iterate_zero_apply, Nat.succ_mul, Function.iterate_add_apply

      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]
  4. 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.

    lines 39–53

    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_le

      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⟩
  5. 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.

    lines 58–67

    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_succ

      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) hfeq
  6. 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.

    lines 73–88

    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_lt

      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
  7. 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.

    line 95

      have hne : u ≠ v := fun h => hT.1 v (h ▸ huv)
  8. 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.

    lines 96–103

    uses digraph_arborescence_count_at_through

      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
  9. 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.

    lines 104–114

    uses Finset.mem_filter, Finset.mem_univ, if_neg, if_pos, true_and

      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]
  10. 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.

    lines 115–125

    uses Finset.mem_filter, Finset.mem_univ, if_neg, if_pos, true_and

      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]
  11. 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.

    lines 126–147

    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_and

      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]
  12. 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.

    lines 148–168

    uses Finset.mem_filter, Finset.mem_univ, Or.inl, Or.inr, if_neg, if_pos, tournament_reverse_arc_p'_iter_n_eq_u, true_and

      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]
  13. 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.

    lines 169–170

    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.

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

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)
See it in the graphDiscuss this resultChallenge it