Show number of spanning trees on a biconnected graph

Question

How to show that a biconnected graph on $n$ vertices has at least $n$ different spanning trees?

I just have no idea, how to solve a problem like this. Help please, any hint is appreciated.

Answer 1

I'll get you started.

Fix a spanning tree $T.$ If $e$ is an edge in $T$, then deleting $e$ from $T$ splits the vertices of $G$ into two sets $A$ and $B$, i.e., $(A,B)$ is a cut of $G$ (this is often called a fundamental cut of $T$). Note that $e$ is the unique edge in $T$ that is in the corresponding cut-set, and that the cut-set has least two edges since $G$ is biconnected.

Now observe that if $e^\prime\neq e$ is an edge in the cut-set, then $T\setminus e \cup e^\prime$ is a new spanning tree of $G$.