In trying to understand the combinatorial structure of spanning trees, we can consider the...

In trying to understand the combinatorial structure of spanning trees, we can consider the space of all possible spanning trees of a given graph and study the properties of this space. This is a strategy that has been applied to many similar problems as well.

Here is one way to do this. Let G be a connected graph, and T and Tʹ two different spanning trees of G. We say that T and T’ are neighbors if T contains exactly one edge that is not in T’, and T’ contains exactly one edge that is not in T.

Now, from any graph G, we can build a (large) graph  as follows. The nodes of  are the spanning trees of G, and there is an edge between two nodes of  if the corresponding spanning trees are neighbors.

Is it true that, for any connected graph G, the resulting graph H is connected? Give a proof that H is always connected, or provide an example (with explanation) of a connected graph G for which H is not connected.