If given a connected graph G, split the graph into Ga and Gb. If you find a minimum spanning tree for Ga and Gb (called Xa and Xb, respectively), does connecting Xa to Xb with a minimal weighted edge still form a spanning tree? Is that spanning tree a minimum spanning tree?
This is my logic so far. I believe that connecting Xa to Xb would form at least a spanning tree almost by definition. (If there is a counterxample though that'd be helpful) However, I don't think it would always form a minimum spanning tree because depending on the structure of the graph, you may be able to remove an edge from Xa or Xb, then add the edge connecting them, and still have a tree. This may be the case in a situation where multiple edges of the same weight connect Xa and Xb at different vertexes.
Is my logic correct so far?
It's correct, that you don't always get a minimal spanning tree by just connecting Xa and Xb. But it is not necessary, that the edges connecting Xa and Xb have the same weight. See the following example:
Assume you have the following Graph G:
A-B-C-D
| | | |
E-F-G-H
Edge (B,C) hast cost 1 and (F,G) has cost 2, all other edges have cost 10.
Then you divide it in Ga and Gb:
A-B C-D
| | | |
E-F G-H
Minimum spanning trees Xa and Xb are:
A-B C-D
| |
E-F G-H
If you now connect them with the minimal possible edge you get a spanning tree with cost 61:
A-B-C-D
| |
E-F G-H
But that's not a minimal spanning tree. A minimal spanning tree (with costs 53) would be
A-B-C-D
|
E-F-G-H