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

### 3 Comments

## 3 Answers

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

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.

### 7 Comments

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

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.

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*