Number of spanning trees in a subgraph

Question

A spanning tree of a connected graph is identified with any acyclic subgraph that contains all vertices of this graph. How to formally prove or where to find a proof that any subgraph of a connected graph contains equal or less numer of spanning trees than the original graph ?

Answer 1

In general, the combinatorial strategy to prove that $|X| \le |Y|$ is to find an injective function from $X$ to $Y$.

In this case, you have a subgraph $H$ of a connected graph $G$; to prove that $G$ has at least as many spanning trees as $H$, you want to find an injective function which turns spanning trees of $H$ into spanning trees of $G$.

Given a spanning tree $T$ of $H$, we can extend it to a spanning tree of $G$ as follows. For as long as $T$ is not a spanning tree of $G$ (that is, for as long as it does not contain the vertices of $G$) we can make $T$ larger by

1. Picking an arbitrary vertex $v$ of $G$ which is not yet in $T$.
2. Finding the shortest path from $v$ to $T$, ending at a vertex $w$ in $T$.
3. Creating a larger tree $T'$ consisting of the tree $T$ and the $v,w$-path found in step 2.

Repeat this with the new tree $T'$ until you have a tree that spans all the vertices of $G$.

You should check that (a) this process is always possible to carry out, (b) it always ends with a spanning tree of $G$, and (c) if we start with different spanning trees of $H$, we are guaranteed to end up with different spanning trees of $П$.

(Statement (c) is necessary to guarantee that the function we construct is injective, which is vital to get the inequality we want.)

Answer 2

Another way to prove that is to use the well-known recursive formula for $t(G)$ (number of spanning trees of graph $G$) $$ t(G) = t(G\backslash e) + t(G|e) \,, $$ where $e$ is an arbitrary edge of $G$, $G\backslash e$ is subgraph of $G$ obtained by removing edge $e$ and $G|e$ is graph obtained from $G$ by contracting edge $e$ (proof is quite simple).

It follows that $t(G\backslash e) < t(G)$, and then we can use induction on number of subgraph's edges to infer the general inequality you asked for.