Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2.3 — N(G) is exactly the solution set of the nonnegativity, edge, and odd hole constraints

Proved
LovaszSchrijver.OddHole.NG_eq_odd_hole_system

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

lift-and-projectodd-holep2o-batch-p100bp2o-gran-per-chapterp2o-plan-paperp2o-v1stable-set-polytope

Let G=(V,E)G = (V, E)G=(V,E) be a finite graph with no isolated nodes, and let N(G)={x∈RV:(1,x)∈N(FR(G))}N(G) = \{x \in \mathbb{R}^V : (1, x) \in N(\mathrm{FR}(G))\}N(G)={x∈RV:(1,x)∈N(FR(G))} be the relaxation of the stable set polytope obtained by one round of the Lovász–Schrijver operator NNN applied to the fractional stable set polytope FRAC(G)\mathrm{FRAC}(G)FRAC(G). Then N(G)N(G)N(G) is exactly the set of x∈RVx \in \mathbb{R}^Vx∈RV satisfying

  1. the nonnegativity constraints xi≥0x_i \ge 0xi​≥0 for each i∈Vi \in Vi∈V;
  2. the edge constraints xi+xj≤1x_i + x_j \le 1xi​+xj​≤1 for each ij∈Eij \in Eij∈E;
  3. the odd hole constraints: for every set C⊆VC \subseteq VC⊆V inducing a chordless odd cycle in GGG,
∑i∈Cxi≤12(∣C∣−1).\sum_{i \in C} x_i \le \tfrac12(|C| - 1).i∈C∑​xi​≤21​(∣C∣−1).

The theorem characterizes completely the constraints obtained in one step of the NNN operator without positive semidefiniteness: one round of NNN on FRAC(G)\mathrm{FRAC}(G)FRAC(G) adds exactly the odd hole constraints. In particular N(G)=STAB(G)N(G) = \mathrm{STAB}(G)N(G)=STAB(G) for every ttt-perfect graph.

Formalization Note Odd holes include triangles (∣C∣=3|C| = 3∣C∣=3) and exclude cycles with chords. The graph is assumed to have no isolated nodes, the paper's standing assumption in Section 2.a.

Preamble
import Mathlib
import Definitions.Def_LovaszSchrijver_OddHole_MatrixCone
import Definitions.Def_LovaszSchrijver_OddHole_StableSetCones
import Definitions.Def_LovaszSchrijver_OddHole_OddHole
Formal statement
namespace LovaszSchrijver.OddHole

/-- Theorem 2.3 (p. 178): for a finite graph `G` with no isolated nodes, the polytope `N(G)` is
exactly the solution set of the nonnegativity, edge, and odd hole constraints. -/
theorem NG_eq_odd_hole_system {V : Type} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (hG : ∀ v, ∃ w, G.Adj v w) :
    NG G = {x : V → ℝ | (∀ i, 0 ≤ x i) ∧ (∀ i j, G.Adj i j → x i + x j ≤ 1) ∧
      ∀ C : Finset V, IsOddHole G C → ∑ i ∈ C, x i ≤ ((C.card : ℝ) - 1) / 2} := by sorry

end LovaszSchrijver.OddHole
Source
Lovász and Schrijver, Cones of matrices and set-functions and 0–1 optimization, SIAM J. Optim. 1(2) (1991), p. 178, Theorem 2.3
Read-back

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

Fix VVV, any finite type with decidable equality (the vertices), and a simple graph GGG on VVV: no loops, symmetric adjacency, adjacency decidable. Assume GGG has no isolated vertices:

∀v∈V, ∃w∈V: v∼Gw.\forall v \in V,\ \exists w \in V:\ v \sim_G w.∀v∈V, ∃w∈V: v∼G​w.

The statement asserts a set equality between two subsets of RV\mathbb{R}^VRV, the real-valued functions x:V→Rx : V \to \mathbb{R}x:V→R.

Left side. The left side is N(G)N(G)N(G), written NG G in the code. It is defined in the imported module Def_LovaszSchrijver_OddHole_StableSetCones, which is not included here. The theorem depends on that definition exactly as written, and this read-back cannot unfold it. The module name suggests that N(G)N(G)N(G) is built from cones related to stable sets. The auditor must check the definition's actual content separately.

Right side. The right side is the set of all x∈RVx \in \mathbb{R}^Vx∈RV that satisfy all three of the following families of constraints:

  1. Nonnegativity: xi≥0x_i \ge 0xi​≥0 for every i∈Vi \in Vi∈V.
  2. Edge constraints: xi+xj≤1x_i + x_j \le 1xi​+xj​≤1 for every ordered pair (i,j)(i,j)(i,j) with i∼Gji \sim_G ji∼G​j.
  3. Odd-hole constraints: for every finite vertex subset C⊆VC \subseteq VC⊆V with IsOddHole(G,C)\mathrm{IsOddHole}(G, C)IsOddHole(G,C),
∑i∈Cxi  ≤  ∣C∣−12.\sum_{i \in C} x_i \;\le\; \frac{|C| - 1}{2}.i∈C∑​xi​≤2∣C∣−1​.

Here ∣C∣|C|∣C∣ is converted to a real number before 111 is subtracted and the result is divided by 222. There is no natural-number truncation and no integer division.

The predicate IsOddHole\mathrm{IsOddHole}IsOddHole comes from the imported module Def_LovaszSchrijver_OddHole_OddHole, also not included. The constraint applies to exactly those vertex sets CCC that this predicate accepts, and to no others. A hole is presumably a chordless cycle, but the code does not say so, so the auditor should verify it. The code does not state whether the predicate requires any minimum size for CCC (for example ∣C∣≥5|C| \ge 5∣C∣≥5 or ∣C∣≥3|C| \ge 3∣C∣≥3), whether it requires ∣C∣|C|∣C∣ to be odd, or whether it requires the induced subgraph to be a chordless cycle.

The theorem asserts N(G)={right side}N(G) = \{\text{right side}\}N(G)={right side} as sets. This means containment in both directions: every point of N(G)N(G)N(G) satisfies all three constraint families, and every point satisfying them lies in N(G)N(G)N(G).

Degenerate cases. If VVV is empty, the hypothesis of no isolated vertices is vacuously true. The right side is then all of R∅\mathbb{R}^{\emptyset}R∅, a single point. The only possible CCC is ∅\emptyset∅, and if IsOddHole(G,∅)\mathrm{IsOddHole}(G,\emptyset)IsOddHole(G,∅) held, the bound would read 0≤−120 \le -\tfrac120≤−21​, which is false. So the theorem claims N(G)N(G)N(G) is that single point, unless the odd-hole predicate accepts the empty set, in which case it claims N(G)=∅N(G) = \emptysetN(G)=∅.

If VVV has exactly one vertex, the hypothesis cannot be satisfied, because a simple graph has no loops. The theorem is then vacuous.

In general, the hypothesis forces every vertex to have at least one neighbour, so ∣V∣≥2|V| \ge 2∣V∣≥2 whenever VVV is non-empty.

The odd-hole bound uses real division, so no default values arise from it. Whether it can ever be applied to a set CCC with ∣C∣≤1|C| \le 1∣C∣≤1, giving the right-hand side 000 or −12-\tfrac12−21​, depends entirely on the unseen definition of IsOddHole\mathrm{IsOddHole}IsOddHole. If GGG has no sets satisfying IsOddHole\mathrm{IsOddHole}IsOddHole, the third family is empty. The claim then reduces to N(G)N(G)N(G) being exactly the nonnegativity-plus-edge polytope.

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