Graph has vertices, edges and connected components.

If , prove that is aforest.

Printable View

- November 5th 2007, 04:51 AMle_su14Discrete question.
Graph has vertices, edges and connected components.

If , prove that is a**forest**. - November 5th 2007, 08: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? - November 5th 2007, 09:45 AMle_su14
- November 5th 2007, 11: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 .

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