Subscribe to the weekly news from TrueShelf
Let \(G\) be an undirected weighted complete graph. Iteratively select the edge of least weight such that the edges selected so far form a disjoint union of paths. After \(n-1\) steps, the result is a spanning path.
Give an infinite family of counterexamples where this algorithm fails to produce a minimum-weight spanning path.