Statement

Proof

The problem is in the correct form for a search problem. It outputs a MST always as one always exists from the definition.

To verify a solution as we can first check it is a spanning tree by running BFS to verify it is connected and checking the size of the edge set is $\vert V \vert - 1$ to check it is a tree. To check it is minimal we can find a solution in polynomial time using Kruskal’s algorithm. We can just check it’s weight vs the weight of the proposed solution to check they match.