Prove that no graph has exactly $2$ spanning trees.

discrete-mathematics graph-theory

Then here is more detailed reasoning that there is no simple graph that has exactly two spanning trees.

  1. If a graph is not connected, then it has $0$ spanning trees.

  2. If the graph is connected and has no cycles then the graph is a tree. In this case the graph has exactly one spanning tree. This tree is the graph itself.

  3. If graph $G$ is connected and has cycles, then it has a spanning tree $T$, which is obtained by removing some edges of $G$. Let $e$ be an edge of graph $G$ which is not included in the tree $T$. Then the graph $T+e$ has exactly one cycle. This cycle has at least two more edges besides $e$. Let these edges be $e'$ and $e''$. Then $T'=T+e-e'$ and $T+e-e''$ are ostensive trees of $G$. Thus we have at least three different spanning trees $T$, $T'$, $T''$ of graph $G$.

Since any graph with non-empty set of vertices has one of these three types, we proved that there is no simple graph with exactly two spanning trees.

Related

How to integrate $\int_0^{\infty} \frac{x}{e^x+1} dx$
Conditions for null-homotopic chain map in a specific example
Solve for $f(x)$ if $f(f(x))=6x-f(x)$
What's the use of scaling here?
Help to find the solution of $y' = \begin{pmatrix}-2 & 1 \\1 &-2\end{pmatrix} \cdot y + \begin{pmatrix}2\sin(t) \\ 2(\cos(t) - \sin(t))\end{pmatrix}$
Example of a general random variable with finite mean but infinite variance
Residue Theorem and Complex analysis (cauchy residue theorem) [duplicate]
Solving $u_t+2u_x=0$
Eigenspace of Kronecker power of a 2*2 rotation matrix
Infinite number of points in the Sierpinski Triangle
What is $\lim\limits_{n\to\infty} (\text j_{x,x}-\text y_{x,x})$ with the BesselYZero and BesselJZero function?
Is the image of a Borel subset of $[0,1]$ under a differentiable map still a Borel set?