Choosing spanning trees to maximise node connectivity
My suggestion would be to try simulated annealing.  This looks like a good candidate for that heuristic.  It sounds like you have some idea what the objective function you want to minimize is (that's good; you need one).

I would suggest that you use simulated annealing as follows:


A state is a possible graph (a set of edges).
The cost function for a state might be your objective function plus some penalty for the number of $C_i$'s that aren't fully connected.
To transition between states, you might randomly choose among the following options:


Add an edge chosen at random (or: choose a $C_i$ that isn't fully connected, and add a randomly chosen edge between some pair of variables $C_i$ that aren't currently in the same connected component)
Delete an edge chosen at random
Pick an existing edge $(u,v)$, delete the edge, then randomly choose some other variable $w$ that is in the same connected component as $v$ and add the edge $(u,w)$.



but of course you can play around with it and try different variations to see which works the best.  This might just give you some reasonable solutions.



You could also try formulating this as a SAT or ILP instance, but my sense is that I would try simulated annealing first.  If you're lucky, it just might work well enough that you don't need to bother with anything else.