Stumbled upon this question in a practice problem set:
Suppose graph $G$ is a forest with $n$ vertices, $m$ edges and $T$ trees. Express $m$ in terms of $n$ and $T$.
I know that a simple graph is $G=(V,E)$, but I don't know where to go from here.
Any tips would be appreciated!
Consider a forest $G$ of $n = 10$ vertices and $m$ edges and $t = 3$ trees (say $T_1, T_2, T_3$). We want to solve for $m$.
To do this, we construct a new graph $G'$ from $G$ by drawing an edge from $T_1$ to $T_2$ and drawing an edge from $T_2$ to $T_3$. Observe that $G'$ now has $n' = 10$ vertices and $m' = m + 2$ edges but only $t' = 1$ tree (can you see why $G'$ is connected and acyclic?). It follows that $m' = 9$ so that $m = 7$.
Can you see how to generalize this argument?