Dark Mode

12,700 views

54 votes

The best answer is a bit misleading.

First let's see the definitions.

**Tree**: acyclic, connected and undirected graph.

**Forest**: collection of 1 or more trees .

**Rooted** **tree**: it's a special type of directed acyclic graphs. It has a root node from which there exist unique path to every other vertex.

The authors says that every tree has a root node which is not a correct statement.

Concepts like height, root node, depth, children, parents, ancestors etc are for Rooted tree and not tree. A tree is simply a connected , acyclic undirected graph.

The comment under the best answer by @Vicky rix is a good answer for this question.

0

64 votes

Best answer

A forest is a collection of trees. here we are given a forest with $n$ vertices and $k$ components. a component is itself a tree.

Since there are $k$ components means that every component has a root (every tree has one), therefore we have $k$ roots.

Introduction of each new vertex to the forest introduces a single edge to a forest. so for remaining $n-k$ vertices when introduced, to make up to $n$ vertices, contributes to $n-k$ edges.

Hence, ans $=$ **option (C)** $= (n-k)$

0

27 votes

A forest is an acyclic graph(with no cycle) , i.e all these components are a tree. With k components there are k roots.

And** **whenever a new node is added to a tree only a singe edge is introduced.

With k roots , remaining nodes are (n-k) each of which introduces an edge.

Hence, there are $\left(n-k\right)\times 1=\left(n-k\right)$ edges.

27 votes

**Another way:**

If $1$ edge is removed $2$ components.

If $2$ edges removed $3$ components.

.

.

.

If $k-1$ edges removed $k$ components.

A tree has $n-1$ edges. So, to make that tree into forest with $k$ components we would remove $k-1$ edges.

Therefore, Total edges in forest (Edges remained) = $n-1-(k-1)=n-k$