§3, p. 93 — the convex hull of nonnegative integer solutions of (3.6) is the polyhedron of (3.2) and (3.5)
ProvedChinesePostman.Polyhedron.postman_polyhedronLet be a finite graph with node set and edge set , where parallel edges are allowed and each edge meets two different nodes. Let be the parity of the degree of node ; is an odd node when . An edge meets a set when exactly one of its ends lies in , and is an odd set when it contains an odd number of odd nodes.
Let be the set of vectors with
((3.1), (3.2), (3.6)), and let be the polyhedron
((3.2), (3.5)). Then
Both inclusions are asserted, and the equality is of subsets of ; in particular the convex hull of is already closed. The vectors in are the numbers of extra traversals of the edges in postman tours, so the theorem describes the Chinese postman problem as a linear program.
Formalization Note The odd sets range over all subsets with an odd number of odd nodes, with no nonemptiness or properness restriction (both are automatic). Points of are real images of integer vectors.
import Mathlib import Definitions.Def_ChinesePostman_Polyhedron_Setting
namespace ChinesePostman.Polyhedron
theorem postman_polyhedron {V E : Type} [Fintype V] [DecidableEq V] [Fintype E] [DecidableEq E]
(G : Graph V E) :
convexHull ℝ (parityPoints G) = postmanPolyhedron G := by sorry
end ChinesePostman.Polyhedron
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.