AFTD Auto-Formalizing Theoretical Domains

digraph_arborescence_count

def

tau(D): the total number of arborescences of D, the sum of a_r(D) over all roots r.

Statement

def digraph_arborescence_count {n : ℕ} (D : Digraph (Fin n)) [DecidableRel D.Adj] : ℕ
Defined in
arXiv:2610.25886 (Extremal arborescences in graph orientations), Conjecture 6.1; tau(D) of Sec. 1
Verified
20 Oct 2026
Axioms
none listed
Built on 1
  • digraph_arborescence_count_ata_r(D): the number of spanning arborescences of D directed towards the root r. Each is recorded by its successor map p: p r = r, every…
Used by 5

Lean source view module on GitHub

/-- tau(D): the total number of arborescences of D, the sum of a_r(D) over all roots r. -/
def digraph_arborescence_count {n : ℕ} (D : Digraph (Fin n)) [DecidableRel D.Adj] : ℕ := ∑ r, digraph_arborescence_count_at D r
See it in the graphDiscuss this resultChallenge it