0
$\begingroup$

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?

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

1 Answer 1

Reset to default
2
$\begingroup$

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .