Lemma 10.9: the minimum spanning tree is a lower bound,
ProvedSupplyChainTheory.mst_lower_boundlower-boundsoperations-researchspanning-treestraveling-salesman
Lemma 10.9. Let be a minimum spanning tree on the nodes of a TSP instance satisfying the triangle inequality. Then : the total length of the tree is at most the length of the optimal tour.
Removing any edge from the optimal tour leaves a spanning path, which is a spanning tree of length at most (the removed edge has nonnegative length), and the minimum spanning tree is no longer than that path. The lemma is the source of the MST-based heuristics and of the Held-Karp bound.
Preamble
import Definitions.Def_SupplyChainTheory_tsp
Formal statement
open Classical
namespace SupplyChainTheory
theorem mst_lower_bound {n : ℕ} (c : Fin n → Fin n → ℝ) (hc : IsMetric c) (hn : 1 ≤ n)
(T : SimpleGraph (Fin n)) (hT : IsMST c T) : graphWeight c T ≤ 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. 430-431, Sect. 10.4.6, Lemma 10.9 and its proof
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.