BEST theorem — Euler tours
ProvedHararySachs.Hyper.best_theoremThis is the BEST theorem (de Bruijn–van Aardenne-Ehrenfest–Smith–Tutte, Theorem 5 of the paper), counted as Euler tours with a distinguished first arc.
Let be a directed multigraph on with arc multiplicities (loops allowed) and arcs in total, where parallel arcs are distinguishable. Suppose is Eulerian: its set of vertices of positive degree is nonempty, for every , and is weakly connected. Let be the number of spanning arborescences of oriented toward the least vertex of , with parallel arcs distinguished. Then the number of Euler tours of , i.e. closed trails using every arc exactly once with a distinguished first position, is
Equivalently, since each Euler circuit gives tours, , which is the BEST theorem. Combined with Lemma 4, it yields Corollary 6, the closed form used in the proof of Lemma 13.
Formalization Note Tours are the mission's numTours: bijections from positions Fin L onto the labeled arcs Arcs m, such that the head of each arc is the tail of the next, cyclically. The arborescence count is numArb, which encodes trees by parent maps weighted by the product of arc multiplicities. In-degree is used in the factorials, as in the mission's associated coefficient; in an Eulerian digraph it equals out-degree.
import Mathlib import Definitions.Def_HararySachs_Hyper_Operators
namespace HararySachs.Hyper
theorem best_theorem {n L : ℕ} (hL : 0 < L) (m : ArcMult n)
(hm : (∑ u : Fin n, ∑ v : Fin n, m u v) = L) (hEu : IsEulerian m) :
numTours m hL =
L * numArb m * ∏ v ∈ active m, Nat.factorial (inDeg m v - 1) := by sorry
end HararySachs.Hyper