I have an MST and need to delete a node. I know that there's an algorithm for that in O(log^4(n)) but since the MST contains less than 50 nodes and 2500 edges and I have the edges sorted already, I wanted to us a more basic solution: I create a union for each connected component and run Kruskal on them to reconnect.
My reasoning is that this should work, because we have an MST and reconnect it through the cheapest way possible after deleting a node.
However, I didn't find anything that confirms that this works, so I wanted to double check here:
Is the resulting tree a minimal spanning tree among the remaining nodes and edges?
It works fine, but it's not as fast as O(log^4(n))
The proof that it works is easy: Using Kruskal's algorithm, an edge is selected iff its endpoints are not connected by any path through only cheaper/earlier edges.
Deleting a vertex and its edges does not create any new paths (it just removes paths), so any edge that was previously selected would still be selected if you ran the whole algorithm again.