1) If a forest F consists of m trees and has n vertices, how many
edges does F have.?

---

Clarification of Question by dan1976-ga on 25 Apr 2005 22:08 PDT

F is simpe graph with no cycles

If you try a few examples, you should be able to see a pattern pretty easily.

What a great handle, "quadraticresidue-ga"!

Yes, start with a single tree.  If it had n vertices, it would have n-1 edges.

Now a forest is a collection of trees.  In each tree there is one
fewer edge than the number of vertices in that tree.

So, how many edges does a forest F require with m trees and n vertices (total)?

regards, mathtalk-ga

Sorry for my broken English!

> If a forest F consists of m trees and has n vertices, how many
edges does F have.?
> F is simpe graph with no cycles

For all trees Ti from the forest F (1 <= i <= m):

V(Ti) = Vi - a quantity of vertices, 1 <= i <= m.
E(Ti) = Ei - a quantity of edges, 1 <= i <= m.
Ei = Vi - 1 - this is a simple feature of tree.
E(F) = E1 + E2 + ... + Em = (V1 - 1) + (V2 - 1) + ... + (Vm - 1) = (V1
+ V2 + ... + Vm) - m.
But V1 + V2 + ... + Vm = V(F) = n.
Then E(F) = n - m.

Thanx.

Forest if collection of disjoint trees.
Step 1: Start from a single tree with n vertices. This will have n-1 edges.
Step 2: Remove an edge from this tree. Now there are 2 trees and
number of edges = n-2.
Step 3: Recursively going the Step 2 m-1 times will leave us with m
trees and number of edges = n-m.