= Minimum spanning tree
{title2=$\min_T\sum_{e\in T}c_e$}
= Minimum-weight spanning tree
{synonym}
A <minimum spanning tree> minimizes total edge weight among <spanning trees> of a connected weighted graph. It can be computed in polynomial time by repeatedly adding the least-weight edge joining two current components. The cut-exchange argument preserves the existence of an optimum containing every accepted edge. Removing an edge of a travelling-salesman tour gives a <spanning tree>, so its optimum is a lower bound on optimal tour cost.
Back to article page
