digraph_arborescence_count_through
def
through(D, a → b): the number of spanning arborescences of D, over all choices of root, that use the arc a → b.
Statement
def digraph_arborescence_count_through {n : ℕ} (D : Digraph (Fin n)) [DecidableRel D.Adj] (a b : Fin n) : ℕ- Source
- step towards tournament_not_near_regular_exists_improving_tournament
- Verified
- 27 Oct 2026
- Axioms
- none listed
- Built on 1
- 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…
- Used by 3
- 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…
- 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…
- digraph_arborescence_count_through_sanitythrough(D, a → b) vanishes when a → b is not an arc of D, never exceeds tau(D), and on the two-vertex complete digraph the arc 0 → 1 lies…
Lean source view module on GitHub
/-- Total number of arborescences of D (summed over all roots) that use the arc a → b. -/ def digraph_arborescence_count_through {n : ℕ} (D : Digraph (Fin n)) [DecidableRel D.Adj] (a b : Fin n) : ℕ := ∑ r, digraph_arborescence_count_at_through D r a b