AFTD Auto-Formalizing Theoretical Domains

tournament_reverse_arc_through_lt_iff_arborescence_lt

theoremverified

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

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

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

    line 8

    uses digraph_arborescence_count_reverse_arc_add_through

      have h := digraph_arborescence_count_reverse_arc_add_through T hT u v huv
  2. through(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).

    line 9

      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

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