# Graph Theory: Forests

Prove that a graph with $n$ vertices and $m$ components and $n-m$ edges is a forest.

-
The same question using a proof by induction was asked here. – Douglas S. Stones Apr 12 '13 at 19:13

Assume that there is a cycle with $k$ edges. The graph on the entire vertex set containing only the edges of that cycle has $n-k+1$ components. Adding each of the remaining $n-m-k$ edges can only decrease the number of components by at most $1$, so after adding them all there are still at least $(n-k+1)-(n-m-k)=m+1$ components left.

-

Do you already know that a connected graph is a tree if and only if it has $n$ vertices and $n-1$ edges? If so, let the components of $G$ be $C_1,\dots,C_m$, with $n_1,\dots,n_m$ vertices respectively. If some $C_k$ had fewer than $n_k-1$ edges, it wouldn’t be connected: if you start with $n_k$ disconnected vertices and add one edge at a time, each edge reduces the number of components by at most $1$, so you need at least $n_k-1$ edges to connect all $n_k$ vertices. Thus, each $C_k$ has at least $n_k-1$ edges.

Now assume that some component is not a tree; renumber the components, if necessary, so that $C_1$ is not a tree. Then $C_1$ has more than $n_1-1$ edges, and $G$ therefore has at least

$$n_1+\sum_{k=2}^m(n_k-1)=n_1+\left(\sum_{k=2}^mn_k\right)-(m-1)=n-m+1$$

edges, contradiction the hypothesis that it has $n-m$ edges. Thus, every component must be a tree, and $G$ must be a forest.

(Note that the heart of this argument $-$ the proof that a connected graph with $k$ vertices must have at least $k-1$ edges $-$ uses exactly the same idea as Joriki’s proof.)

-