BEST theorem — for balanced multidigraphs
ProvedBESTTheorem.card_euler_toursBEST theorem (van Aardenne-Ehrenfest–de Bruijn–Smith–Tutte), labelled-arc counting form, for an arbitrary finite multidigraph.
Let be a finite set of arcs and a finite set of vertices. Each arc has a tail and a head ; loops and parallel arcs are allowed. Write for the number of arcs with tail . Assume the multidigraph is balanced: every vertex has as many incoming arcs as outgoing arcs. Fix a root with at least one out-arc.
An Euler tour is a bijection with for every . It is a closed walk using every arc exactly once, recorded together with its starting position, so each cyclic Euler circuit is counted times.
Let be the set of vertices with . Let be the number of spanning arborescences oriented toward , counted with arc multiplicities. That is, is the sum over parent maps that satisfy
- for every , and
- every reaches by iterating ,
of the product . Then
where for vertices with no arcs.
Connectivity is not assumed. If the arcs do not form one weakly connected piece, both sides are . As a corollary, does not depend on the choice of root .
import Mathlib open Finset Classical
namespace BESTTheorem
theorem card_euler_tours {V A : Type*} [Fintype V] [DecidableEq V] [Fintype A] [DecidableEq A]
(tl hd : A → V) (hN : 0 < Fintype.card A)
(hbal : ∀ v, (univ.filter (fun a => hd a = v)).card = (univ.filter (fun a => tl a = v)).card)
(r : V) (hr : ∃ a, tl a = r) :
Fintype.card {σ : Fin (Fintype.card A) ≃ A // ∀ t : Fin (Fintype.card A),
hd (σ t) = tl (σ ⟨(t.val + 1) % Fintype.card A, Nat.mod_lt _ hN⟩)} =
Fintype.card A *
(∑ p : V → V,
if (∀ v, ¬(0 < (univ.filter (fun a => tl a = v)).card ∧ v ≠ r) → p v = v) ∧
(∀ v, 0 < (univ.filter (fun a => tl a = v)).card → v ≠ r → ∃ k, p^[k] v = r) then
∏ v ∈ univ.filter (fun v => 0 < (univ.filter (fun a => tl a = v)).card ∧ v ≠ r),
(univ.filter (fun a => tl a = v ∧ hd a = p v)).card
else 0) *
∏ v, ((univ.filter (fun a => tl a = v)).card - 1).factorial := by sorry
end BESTTheorem