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