1.9k views
How many edges can there be in a forest with $p$ components having $n$ vertices in all?
in DS
recategorized | 1.9k views
+11

forest is a disjoint union of trees.

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

edited by
0
Thanks!
0
Nice explanation

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
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 ?
+1
A forest itself is a graph. Where is that formula coming from?
+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 ? :)
+1

@ravi Here we are given forest

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.

0
@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.$

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

by
edited by