[Math] Forests and their number of components

graph theory

A simple graph $G=(V,E)$ is a forest iff the number of components is $|V|-|E|$.

Let $|V| = n$ and $|E| = k$.

$\Rightarrow$ How can I use the fact that a simple graph on $n$ vertices and $k$ edges has at least $n-k$ components (I actually have the proof of this)? Do we have equality since adding more edges forms a cycle?

For the converse, if the graph has $|V|-|E|$ components, then each of the components should be a tree because each $n_i$-vertex tree contains $n_i-1$ edges. Is this a good enough argument?

Best Answer

For the first part assume that $G$ has $s$ components. Then as it's forest we have that each such component is a tree and hence if $V_1$ is the number of vertices in the first component then there are $V_1-1$ edges in it. Obviously the number of edges in G is given by:

$$|E| = \sum_{n=1}^s (V_n - 1) = \sum_{n=1}^s V_n - s = |V| - s \implies s = |V| - |E|$$

Hence we proved one direction. For the other direction we know that a connected component of a graph can have at least $V_i - 1$ edges, where $V_i$ is the number of vertices in that connected component. So as $G$ has $s=|V| - |E|$ components we have:

$$|E| \ge \sum_{n=1}^s (V_n - 1) = |V| - s = |E|$$

Because we have equality we get that equality must hold in each of the inequality, so each connected component has exactly $V_i - 1$ edges and hence it's a tree. As each connected component is a tree we have that $G$ is a forest.