Minimum Spanning Tree problem is in NP

Statement

Lemma

Minimum Spanning Tree problem (MST) is in NP

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 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.