Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 10.13 (Christofides): the tour returned by Christofides' heuristic satisfies zCH/z∗≤3/2z_{CH}/z^* \le 3/2zCH​/z∗≤3/2

Proved
SupplyChainTheory.christofides_bound

by naimengye · Sep 24, 2026 · Mathlib 0df444a (Lean v4.33.1)

approximationheuristicsmatchingsoperations-researchtraveling-salesman

Theorem 10.13. For every instance of the TSP that satisfies the triangle inequality,

zCHz∗  ≤  32,\frac{z_{CH}}{z^*} \;\le\; \frac{3}{2},z∗zCH​​≤23​,

where z∗z^*z∗ is the length of the optimal tour and zCHz_{CH}zCH​ the length of the tour returned by Christofides' heuristic (Algorithm 10.6): find a minimum spanning tree T∗T^*T∗, find a minimum-weight perfect matching MMM on the odd-degree nodes of T∗T^*T∗, take an Eulerian tour of the graph formed by the edges of T∗T^*T∗ and of MMM (an edge may appear in both), and shortcut it by visiting the nodes in order of first appearance.

The book's proof: z(T∗)≤z∗z(T^*) \le z^*z(T∗)≤z∗ by Lemma 10.9; the optimal tour restricted to the odd nodes by shortcutting has length at most z∗z^*z∗ and splits into two perfect matchings on those nodes, so z(M)≤12z∗z(M) \le \frac{1}{2} z^*z(M)≤21​z∗; the Eulerian tour has length z(T∗)+z(M)≤32z∗z(T^*) + z(M) \le \frac{3}{2}z^*z(T∗)+z(M)≤23​z∗, and shortcutting does not lengthen it. This is the best worst-case bound known for the metric TSP; Problem 10.13 shows it is tight, and Lemma 10.18 records that it holds even against the LP relaxation.

Formalization Note The graph T∗+MT^* + MT∗+M is a multigraph when a matching edge repeats a tree edge, so it is represented by its Eulerian walk: a closed walk in the complete graph whose edge multiset is the sum of the tree's and the matching's. Every MST, minimum matching, Eulerian tour and start node is covered.

Preamble
import Definitions.Def_SupplyChainTheory_tsp
Formal statement
open Classical

namespace SupplyChainTheory

theorem christofides_bound {n : ℕ} (c : Fin n → Fin n → ℝ) (hc : IsMetric c) (hn : 1 ≤ n)
    (T : SimpleGraph (Fin n)) (hT : IsMST c T) (M : Finset (Sym2 (Fin n)))
    (hM : IsMinMatchingOn c (oddNodes T) M) (v : Fin n) (W : (⊤ : SimpleGraph (Fin n)).Walk v v)
    (hW : (W.edges : Multiset (Sym2 (Fin n))) = T.edgeFinset.val + M.val)
    (τ : Equiv.Perm (Fin n)) (hτ : IsShortcut W.support τ) :
    tourLength c τ ≤ (3 / 2 : ℝ) * optTourLength c := by sorry

end SupplyChainTheory
Source
Lawrence V. Snyder and Zuo-Jun Max Shen, Fundamentals of Supply Chain Theory, 2nd ed., Wiley 2019, DOI 10.1002/9781119584445, pp. 433-435, Sect. 10.4.7, Theorem 10.13, Eq. (10.28)-(10.29), and its proof; Algorithm 10.6; after Christofides (1976)
Human review
  • Endorsed by Shuze Chen · Sep 25, 2026

    Confirmed by the moderator at approval.

  • Endorsed by naimengye · Sep 25, 2026

    Confirmed by the mission captain (proposal self-audit).

  • Endorsed by Community (Bot) · Oct 30, 2026

    Confirmed by the moderator at approval.

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