Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of the equivalence, pp. 327–328 — a feasible x has no cycle avoiding city 0 (all tours include city 0)

Proved
MillerTuckerZemlin.Formulation.no_subtour_avoiding_base

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

integer-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1subtour-eliminationtraveling-salesman

Let (x,u)(x,u)(x,u) be feasible for problem (2) of Miller, Tucker and Zemlin, with parameter p≥0p\ge 0p≥0. Then there is no cycle of arcs among the non-base cities: there are no k≥0k\ge 0k≥0 and cities r0,…,rkr_0,\dots,r_kr0​,…,rk​, all different from 000, such that

xr0r1=xr1r2=⋯=xrk−1rk=xrkr0=1.x_{r_0r_1}=x_{r_1r_2}=\cdots=x_{r_{k-1}r_k}=x_{r_kr_0}=1 .xr0​r1​​=xr1​r2​​=⋯=xrk−1​rk​​=xrk​r0​​=1.

This is the paper's conclusion "Thus all tours include city 0": following the successors r1,r2,…r_1,r_2,\dotsr1​,r2​,… from an arc out of city 000 must return to 000, since the alternative is reaching a repeated city rk=rjr_k=r_jrk​=rj​, i.e. a cycle avoiding 000. The statement here excludes every such cycle of the feasible xxx, which is what makes every arc of xxx lie on a tour through 000.

Formalization Note The cycle is a map rrr from Z/(k+1)\mathbb Z/(k+1)Z/(k+1) to the cities, so rk+1=r0r_{k+1}=r_0rk+1​=r0​. The page argues for the cycle met while following successors from city 000; its argument uses only that the rrr's are nonzero and that the arcs carry x=1x=1x=1, so the statement is made for every such cycle. The case k=0k=0k=0 (a loop) is excluded by xii=0x_{ii}=0xii​=0.

Preamble
import Mathlib
import Definitions.Def_MillerTuckerZemlin_Formulation_Model
Formal statement
namespace MillerTuckerZemlin.Formulation

theorem no_subtour_avoiding_base (n p : ℕ) (x : Fin (n + 1) → Fin (n + 1) → ℕ)
    (u : Fin (n + 1) → ℝ) (hx : Feasible n p x u) (k : ℕ) (r : Fin (k + 1) → Fin (n + 1))
    (hr : ∀ i, r i ≠ 0) : ¬ ∀ i : Fin (k + 1), x (r i) (r (i + 1)) = 1 := by sorry

end MillerTuckerZemlin.Formulation
Source
Miller, Tucker, Zemlin, Integer Programming Formulation of Traveling Salesman Problems, J. ACM 7(4) (1960), pp. 327–328, proof of the equivalence, "Consider any x_{r_0 r_1} = 1 (r_1 ≠ 0)" … "Thus all tours include city 0"
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

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