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

forest is a disjoint union of trees. 

3 Answers

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

answered by Boss (15.3k points)
edited by
0
Thanks!
+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 Boss (34k points)
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 ?
0
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.$
+6 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

answered by Boss (11k points)
edited by
0
"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

41,053 questions
47,650 answers
147,206 comments
62,380 users