GATE CSE 1992 | Question: 03,iii

Question

How many edges can there be in a forest with $p$ components having $n$ vertices in all?

Comments

A forest is a disjoint union of trees. 

---

https://gateoverflow.in/2085/gate2014-3-51

---

Please add  this question in GO PDF

Answer 1

Answer: $\mathbf{n - p}$.

There are $p$ components and $n$ vertices. A component can have any no. of vertices but it must be a tree.

Let the no. of vertices in $1$st component be $x_1$, in $2$nd component $x_2$, in $3$rd component $x_3$, and so on. For the $p$th component, there will be $x_p$ vertices.

• In a tree with $n$ vertices, there are exactly $n - 1$ edges.

So, In $1$st component $\qquad \Rightarrow$ $(x_1 - 1)$ edges.
$2$nd component $\qquad \Rightarrow$ $(x_2 - 1)$ edges.
$\vdots$
In $p$th component $\qquad \Rightarrow$ $(x_p - 1)$ edges.

Therefore, total no. of edges $=[(x_1 + x_2 + x_3 +\ldots+ x_p) - p]$

$(x_1 + x_2 + x_3 + \ldots+ x_p) = n$ (total no. of vertices).

So, total no. of edges is $(n - p)$.

Comments

Thanks!

---

Nice explanation

---

i thought n vertices in each component ☹

---

Ritik gupta

the wording of the question is like that only :(

Answer 2

Answer: n-p

Corollary: If G is a forest with n vertices and p components, then G has n-p edges.

As, 0 edges for p-1 vertices (p-1 components) and n-p edges for n-p+1 vertices (1 component). So, total of n-p edges for p components.

Comments

@Arjun sir, Just thinking as an extreme case, if I have n nodes, then I can have at max nC2 edges I think.

And if all the connected components but one has only 1 vertex each, then the last component will have n-p+1 vertices, and so max edges could be n-p+1C2. But I am not sure Arjun sir, if I am right. Actually, could you tell me from where to study connected components, I am studying the CLRS book now, but not the whole book, only the topics in which I find myself weak, but I can't find in it the topic of connected components. Could you help me plz sir ? :)

---

@ravi Here we are given forest 

A forest is an undirected graph, all of whose connected components are trees.

So the combination formula you are using is a graph which contains cycles, while tree doesn't, hence not applicable for trees.

---

@shubham, Yeah that combinatorial formula can't be applied to trees but that logic can be applied. Am I right ?T
The last component will have n-p+1 vertices so it will have $n-p+1-1 = n-p \  edges.$

Answer 3

n vertices  p components.
( Component means they are non connected subgraphs )

Note that it is a forest ( Collection of trees only)

We want maximum edges in total forest. Right ? How to get maximum edges ? 

To get maximum,  take one vertex each for each component,  except last component. 
Now p-1 components has 1 vertex each so no edges. 
The last component has  n-(p-1) vertices. 
So find the maximum number of edges in last tree.
It has n-(p-1) -1   edges. = n-p edges.    Very Simple :) 

BY THE WAY IT IS AN EXAMPLE ONLY.  YOU WILL ALWAYS GET n-k edges in any example. 

But to get maximum edges in any graph (not forest), as like the qsn below,  only these type of examples will give maximum...where rest components have one vertex & last one with rest vertex. 
Must do a similar model qsn on graph:   https://gateoverflow.in/510/gate1991_01-xv

Comments

Ahwan

I think this case which you explained is for the minimum no of edges ..as in question it is mentioned that we have p components and n vertices in all .. so if we want the minimum no of edges it will be    (n-p)....but if maxm is asked then it should be [(n-p)(n-p+1)/2 ].

correct me if i m wrong!