Past exam of the integer programming course of the University of Oxford / 2010 / 1 / a

The two pieces of a one-tree can be optimized independently. Compute a minimum spanning tree $F$ on vertices $\{2,\dots ,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.