If we are given randomly selected edges, we are not guaranteed that removing one such edge will produce a minimum spanning tree (note that there may be multiple MSTs for a graph). We are simply guaranteed that it is a spanning tree of minimal weight given the edges.

In Euclidean space, we can model the graph as . I will start with vertex and take the edge with maximum weight incident to . I then go to the vertex on the other side of the edge, call it and pick its largest edge not incident to . I continue this process such that no vertex on an iteration picks an edge incident to a vertex selected from any previous iteration. We are left with a spanning tree. Now for , pick the edge incident to and we have a cycle. Remove the edge on this cycle with the maximum weight. We have a spanning tree that is clearly not minimal.