Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

No integrality gap up to five cities: OPT≤LP\mathrm{OPT} \le \mathrm{LP}OPT≤LP for n≤5n \le 5n≤5

Proved
MetricTSP.tspOpt_le_hkValue_of_le_five

by SamenHossain · Oct 13, 2026 · Mathlib 0df444a (Lean v4.33.1)

held-karpintegrality-gappolyhedral-combinatoricssmall-casestraveling-salesman

For every nnn with 3≤n≤53 \le n \le 53≤n≤5 and every metric cost function ccc on nnn cities (symmetric, zero on the diagonal, satisfying the triangle inequality), the optimal tour cost is at most the Held--Karp bound: OPT(c)≤LP(c)\mathrm{OPT}(c) \le \mathrm{LP}(c)OPT(c)≤LP(c). Together with held_karp_le_opt this gives OPT(c)=LP(c)\mathrm{OPT}(c) = \mathrm{LP}(c)OPT(c)=LP(c), so the subtour-elimination relaxation has no integrality gap on at most five cities. This also follows from a classical polyhedral fact: for n≤5n \le 5n≤5 the subtour-elimination polytope equals the convex hull of the tour incidence vectors, so equality holds for arbitrary symmetric edge costs, not only metric ones. For n≥6n \ge 6n≥6 the tour polytope is strictly contained in the subtour-elimination polytope, and Benoit--Boyd computed the exact metric integrality gap for every n≤10n \le 10n≤10.

Preamble
import Mathlib
import Definitions.Def_MetricTSP_model
Formal statement
namespace MetricTSP

theorem tspOpt_le_hkValue_of_le_five (n : ℕ) (hn : 3 ≤ n) (hn5 : n ≤ 5)
    (c : Fin n → Fin n → ℝ) (hc : IsMetricCost c) :
    tspOpt c ≤ hkValue c := by sorry

end MetricTSP
Source
Classical: the subtour-elimination polytope equals the symmetric TSP polytope for n≤5n \le 5n≤5 and is strictly larger for n≥6n \ge 6n≥6, as stated in Letchford, Separating a superclass of comb inequalities in planar graphs, Math. Oper. Res. 25(3) (2000) 443-454, https://doi.org/10.1287/moor.25.3.443.12213, who attributes it to Grötschel--Padberg (1979); see Grötschel--Padberg, On the symmetric travelling salesman problem I: Inequalities and II: Lifting theorems and facets, Math. Programming 16 (1979) 265-280 and 281-302, https://doi.org/10.1007/BF01582116, https://doi.org/10.1007/BF01582117; exact gaps for n≤10n \le 10n≤10: Benoit--Boyd, Finding the exact integrality gap for small traveling salesman problems, Math. Oper. Res. 33(4) (2008) 921-931, https://doi.org/10.1287/moor.1080.0337

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