Forests and their number of components

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?

$\Leftarrow$ 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?

• Have you tried induction? – user499203 Nov 22 '17 at 18:48
• I did not actually. Which direction were you thinking about? @ThePirateBay – mandella Nov 22 '17 at 18:49
• Find the graph with the smallest possible $n$ and $k$, then prove it is a forest iff it satisfy these requirements, then prove it for $n+1$ for same $k$ and then for $k+1$ for arbitrary $n$. – user499203 Nov 22 '17 at 18:51

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.

• very nice. Please correct $V_1$ vertices not edges in the second line. – mandella Nov 22 '17 at 19:57
• Also, I do not understand why $|E| \geq |E|$ implies equality? – mandella Nov 22 '17 at 19:57
• @mandella We have $|E| \ge |E|$. Obviously we have that strict inequality can't hold. This means that in each used inequality we must have inequality. In fact if a component has stricly more than $V_i - 1$ edges then we get: $|E| > |E|$, which is impossible. Hence a contradiction. – Stefan4024 Nov 22 '17 at 20:00
• Perfect. Thanks! @Stefan4024 – mandella Nov 22 '17 at 20:01