= Solution
The two pieces of a <one-tree> can be optimized independently. Compute a <minimum spanning tree> $F$ on vertices $\{2,\ldots,n\}$ and choose the two cheapest distinct edges incident to vertex one. Return their union.
Every feasible <one-tree> contains such a <spanning tree> and such a pair, so its cost is at least the sum of these two independent minima. Their union is itself feasible, attaining that <lower bound>. This proves optimality.
Use <Prim's algorithm> for $F$: repeatedly add a cheapest edge crossing from the current tree to an unvisited vertex. The <minimum spanning tree cut property> makes each chosen edge safe. With the dense weight <matrix> of a complete graph, maintain the best connection to each unvisited vertex and select the least one by a scan. There are $n-2$ iterations with $O(n)$ work apiece. A further scan finds the two cheapest incident edges. Thus the total complexity is $\boxed{O(n^2)}$, with $O(n)$ additional working storage beyond the input <matrix>.
Back to article page
