Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Eqs. (2.13)–(2.17): shortest paths between the named nodes of Fi+1F_{i+1}Fi+1​

Proved
TSPHeuristics.NNLower.shortest_paths_F_succ

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

p2o-batch-p100ap2o-gran-per-chapterp2o-plan-paperp2o-v1shortest-pathtraveling-salesman

Let i≥1i\ge1i≥1 and let A,B,C,D,E,F,GA,B,C,D,E,F,GA,B,C,D,E,F,G be the nodes of Fi+1F_{i+1}Fi+1​ named in Fig. 1: AAA, BBB, CCC the start, middle and right node of the left copy of FiF_iFi​, DDD the new middle node, and EEE, FFF, GGG the start, middle and right node of the right copy. Write XY‾\overline{XY}XY for the length of a shortest path between XXX and YYY in Fi+1F_{i+1}Fi+1​. Then

(2.13)AB‾=BC‾=EF‾=FG‾=li−1,(2.14)AC‾=EG‾=li+1−2,(2.15)BE‾=DF‾=li,(2.16)AD‾=DG‾=li+1−1,(2.17)AG‾=li+2−2.\begin{aligned} &(2.13)\quad \overline{AB}=\overline{BC}=\overline{EF}=\overline{FG}=l_i-1,\\ &(2.14)\quad \overline{AC}=\overline{EG}=l_{i+1}-2,\\ &(2.15)\quad \overline{BE}=\overline{DF}=l_i,\\ &(2.16)\quad \overline{AD}=\overline{DG}=l_{i+1}-1,\\ &(2.17)\quad \overline{AG}=l_{i+2}-2. \end{aligned}​(2.13)AB=BC=EF=FG=li​−1,(2.14)AC=EG=li+1​−2,(2.15)BE=DF=li​,(2.16)AD=DG=li+1​−1,(2.17)AG=li+2​−2.​

These identities are the induction that establishes properties a) and b) of Gˉi\bar G_iGˉi​.

Formalization Note With s=2i+1−1s=2^{i+1}-1s=2i+1−1 the number of nodes of FiF_iFi​: A=0A=0A=0, B=2i−1B=2^i-1B=2i−1, C=s−1C=s-1C=s−1, D=sD=sD=s, E=s+1E=s+1E=s+1, F=s+2iF=s+2^iF=s+2i, G=2sG=2sG=2s. Distances are taken in Fi+1F_{i+1}Fi+1​ (not Gi+1G_{i+1}Gi+1​).

Preamble
import Mathlib
import Definitions.Def_TSPHeuristics_NNLower_ShortestPathMetric
import Definitions.Def_TSPHeuristics_NNLower_LowerBoundFamily
Formal statement
namespace TSPHeuristics.NNLower

/-- Eqs. (2.13)–(2.17), p. 569: in `F_{i+1}` (for `i ≥ 1`), with the nodes of Fig. 1
`A = 0`, `B = middle i`, `C = s − 1`, `D = s`, `E = s + 1`, `F = s + 1 + middle i`, `G = 2 s`
(`s = numNodes i`), the shortest-path distances are
`AB = BC = EF = FG = l_i − 1`, `AC = EG = l_{i+1} − 2`, `BE = DF = l_i`,
`AD = DG = l_{i+1} − 1`, `AG = l_{i+2} − 2`. -/
theorem shortest_paths_F_succ (i : ℕ) (hi : 1 ≤ i) :
    let s := numNodes i
    let A := 0
    let B := middle i
    let C := s - 1
    let D := s
    let E := s + 1
    let F := s + 1 + middle i
    let G := 2 * s
    let dF := spDist (edgesF (i + 1))
    (dF A B = ell i - 1 ∧ dF B C = ell i - 1 ∧ dF E F = ell i - 1 ∧ dF F G = ell i - 1) ∧
    (dF A C = ell (i + 1) - 2 ∧ dF E G = ell (i + 1) - 2) ∧
    (dF B E = ell i ∧ dF D F = ell i) ∧
    (dF A D = ell (i + 1) - 1 ∧ dF D G = ell (i + 1) - 1) ∧
    dF A G = ell (i + 2) - 2 := by sorry

end TSPHeuristics.NNLower
Source
Rosenkrantz, Stearns, Lewis, An Analysis of Several Heuristics for the Traveling Salesman Problem, SIAM J. Comput. 6(3), 1977, https://doi.org/10.1137/0206041, p. 569, eqs. (2.13)–(2.17)
Read-back

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

Setting. Fix a natural number i≥1i \ge 1i≥1 and write s=ni=2i+1−1s = n_i = 2^{i+1} - 1s=ni​=2i+1−1. Fi+1F_{i+1}Fi+1​ is the recursively defined edge list on nodes 0,…,2s0,\dots,2s0,…,2s. It consists of:

  • FiF_iFi​ on nodes 0,…,s−10,\dots,s-10,…,s−1;
  • a copy of FiF_iFi​ shifted by s+1s+1s+1;
  • the edges (s−1,s,1)(s-1,s,1)(s−1,s,1), (s,s+1,1)(s,s+1,1)(s,s+1,1), (s, s+1+mi, ℓi)(s,\ s+1+m_i,\ \ell_i)(s, s+1+mi​, ℓi​) and (mi, s+1, ℓi)(m_i,\ s+1,\ \ell_i)(mi​, s+1, ℓi​), where mi=2i−1m_i = 2^i - 1mi​=2i−1 and ℓj=4⋅2j−(−1)j+36\ell_j = \dfrac{4\cdot 2^j - (-1)^j + 3}{6}ℓj​=64⋅2j−(−1)j+3​.

Write ddd for the shortest-path distance spFi+1\mathrm{sp}_{F_{i+1}}spFi+1​​: the infimum of total weights of walks in Fi+1F_{i+1}Fi+1​, with edges in either direction. It is 000 when no walk exists or costs are unbounded below.

Named nodes.

LabelNode
AAA000
BBB2i−12^i - 12i−1
CCCs−1s - 1s−1
DDDsss
EEEs+1s+1s+1
FFFs+2is + 2^is+2i
GGG2s2s2s

Claim. All of the following equalities hold simultaneously:

d(A,B)=d(B,C)=d(E,F)=d(F,G)=ℓi−1,d(A,B) = d(B,C) = d(E,F) = d(F,G) = \ell_i - 1,d(A,B)=d(B,C)=d(E,F)=d(F,G)=ℓi​−1, d(A,C)=d(E,G)=ℓi+1−2,d(A,C) = d(E,G) = \ell_{i+1} - 2,d(A,C)=d(E,G)=ℓi+1​−2, d(B,E)=d(D,F)=ℓi,d(B,E) = d(D,F) = \ell_i,d(B,E)=d(D,F)=ℓi​, d(A,D)=d(D,G)=ℓi+1−1,d(A,D) = d(D,G) = \ell_{i+1} - 1,d(A,D)=d(D,G)=ℓi+1​−1, d(A,G)=ℓi+2−2.d(A,G) = \ell_{i+2} - 2.d(A,G)=ℓi+2​−2.

Each distance is taken in the order written. The claim concerns distances in Fi+1F_{i+1}Fi+1​, not in the augmented list Gi+1G_{i+1}Gi+1​.

Degenerate cases. The case i=0i = 0i=0 is excluded. For i≥1i \ge 1i≥1 we have s≥3s \ge 3s≥3, so C=s−1C = s-1C=s−1 involves no truncated subtraction, and the seven labels name seven distinct nodes.

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