4
$\begingroup$

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

Using proof by contradiction, how would you go about this?

  • 0
    The same question using a proof by induction was asked [here](http://math.stackexchange.com/questions/195666/graph-theory-and-forests).2013-04-12

2 Answers 2

5

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.

0

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