How can I check if a given spanning tree is a MST?

Suppose we are given a graph G and a spanning tree T of it. How can we check that if this spanning tree is a MST or not?

I suggest that for each edge i that is not in T, all edges j on the unique path of T from one end of i to the other end, we must have w_i >= w_j

Solution

You want to check that for each edge (u, v) not in the MST, the path from u to v in the MST has no edge with weight larger than that of (u, v). For a single vertex in the tree, you can use a single BFS or DFS to find the largest-weight edge on the path to all other nodes, so this gives an O(n²) algorithm (n times O(n) search). You can probably do better by not starting from scratch for each vertex. That said, it may be more efficient to just calculate an MST and see if the sum of all edge weights is the same. As mentioned by @Niklas in the comments, there are linear time methods for verifying an MST, but they seem to be significantly more involved.