Discrete question.

Printable View

November 5th 2007, 03:51 AM
le_su14

Discrete question.

Graph $G = (V,E)$ has $n$ vertices, $m$ edges and $p$ connected components.
If $m = n - p$ , prove that $G$ is a forest.
November 5th 2007, 07:00 AM
Plato

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?
November 5th 2007, 08:45 AM
le_su14

Quote:

Originally Posted by Plato

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?

I can't prove that a cycle doesn't exist in every tree.
What can I refer to when I suppose that there is a connected component contains a cycle?
November 5th 2007, 10:56 AM
Plato

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 $\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.
November 5th 2007, 06:56 PM
le_su14

Quote:

Originally Posted by Plato

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 $\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.

Thank you very much! Now I can solve it.