Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3.2.1 — integrality of the bipartite perfect-matching LP relaxation

Proved
MatousekLP.Integrality.perfect_matching_lp_integral

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

bipartite-graphinteger-programminglinear-programmingmatchingp2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1

Let G=(V,E)G = (V, E)G=(V,E) be an arbitrary finite bipartite graph with real edge weights wew_ewe​ (of any sign). Consider the LP relaxation of the perfect-matching integer program (3.1):

maximize ∑e∈Ewexesubject to ∑e∈E: v∈exe=1 (v∈V),0≤xe≤1 (e∈E).\text{maximize } \sum_{e \in E} w_e x_e \quad \text{subject to } \sum_{e \in E:\, v \in e} x_e = 1 \ (v \in V), \quad 0 \le x_e \le 1 \ (e \in E).maximize e∈E∑​we​xe​subject to e∈E:v∈e∑​xe​=1 (v∈V),0≤xe​≤1 (e∈E).

If this LP relaxation has at least one feasible solution, then it has at least one integral optimal solution xxx, i.e. xe∈{0,1}x_e \in \{0,1\}xe​∈{0,1} for every edge and ∑ewexe≥∑eweye\sum_e w_e x_e \ge \sum_e w_e y_e∑e​we​xe​≥∑e​we​ye​ for every feasible yyy of the relaxation. This xxx is an optimal solution for the integer program (3.1) as well.

The theorem says that a maximum-weight perfect matching of a bipartite graph can be found by solving a linear program. It does not assert that every optimal solution of the relaxation is integral.

Formalization Note The conclusion is a vector xxx feasible for (3.1) (hence 0/1) that is optimal among all feasible points of the relaxation, and also, explicitly, among all feasible points of (3.1).

Preamble
import Mathlib
import Definitions.Def_MatousekLP_Integrality_BipartiteGraph
import Definitions.Def_MatousekLP_Integrality_PerfectMatchingLP
Formal statement
namespace MatousekLP.Integrality

theorem perfect_matching_lp_integral {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (hG : IsBipartite G) (w : G.edgeSet → ℝ)
    (hfeas : ∃ x : G.edgeSet → ℝ, IsPMRelaxFeasible G x) :
    ∃ x : G.edgeSet → ℝ, IsPMIntFeasible G x ∧
      (∀ y : G.edgeSet → ℝ, IsPMRelaxFeasible G y → pmObjective G w y ≤ pmObjective G w x) ∧
      (∀ y : G.edgeSet → ℝ, IsPMIntFeasible G y → pmObjective G w y ≤ pmObjective G w x) := by sorry

end MatousekLP.Integrality
Source
Matoušek & Gärtner, Understanding and Using Linear Programming, Springer 2007, p. 34, Theorem 3.2.1 (integer program (3.1): p. 33)
Human review
  • Endorsed by Shuze Chen · Oct 5, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 5, 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