2
$\begingroup$

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.

  • 0
    Is it possible to answer without knowing the number of trees in the forest?2012-12-08
  • 0
    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..2012-12-08
  • 1
    @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).2012-12-08
  • 0
    @dtldarek: Nine new components, but ten altogether.2012-12-08
  • 0
    @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.2012-12-08
  • 0
    @BrianM.Scott That's right, thanks.2012-12-08

1 Answers 1

6

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.

  • 0
    Amazing!! How could I imagine a simple solution like this?!2012-12-08
  • 1
    @Sigur: By not being such a pessimist? :-)2012-12-08
  • 0
    Lol, thanks Brian! One question though... How did you know that m=10?2012-12-09
  • 0
    @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$.2012-12-09
  • 0
    Thanks again! I really appreciate your help!2012-12-09