# Forests in Graph Theory

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!

• Hint: First think about how many edges are in a tree with $n$ vertices. Then think about what happens when you remove an edge. Use induction. – Jair Taylor Apr 11 '18 at 7:28
• I'd also recommend just drawing out examples of forests and trying to find a pattern. – Jair Taylor Apr 11 '18 at 7:29

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$.