1. ## 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.

2. 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?

3. 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?

4. 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.

5. 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.