Given a minimum spanning tree T of a connected graph with distinct edge weights, give an O(V^2) algorithm for the second best spanning tree and prove that it differs from T by exactly one edge swap.

Given a minimum spanning tree T of a connected graph with distinct edge weights, give an O(V^2) algorithm for the second best spanning tree and prove that it differs from T by exactly one edge swap.

Approach: Show first that some optimal second best tree shares all but one edge with T, then search over the single swap by precomputing the heaviest edge on every tree path.

Precompute the maximum weight edge on the tree path between every pair, then take the edge swap minimising w(e) - maxPath(e), which is O(V^2). The structure claim follows from an exchange argument. Let T' be a second best tree and take an edge f of T' outside T. Adding f to T closes one cycle, and letting g be the heaviest T edge on that cycle other than f, the tree T - g + f is spanning and heavier than T, so it is a candidate. Any tree differing from T in two or more edges is at least as heavy as one of these single swap trees, so a one-swap tree attains the optimum, and distinct weights make it strictly heavier than T. For the algorithm, run a search from every vertex over T propagating the tree path maximum as the larger of the parent value and the edge just crossed, which fills the table in O(V^2). Then scan every non-tree edge e = (u,v) and take the minimum of w(e) - maxPath(u,v), a pass costing O(E) that the table build dominates.

Follow-up: How would you answer the same question online as edge weights change one at a time?

Key concepts: edge swap, tree path maximum, exchange argument, second best.