recategorized by
6,346 views
33 votes
33 votes
How many edges can there be in a forest with $p$ components having $n$ vertices in all?
recategorized by

3 Answers

Best answer
78 votes
78 votes

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
11 votes
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.
11 votes
11 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

edited by

Related questions

23 votes
23 votes
3 answers
1
Kathleen asked Sep 13, 2014
4,549 views
Assume that the last element of the set is used as partition element in Quicksort. If $n$ distinct elements from the set $\left[1\dots n\right]$ are to be sorted, give an...
9 votes
9 votes
4 answers
2
Kathleen asked Sep 12, 2014
3,139 views
A non-planar graph with minimum number of vertices has$9$ edges, $6$ vertices$6$ edges, $4$ vertices$10$ edges, $5$ vertices$9$ edges, $5$ vertices
10 votes
10 votes
1 answer
3
Kathleen asked Sep 12, 2014
5,447 views
Maximum number of edges in a planar graph with $n$ vertices is _____
1 votes
1 votes
4 answers
4
go_editor asked May 23, 2016
997 views
A simple graph is one in which there are no self loops and each pair of distinct vertices is connected by at most one edge. Show that any finite simple graph has at least...