Theorem 10.10 (Euler): a connected graph has an Eulerian tour iff every node has even degree
ProvedSupplyChainTheory.euler_tour_iffTheorem 10.10. An undirected, connected graph has an Eulerian tour, a closed walk that traverses every edge exactly once, if and only if every node has even degree.
The book omits the proof. Necessity is the observation that a closed walk enters and leaves each node equally often; sufficiency is Hierholzer's construction, splicing closed trails until all edges are used. This is the fact that turns a doubled spanning tree, or a tree plus a perfect matching on its odd nodes, into a closed walk through all the nodes, which the MST and Christofides heuristics then shortcut.
Formalization Note Stated for Mathlib simple graphs on a finite vertex type; the doubled trees of the heuristics are handled through their walks in the other items.
import Definitions.Def_SupplyChainTheory_tsp
open Classical
namespace SupplyChainTheory
theorem euler_tour_iff {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)
[DecidableRel G.Adj] (hG : G.Connected) :
(∀ v, Even (G.degree v)) ↔ ∃ (v : V) (p : G.Walk v v), p.IsEulerian := by sorry
end SupplyChainTheory
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.