The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+11 votes
How many edges can there be in a forest with $p$ components having $n$ vertices in all?
asked in DS by Veteran (69k points)
recategorized by | 569 views

forest is a disjoint union of trees. 

3 Answers

+18 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 $\Rightarrow$ $(x_1 - 1)$ edges.
$2$nd component $\Rightarrow$ $(x_2 - 1)$ edges.
In $p$th component $\Rightarrow$ $(x_p - 1)$ edges.

Therefore, Total no. of edges are $[(x_1 + x_2 + x_3 +..... x_p) - p]$

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

So Total no. of edges are $(n - p)$.

answered by Veteran (15.1k points)
edited by
+9 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.
answered by Veteran (36.4k points)
Yes, but no contraint is mentioned. I think there is typo in this question. It should be max or min.
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 ?
A forest itself is a graph. Where is that formula coming from?
@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 

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.

+4 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 :) 


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:

answered by Veteran (10.4k points)
edited by
"having 'n' vertices in all"

what does it mean ? each component has n vertices or total vertices are n ?

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

34,170 questions
40,846 answers
39,704 users