combinatoricsgraph theorytrees
Concerning trees in graph theory:
How many trees does a forest with $n$ vertices and $m$ edges contain?
This has to do with combinatorics apparently but I'm struggling with these assignments since we skipped that topic.
I'm thinking it's related to $m-1$ or $n-1$ something.
We create a bipartite graph. In one part we have the $n^{n-2}$ labeled spanning trees of $K_n$, and in the other part we have the $\binom{n}{2}$ edges in $K_n$, and we draw an edge between two vertices whenever a tree contains an edge. It'll looks something like the image below:
Trees have $n-1$ edges, so the degree of every tree vertex in the above graph is $n-1$. By symmetry, every edge in $K_n$ belongs to the same number of trees, say $d$, which is also the degree of any edge vertex in the above graph. Hence the number of edges in the above graph is $$n^{n-2} (n-1)=d \binom{n}{2}$$ which implies that $$d=\frac{n^{n-2} (n-1)}{\binom{n}{2}}=2n^{n-3}.$$
The number of trees that contain a given edge is $d$, so the number of trees that don't contain that edge is $$n^{n-2}-d=n^{n-3}(n-2).$$ This is also the number of labeled spanning trees of $K_n \setminus \{e\}$.
You can think of each connected component as a graph by itself and talk about its associated spanning trees.
What it is saying is that you build a spanning forest by choosing a spanning tree from each connected component, therefore the number of trees in a spanning forest is the same as the number of connected components.
Best Answer
First picture $n$ vertices with no edges. Then add the missing edges. Every time we add an edge, we combine two trees into one (as its vertices cannot come from the same tree - prove this). Therefore we end up with $n-m$ trees.