A **forest** is a disjoint union of trees.

The Gateway to Computer Science Excellence

+21 votes

+52 votes

Best answer

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

+11 votes

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.

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.

0

Yes, but no contraint is mentioned. I think there is typo in this question. It should be max or min.

+1

So, there can't be any graphs in a forest ? if they can be, then I think no. of edges for n-p+1 vertices will be (n-p+1)C2. @Arjun sir ?

+2

@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 ? :)

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 ? :)

+1

@ravi Here we are given forest

A

forestis 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.

+10 votes

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*

52,345 questions

60,510 answers

201,930 comments

95,354 users