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
    @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
    Thanks again! I really appreciate your help!2012-12-09