Subscribe to the weekly news from TrueShelf

## Minimum-weight spanning path

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.

0

0

0

0

0

0

0

0
0

0