Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 7.1 — the odd-cycle LP and its dual have zero–one optima on series-parallel networks

Proved
ChvatalPolytopes.SeriesParallel.odd_cycle_lp_zero_one_optima

by mikedeng1 · Sep 26, 2026 · Mathlib 0df444a (Lean v4.33.1)

graph-theorylinear-optimizationlp-dualityp2o-batch-p100ap2o-gran-per-chapterp2o-plan-paperp2o-v1series-parallelstable-set-polytope

Let G=(V,E)G=(V,E)G=(V,E) be a finite series-parallel network, i.e. a graph containing no homeomorph of K4K_4K4​. Consider the linear program

max⁡ ∑u∈Vxusubject to (7.1),\max\ \sum_{u\in V}x_u\quad\text{subject to (7.1)},max u∈V∑​xu​subject to (7.1),

where (7.1) is 0≤xu≤10\le x_u\le10≤xu​≤1 (u∈Vu\in Vu∈V), xv+xw≤1x_v+x_w\le1xv​+xw​≤1 (vw∈Evw\in Evw∈E), and ∑u∈Cxu≤12(∣C∣−1)\sum_{u\in C}x_u\le\tfrac12(|C|-1)∑u∈C​xu​≤21​(∣C∣−1) for every vertex set CCC inducing an odd circuit in GGG. Then both this problem and its linear programming dual have zero–one optimal solutions:

  1. there is a zero–one vector xxx satisfying (7.1) with ∑uxu≥∑uxu′\sum_u x_u\ge\sum_u x'_u∑u​xu​≥∑u​xu′​ for every real x′x'x′ satisfying (7.1);
  2. there is a zero–one dual feasible point (y,z,w)(y,z,w)(y,z,w) whose dual objective ∑uyu+∑eze+∑C12(∣C∣−1)wC\sum_u y_u+\sum_e z_e+\sum_C\tfrac12(|C|-1)w_C∑u​yu​+∑e​ze​+∑C​21​(∣C∣−1)wC​ is at most that of every real dual feasible point.

In particular the maximum of the relaxation equals the stability number α(G)\alpha(G)α(G), attained at a stable set, and a zero–one dual optimum certifies it by covering the vertices with vertices, edges and induced odd circuits.

Formalization Note The dual is the one fixed in the OddCycleLP definition file: x≥0x\ge0x≥0 as sign constraints, dual variables y≥0y\ge0y≥0 on vertices, z≥0z\ge0z≥0 on edges and w≥0w\ge0w≥0 on Z(G)Z(G)Z(G), and the covering constraint yu+∑e∋uze+∑C∋uwC≥1y_u+\sum_{e\ni u}z_e+\sum_{C\ni u}w_C\ge1yu​+∑e∋u​ze​+∑C∋u​wC​≥1. Optimality is against all real feasible points of the respective program, not only zero–one ones. The theorem does not assume VVV nonempty; for the empty graph both programs are trivial.

Preamble
import Mathlib
import Definitions.Def_ChvatalPolytopes_SeriesParallel_IsSeriesParallel
import Definitions.Def_ChvatalPolytopes_SeriesParallel_OddCycleLP
Formal statement
namespace ChvatalPolytopes.SeriesParallel

/-- **Theorem 7.1** (Chvátal 1975, p. 151). Let `G = (V, E)` be a series-parallel network. Then
both the problem of maximizing `∑ (x_u : u ∈ V)` subject to (7.1) and its linear programming dual
have zero–one optimal solutions.

