edited by
18,195 views
57 votes
57 votes

If $G$ is the forest with $n$ vertices and $k$ connected components, how many edges does $G$ have?

  1. $\left\lfloor\frac {n}{k}\right\rfloor$
  2. $\left\lceil \frac{n}{k} \right\rceil$
  3. $n-k$
  4. $n-k+1$
edited by

11 Answers

Best answer
67 votes
67 votes

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)$

edited by
34 votes
34 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$

28 votes
28 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.

edited by
Answer:

Related questions

100 votes
100 votes
10 answers
1
38 votes
38 votes
9 answers
3
go_editor asked Sep 28, 2014
26,908 views
The maximum number of edges in a bipartite graph on $12$ vertices is____
32 votes
32 votes
9 answers
4
makhdoom ghaya asked Feb 13, 2015
24,385 views
Let G be a connected planar graph with 10 vertices. If the number of edges on each face is three, then the number of edges in G is_______________.