# Having a forest and making it into a tree?

Let F be a forest with 100 vertices and 90 edges. How many new edges must be added without adding vertices to obtain a tree?

This is what I have so far for this question... I don't think it's this simple, but please tell me where I went wrong..

We can link the forests together to make one big tree. A tree on n vertices has n-1 edges, so we need to add 9 more edges (100-1 = 99 and we only have 90 edges) to obtain a tree.

-
Is it possible to answer without knowing the number of trees in the forest? –  Sigur Dec 8 '12 at 23:45
Well, we can have 100 trees (just a dot) in a forest at most, but we also have 90 edges.. So if we add 1 edge to each of those trees, then we will have 50 trees in the forest, but we will have 50 edges.. –  Wooooop Dec 8 '12 at 23:49
@Sigur It is a forest, so each connected component is a tree, and they have $n-1$ edges for $n$ vertices. So each edge we miss from $99$ denotes a new component, i.e. there are $9+1$ components there (as Brian pointed out there is the first component). –  dtldarek Dec 8 '12 at 23:50
@dtldarek: Nine new components, but ten altogether. –  Brian M. Scott Dec 8 '12 at 23:52
@kevlar It is that simple. The only thing you would like to discuss in more detail is why there exist $9$ that would join your forest together. –  dtldarek Dec 8 '12 at 23:52

It’s almost this simple. Since a tree on $100$ vertices must have $99$ edges, it’s clear that you need to add $9$ edges. To finish the job, though, you really ought to explain why there’s always a way to add those $9$ edges to get a tree. There’s more than one way to justify this. One is to let the connected components of the graph be $T_1,\dots,T_m$, with $n_1,\dots,n_m$ vertices respectively. Each of those components must be a tree (why?), so $T_k$ has $n_k-1$ edges. We know that $$n_1+\ldots+n_m=100$$ and $$(n_1-1)+\ldots+(n_m-1)=90\;,$$ and from this it’s easy to deduce that $m=10$: the forest consists of ten trees. Now let $v_1,\dots,v_{10}$ be the roots of the ten trees, and add the nine edges $v_1v_2,v_2v_3,\dots,v_9v_{10}$; the resulting graph clearly works.
@kevlar: You’re welcome. We know that $T_k$ has $n_k-1$ edges, and there are altogether $90$ edges in all of the $T_k$’s put together, so $(n_1-1)+\ldots+(n_m-1)=90$. But the lefthand side is just $(n_1+\ldots+n_m)-m$, and $n_1+\ldots+n_m=100$, so $100-m=90$, and $m=10$. –  Brian M. Scott Dec 9 '12 at 1:03