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?

  • $\begingroup$ Have you tried induction? $\endgroup$
    – user499203
    Nov 22 '17 at 18:48
  • $\begingroup$ I did not actually. Which direction were you thinking about? @ThePirateBay $\endgroup$
    – mandella
    Nov 22 '17 at 18:49
  • $\begingroup$ 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$. $\endgroup$
    – 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.

  • $\begingroup$ very nice. Please correct $V_1$ vertices not edges in the second line. $\endgroup$
    – mandella
    Nov 22 '17 at 19:57
  • $\begingroup$ Also, I do not understand why $|E| \geq |E|$ implies equality? $\endgroup$
    – mandella
    Nov 22 '17 at 19:57
  • $\begingroup$ @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. $\endgroup$
    – Stefan4024
    Nov 22 '17 at 20:00
  • 1
    $\begingroup$ Perfect. Thanks! @Stefan4024 $\endgroup$
    – mandella
    Nov 22 '17 at 20:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.