For the question below I am getting m+n+c but I am told it is wrong can someone please help

How many edges must be removed to produce the spanning forest of a graph

with n vertices, m edges and c connected components?

Thanks

Printable View

- Nov 4th 2010, 03:13 PMtheflyingcowSpanning Forest
For the question below I am getting m+n+c but I am told it is wrong can someone please help

How many edges must be removed to produce the spanning forest of a graph

with n vertices, m edges and c connected components?

Thanks - Nov 5th 2010, 07:37 AMtheflyingcow
The only way I can make sense of the m-n+c is that:

n vertices stay the same for every component of spanning trees.(n)

There are less edges m in every spanning tree.(m-n)

Lastly there you union all the components to create a spanning forest.(+c)

So overall you get m-n+c.

Is that right?