GATE CSE 2014 | Set 3 | Question: 51

Question

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

• A. $\left\lfloor\frac {n}{k}\right\rfloor$
• B. $\left\lceil \frac{n}{k} \right\rceil$
• C. $n-k$
• D. $n-k+1$

Comments

here is a slight variation of the same question :

calculate no of distinct forests possible with n vertices and k components 

can be solved with star-bar problem:

consider every component as a box 

first fill every box with minimum 1 vertex –> so k components with 1 vertex each

remaining n-k vertices can be distributed in k components in $\binom{n-k+k-1}{n-k} = \binom{n-1}{n-k}$ ways.

So, $\binom{n-1}{n-k}$ forests possible with n vertices and k components.

---

Similar Question with good solution !

GATE 1992-Q-03

---

Simplest Approach !!
We can directly solve this with simple EULER FORMULA 

V + F = E + K + 1

 Here V -> no of vertices = here N given
          F -> no. of faces => here forest is given and in forest no. of faces are always equal to 1
          E-> no of edges => we have to find
          K-> no of components => here k given 

Now put all in formula you will get 

E = n-k

exact same question GATE 1992

 

 

Answer 1

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

Comments

very well explained @Vicky rix

---

note: if asked for a tree then (n-k)(n-k+1)/2 isn't it?

---

@Vicky rix  excellent explaination !

Answer 2

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$

Answer 3

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.

Answer 4

Please verify this method

Answer 5

Since a forest with n vertices can not have more than n-1 edges with no cycle. By keeping this definition in mind, draw some graphs such as

n = 4 components(k)=2 then e=2

n = 5 , k = 3 then e= 2

n = 4 k = 3 then e = 1  

and so all are satisfying than e = n - k

Answer 6

Let each connected component has xi vertices