Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

BEST theorem — #Euler tours=N τr(G)∏v(d+(v)−1)!\#\text{Euler tours} = N\,\tau_r(G)\prod_v (d^+(v)-1)!#Euler tours=Nτr​(G)∏v​(d+(v)−1)! for balanced multidigraphs

Proved
BESTTheorem.card_euler_tours

by milia · Nov 12, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatoricsgraph-theory

BEST theorem (van Aardenne-Ehrenfest–de Bruijn–Smith–Tutte), labelled-arc counting form, for an arbitrary finite multidigraph.

Let AAA be a finite set of N≥1N \ge 1N≥1 arcs and VVV a finite set of vertices. Each arc aaa has a tail tl(a)\mathrm{tl}(a)tl(a) and a head hd(a)\mathrm{hd}(a)hd(a); loops and parallel arcs are allowed. Write d+(v)d^+(v)d+(v) for the number of arcs with tail vvv. Assume the multidigraph is balanced: every vertex has as many incoming arcs as outgoing arcs. Fix a root rrr with at least one out-arc.

An Euler tour is a bijection σ:{0,…,N−1}→A\sigma : \{0,\dots,N-1\} \to Aσ:{0,…,N−1}→A with hd(σ(t))=tl(σ(t+1 mod N))\mathrm{hd}(\sigma(t)) = \mathrm{tl}(\sigma(t+1 \bmod N))hd(σ(t))=tl(σ(t+1modN)) for every ttt. It is a closed walk using every arc exactly once, recorded together with its starting position, so each cyclic Euler circuit is counted NNN times.

Let SSS be the set of vertices v≠rv \ne rv=r with d+(v)>0d^+(v) > 0d+(v)>0. Let τr\tau_rτr​ be the number of spanning arborescences oriented toward rrr, counted with arc multiplicities. That is, τr\tau_rτr​ is the sum over parent maps p:V→Vp : V \to Vp:V→V that satisfy

  • p(v)=vp(v) = vp(v)=v for every v∉Sv \notin Sv∈/S, and
  • every v∈Sv \in Sv∈S reaches rrr by iterating ppp,

of the product ∏v∈S#{a:tl(a)=v, hd(a)=p(v)}\prod_{v \in S} \#\{a : \mathrm{tl}(a) = v,\ \mathrm{hd}(a) = p(v)\}∏v∈S​#{a:tl(a)=v, hd(a)=p(v)}. Then

#{Euler tours}  =  N⋅τr⋅∏v∈V(d+(v)−1)!,\#\{\text{Euler tours}\} \;=\; N \cdot \tau_r \cdot \prod_{v \in V} \bigl(d^+(v) - 1\bigr)!,#{Euler tours}=N⋅τr​⋅v∈V∏​(d+(v)−1)!,

where (0−1)!=0!=1(0-1)! = 0! = 1(0−1)!=0!=1 for vertices with no arcs.

Connectivity is not assumed. If the arcs do not form one weakly connected piece, both sides are 000. As a corollary, τr\tau_rτr​ does not depend on the choice of root rrr.

Preamble
import Mathlib
open Finset Classical
Formal statement
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
Source
R. P. Stanley, Enumerative Combinatorics Vol. 2, Theorem 5.6.2 (BEST theorem); T. van Aardenne-Ehrenfest and N. G. de Bruijn, Circuits and trees in oriented linear graphs, Simon Stevin 28 (1951) 203–217; https://en.wikipedia.org/wiki/BEST_theorem

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me