Recursive minimal spanning tree algorithms

Question

Is this a right algorithm for finding minimal spanning tree.

Divide Graph into 2 equally connected parts. Find its minimal spanning trees. Connect them using the smallest edge that connects them. I am trying to get counterexample of this algorithm, but can't.

Answer 1

Consider a four-node graph, connected in a square, with the left edge having cost 10 and all other edges having cost 1. If you divide the graph into left and right for your recursive step, you will end up with a spanning tree of cost 12, instead of cost 3.

MST is not well-adapted to "divide-and-conquer" algorithms. The closest thing is probably the Reverse-Delete algorithm; whenever you fail to remove an edge (because it would disconnect the graph), you can think of the remaining steps as executing recursively on the two sides of that edge.