(a) Some zero–one vector `x` satisfying (7.1) has `∑ x_u ≥ ∑ x'_u` for every *real* `x'`
satisfying (7.1).
(b) Some zero–one dual feasible `(y, z, w)` has dual objective at most that of every real dual
feasible point. The dual is the one of `DualFeasible`/`dualValue` (`0 ≤ x_u` as sign
constraints). -/
theorem odd_cycle_lp_zero_one_optima {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (hG : IsSeriesParallel G) :
    (∃ x : V → ℝ, (∀ u, x u = 0 ∨ x u = 1) ∧ OddCycleFeasible G x ∧
      ∀ x' : V → ℝ, OddCycleFeasible G x' → primalValue x' ≤ primalValue x) ∧
    (∃ (y : V → ℝ) (z : G.edgeSet → ℝ) (w : {C : Finset V // C ∈ oddCircuits G} → ℝ),
      (∀ u, y u = 0 ∨ y u = 1) ∧ (∀ e, z e = 0 ∨ z e = 1) ∧ (∀ C, w C = 0 ∨ w C = 1) ∧
      DualFeasible G y z w ∧
      ∀ (y' : V → ℝ) (z' : G.edgeSet → ℝ) (w' : {C : Finset V // C ∈ oddCircuits G} → ℝ),
        DualFeasible G y' z' w' → dualValue G y z w ≤ dualValue G y' z' w') := by sorry

end ChvatalPolytopes.SeriesParallel
Source
Chvátal, On certain polytopes associated with graphs, J. Combin. Theory Ser. B 18 (1975), p. 151, Theorem 7.1
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Let VVV be any finite type of vertices with decidable equality; it may be empty. Let GGG be a simple graph on VVV with a decidable adjacency relation. The one hypothesis is that GGG satisfies the predicate IsSeriesParallel(G)\mathrm{IsSeriesParallel}(G)IsSeriesParallel(G). This predicate comes from an imported definition that is not shown here, so what it requires cannot be stated from this code. The statement also uses five other imported, undisplayed notions:

  • OddCycleFeasible(G,x)\mathrm{OddCycleFeasible}(G, x)OddCycleFeasible(G,x): a property of a real vector x∈RVx \in \mathbb{R}^Vx∈RV that depends on GGG.
  • primalValue(x)\mathrm{primalValue}(x)primalValue(x): a real number computed from x∈RVx \in \mathbb{R}^Vx∈RV alone. It does not take GGG as an argument.
  • oddCircuits(G)\mathrm{oddCircuits}(G)oddCircuits(G): a collection of finite vertex subsets C⊆VC \subseteq VC⊆V. Let C\mathcal{C}C be the set of its members.
  • DualFeasible(G,y,z,w)\mathrm{DualFeasible}(G, y, z, w)DualFeasible(G,y,z,w): a property of a triple y∈RVy \in \mathbb{R}^Vy∈RV, z∈RE(G)z \in \mathbb{R}^{E(G)}z∈RE(G) (one real per edge of GGG), w∈RCw \in \mathbb{R}^{\mathcal{C}}w∈RC (one real per member of C\mathcal{C}C).
  • dualValue(G,y,z,w)\mathrm{dualValue}(G, y, z, w)dualValue(G,y,z,w): a real number computed from the same triple.

None of these is unfolded here. Their meaning, including whether they encode an "odd cycle" linear program and its dual, rests entirely on their definitions. The theorem's doc comment describes them, but the read-back does not rely on that description.

Under this hypothesis, the theorem asserts the conjunction of two statements.

(a) Primal part. There exists a vector x∈RVx \in \mathbb{R}^Vx∈RV such that:

  • every coordinate satisfies xu∈{0,1}x_u \in \{0, 1\}xu​∈{0,1};
  • OddCycleFeasible(G,x)\mathrm{OddCycleFeasible}(G, x)OddCycleFeasible(G,x) holds;
  • for every real vector x′∈RVx' \in \mathbb{R}^Vx′∈RV with OddCycleFeasible(G,x′)\mathrm{OddCycleFeasible}(G, x')OddCycleFeasible(G,x′),
primalValue(x′)≤primalValue(x).\mathrm{primalValue}(x') \le \mathrm{primalValue}(x).primalValue(x′)≤primalValue(x).

So some 000–111 feasible vector attains the maximum of primalValue\mathrm{primalValue}primalValue over all real feasible vectors. In particular, that maximum exists.

(b) Dual part. There exist y∈RVy \in \mathbb{R}^Vy∈RV, z∈RE(G)z \in \mathbb{R}^{E(G)}z∈RE(G) and w∈RCw \in \mathbb{R}^{\mathcal{C}}w∈RC such that:

  • every entry of yyy, zzz and www lies in {0,1}\{0, 1\}{0,1};
  • DualFeasible(G,y,z,w)\mathrm{DualFeasible}(G, y, z, w)DualFeasible(G,y,z,w) holds;
  • for every real triple (y′,z′,w′)(y', z', w')(y′,z′,w′) of the same shapes with DualFeasible(G,y′,z′,w′)\mathrm{DualFeasible}(G, y', z', w')DualFeasible(G,y′,z′,w′),
dualValue(G,y,z,w)≤dualValue(G,y′,z′,w′).\mathrm{dualValue}(G, y, z, w) \le \mathrm{dualValue}(G, y', z', w').dualValue(G,y,z,w)≤dualValue(G,y′,z′,w′).

So some 000–111 dual-feasible triple attains the minimum of dualValue\mathrm{dualValue}dualValue over all real dual-feasible triples.

The two parts are independent existence claims. The statement does not assert that the optimal primal value equals the optimal dual value, and it does not relate xxx to (y,z,w)(y, z, w)(y,z,w) in any way.

Degenerate cases. Both parts are existence claims, so the theorem asserts that each feasible set is nonempty and contains a 000–111 point. It also asserts that primalValue\mathrm{primalValue}primalValue is bounded above and dualValue\mathrm{dualValue}dualValue is bounded below on those sets. It is never true merely because a feasible set is empty; the only route to vacuity is the hypothesis.

  • Empty VVV: xxx, yyy and zzz are the unique empty functions, and the 000–111 conditions on them hold trivially. Whether the theorem holds then depends only on the imported definitions: whether IsSeriesParallel\mathrm{IsSeriesParallel}IsSeriesParallel accepts the empty graph, whether the empty vector is feasible, and what the value functions return.
  • No edges: zzz ranges over the single empty function.
  • C\mathcal{C}C empty: www ranges over the single empty function.
  • The hypothesis: whether IsSeriesParallel(G)\mathrm{IsSeriesParallel}(G)IsSeriesParallel(G) holds for no graph or for only trivial ones, which would make the theorem vacuous or nearly so, cannot be determined from this code.
  • Default values of total functions: none appear in the statement itself. Any divisions, natural-number subtractions or other default-valued operations would sit inside the undisplayed definitions.
Human review
  • Endorsed by Shuze Chen · Sep 27, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Sep 27, 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