Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The 4/3 conjecture for n≥6n \ge 6n≥6 cities

Open
MetricTSP.four_thirds_conjecture_of_six_le

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

held-karpintegrality-gapopen-problemtraveling-salesman

For every n≥6n \ge 6n≥6 and every metric cost function ccc on nnn cities (symmetric, zero on the diagonal, satisfying the triangle inequality; distinct cities may be at distance 000), the optimal tour costs at most 43\frac4334​ times the Held--Karp bound:

OPT(c)  ≤  43 LP(c),\mathrm{OPT}(c) \;\le\; \tfrac{4}{3}\, \mathrm{LP}(c),OPT(c)≤34​LP(c),

where OPT(c)\mathrm{OPT}(c)OPT(c) is the minimum cost of a tour through all nnn cities and LP(c)\mathrm{LP}(c)LP(c) is the optimum of the subtour-elimination relaxation. This is four_thirds_conjecture with n≥3n \ge 3n≥3 replaced by n≥6n \ge 6n≥6, and the two are equivalent: for 3≤n≤53 \le n \le 53≤n≤5 the subtour LP is exact (OPT≤LP\mathrm{OPT} \le \mathrm{LP}OPT≤LP) and LP≥0\mathrm{LP} \ge 0LP≥0 because metric costs are nonnegative, so the content of the conjecture lies entirely in n≥6n \ge 6n≥6. The worst-case ratio OPT/LP\mathrm{OPT}/\mathrm{LP}OPT/LP first exceeds 111 at n=6n = 6n=6, where it is 109\frac{10}{9}910​. Benoit and Boyd (2008) computed the exact worst-case ratio by computer for every n≤10n \le 10n≤10, which confirms the conjecture in that range, but the statement remains open in general.

Preamble
import Mathlib
import Definitions.Def_MetricTSP_model
Formal statement
namespace MetricTSP

theorem four_thirds_conjecture_of_six_le (n : ℕ) (hn : 6 ≤ n)
    (c : Fin n → Fin n → ℝ) (hc : IsMetricCost c) :
    tspOpt c ≤ 4 / 3 * hkValue c := by sorry

end MetricTSP
Source
Restriction of the 4/3 conjecture (`four_thirds_conjecture`; Goemans, Worst-case comparison of valid inequalities for the TSP, Math. Programming 69 (1995) 335-349). Small-n computations: 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; Cook--Hougardy--Petrich, Extending exact integrality gap computations for the metric TSP, arXiv:2603.12995 (2026), https://arxiv.org/abs/2603.12995

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