How many edges are needed to connect a forest of x trees?

136 Views Asked by At

Let's say I have a forest of x trees (a bunch of disconnected trees). How many edges must be added to convert the forest into a single, contiguous tree?

Wouldn't it just be x-1 edges?

The problem also states that the trees have $y_1, y_2, ..., y_x$ vertices, respectively, and I don't understand why this information is relevant.

Am I misinterpreting something?

1

There are 1 best solutions below

0
On BEST ANSWER

If you're unconvinced, try a proof by induction. Start with the case where $x=2$. Then assume it works when you have $n$ trees and look at what happens when you have $n+1$ trees.