Many MST's can be found by partitioning a graph, finding the MST of each "half", and then connecting the two halves together in the least expensive way.
I am asked to provide a counter example to disprove this algorithm. Here's what I came up with: 
I thought, well this can't be partitioned vertically or horizontally to make the algorithm work, but then I realized it could be partitioned vertically along the left-most "box" to make the partitioning algorithm work. I tried thinking of some other polygons to use as examples but always ran into the same problem. I also asked a friend in class, and he couldn't come up with anything either.
Does a graph exist that fully disproves this algorithm, such that not a single partition can be made to successfully find the MST? If so, what's an example?
Best Answer
Given a cheapest spanning tree, surely one can always come up with a good partition post facto by picking an edge of the spanning tree and partitioning into the vertex sets of the two subtrees obtained by deleting that edge. Of course, if we don't know the spanning tree ahead of time, this is not very practical -- but it does suggest you need to be more specific about what algorithm it is you're trying to defeat, because you need to exploit something specific about how the algorithm finds a partition. (Alternatively, the point might just be that not every partition works, in which case it suffices to find one partition that doesn't give an MST in the whole graph, as you did in your example.)