Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§3, p. 93 — the convex hull of nonnegative integer solutions of (3.6) is the polyhedron of (3.2) and (3.5)

Proved
ChinesePostman.Polyhedron.postman_polyhedron

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

chinese-postmanconvex-hullinteger-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1t-join-polyhedron

Let GGG be a finite graph with node set NNN and edge set EEE, where parallel edges are allowed and each edge meets two different nodes. Let bn∈{0,1}b_n\in\{0,1\}bn​∈{0,1} be the parity of the degree of node nnn; nnn is an odd node when bn=1b_n=1bn​=1. An edge meets a set S⊆NS\subseteq NS⊆N when exactly one of its ends lies in SSS, and SSS is an odd set when it contains an odd number of odd nodes.

Let X⊆REX\subseteq\mathbb R^EX⊆RE be the set of vectors xxx with

xe∈Z,xe≥0 (e∈E),∑e∈Eanexe≡bn(mod2) (n∈N),x_e\in\mathbb Z,\quad x_e\ge 0\ (e\in E),\qquad \sum_{e\in E}a_{ne}x_e\equiv b_n\pmod 2\ (n\in N),xe​∈Z,xe​≥0 (e∈E),e∈E∑​ane​xe​≡bn​(mod2) (n∈N),

((3.1), (3.2), (3.6)), and let P⊆REP\subseteq\mathbb R^EP⊆RE be the polyhedron

P={x:xe≥0 (e∈E),  ∑{xe:e meets S}≥1  for every odd set S}P=\Big\{x : x_e\ge 0\ (e\in E),\ \ \sum\{x_e : e\text{ meets }S\}\ge 1\ \text{ for every odd set } S\Big\}P={x:xe​≥0 (e∈E),  ∑{xe​:e meets S}≥1  for every odd set S}

((3.2), (3.5)). Then

conv⁡X=P.\operatorname{conv} X = P .convX=P.

Both inclusions are asserted, and the equality is of subsets of RE\mathbb R^ERE; in particular the convex hull of XXX is already closed. The vectors in XXX 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 S⊆NS\subseteq NS⊆N with an odd number of odd nodes, with no nonemptiness or properness restriction (both are automatic). Points of XXX are real images of integer vectors.

Preamble
import Mathlib
import Definitions.Def_ChinesePostman_Polyhedron_Setting
Formal statement
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
Source
Edmonds and Johnson, Matching, Euler tours and the Chinese postman, Math. Programming 5 (1973), p. 93 (statement), p. 94 (restated), pp. 94–96 (proof), §3, (3.2), (3.5), (3.6)
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

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