Graph $\displaystyle G = (V,E)$ has $\displaystyle n$ vertices, $\displaystyle m$ edges and $\displaystyle p$ connected components.

If $\displaystyle m = n - p$, prove that $\displaystyle G$ is aforest.

Printable View

- Nov 5th 2007, 03:51 AMle_su14Discrete question.
Graph $\displaystyle G = (V,E)$ has $\displaystyle n$ vertices, $\displaystyle m$ edges and $\displaystyle p$ connected components.

If $\displaystyle m = n - p$, prove that $\displaystyle G$ is a**forest**. - Nov 5th 2007, 07:00 AMPlato
In other words, you want to show that each component of that graph is a tree.

None of the components can contain a cycle.

Consider the fact |E|=|V|-p. Is a cycle possible? - Nov 5th 2007, 08:45 AMle_su14
- Nov 5th 2007, 10:56 AMPlato
This is again one of those situations in which I don’t for sure what you have to use. In general a tree has one less edge than vertices. If a component (btw. saying connect is redundant components are connected) has a cycle then it has at least as many edges as vertices. That would contradict the given that |E|=|V|-p.

If every component is a tree then $\displaystyle \left| E \right| = \sum\limits_{k = 1}^p {\left| {E_k } \right|} = \sum\limits_{k = 1}^p {\left( {\left| {V_k } \right| - 1} \right)} = \left| V \right| - p$.

So a cycle any where changes that equation. - Nov 5th 2007, 06:56 PMle_su14