Euler's criterion — a digraph has an Euler tour iff it is Eulerian
ProvedHararySachs.Hyper.numTours_pos_iffThis is Euler's criterion for directed multigraphs, in the form used in the proof of Lemma 4 of Clark and Cooper: a digraph has an Euler tour exactly when it is Eulerian.
Let be a directed multigraph on with distinguishable arcs from to (loops allowed) and arcs in total. Call Eulerian when the following hold, where is the set of vertices of positive degree:
- ;
- for every vertex ;
- any two vertices of are joined by a chain of arcs, each traversed in either direction.
Then
An Euler tour is a closed trail using every arc exactly once, with a distinguished first position.
The paper recalls this criterion on p. 5 before Lemma 4. It is the existence half of Lemma 4, and every Euler-circuit count, such as the BEST theorem, presupposes it.
Formalization Note The left-hand side is 0 < numTours m hL, the number of tour bijections Fin L ≃ Arcs m. Eulerian is the mission predicate IsEulerian m, with weak connectivity expressed by Relation.ReflTransGen (WeakAdjacent m) on active vertices.
import Mathlib import Definitions.Def_HararySachs_Hyper_Operators
namespace HararySachs.Hyper
theorem numTours_pos_iff {n L : ℕ} (hL : 0 < L) (m : ArcMult n)
(hm : (∑ u : Fin n, ∑ v : Fin n, m u v) = L) :
0 < numTours m hL ↔ IsEulerian m := by sorry
end HararySachs.Hyper