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

http://www.math.ucsd.edu/~gptesler/184a/slides/184a_trees_17-handout.pdf

---

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. 

---

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.

Answer 1

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 2

Let each connected component has xi vertices

Answer 3

There are k components and n vertices.

Let us assume that number of vertices in different components to be $n1$, $n2$, $n3$, $n4$,... $nk$.

Now, number of edges in each components will be $n1-1$, $n2-1$, $n3-1$, $n4-1$,... $nk-1$. (Since, each component in a forest is a tree, and if no. of vertices in a tree is $i$, then no. of edges in that tree is $i-1$)

Total number of edges = $(n1-1)+(n2-1)+(n3-1)+(n4-1)+... (nk-1)$

$=(n1+n2+n3+n4+...nk)-(1+1+1+1+...' k'times )$

$=n-k$   (Since, $n1+n2+n3+n4+...nk=n$)

So, option D is correct.

Answer 4

Simplest answer is:

When no. of vertices = no. of components (n=k).

  It means each component will have just one vertex ,so for k components we have k vertices where n=k.

So in this forest we will have zero edges, or n-k=0 (because n=k). 

eg: n=k=4

   .   .   .   .    (each dot represent a vertex, so there is no edge here)

 

So, Answer is (C)