§6, pp. 115–118 — every connected, even, symmetric mixed graph has an Euler tour
ProvedChinesePostman.Mixed.mixed_euler_tourLet be a finite mixed graph (some edges directed, some undirected; parallel edges allowed; no loops) that is
- connected when the directions on the edges are ignored;
- even: every node meets an even number of edges, regardless of direction;
- symmetric: every node has as many edges directed away from it as directed toward it.
Then for every node there is an Euler tour of starting and ending at :
This is the main result of §6: the paper's algorithm first assigns directions to enough undirected edges and then traces the tour by its Rule. For graphs with only undirected edges it gives Euler's theorem for connected even multigraphs; for graphs with only directed edges, the classical theorem for connected balanced digraphs.
Formalization Note The tour must respect directions: a tour of the underlying undirected multigraph is not enough. The single-node graph without edges is allowed, and its one-node tour is the Euler tour.
import Mathlib import Definitions.Def_ChinesePostman_Mixed_Setting
namespace ChinesePostman.Mixed
/-- §6, pp. 115–118: every connected, even, symmetric mixed graph has an Euler tour, starting at
any prescribed node `r`, that traverses every directed edge in its direction. -/
theorem mixed_euler_tour {V E : Type} [Fintype V] [DecidableEq V] [Fintype E]
[DecidableEq E] (G : MixedGraph V E) (hconn : G.Connected) (heven : G.IsEven)
(hsym : G.IsSymmetric) (r : V) :
∃ ns es, G.IsMixedEulerTour ns es ∧ ns.head? = some r := by sorry
end ChinesePostman.Mixed
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.