Showing that graph of spanning trees are connected Suppose we have a graph $H$, where each vertex represents a spanning tree of another graph $G$.

We create an edge between 2 vertices in $H$ if $ST_1$ (spanning tree) contains exactly one edge not in $ST_2$ (and vice versa).

How do we show that $H$ is connected?
Use induction on the number of edges and vertices in $G$.  Fix some edge $e$ of $G$.  If $S$ and $T$ are two different spanning trees that do not use $e$, apply the induction hypothesis on the graph $G\setminus e$.  If both use $e$, apply the inductive hypothesis to the contracted graph $G/e$.  If only one does, w.l.o.g., $S$, replace $T$ by $T'$, obtained by adding $e$ to $T$ and removing any edge in the (unique) cycle in $T+e$.  Either $T'$ is $S$, or we are back in a previous case.