Number of edges in a graph with n vertices and k connected components

Question

Let $m$ be the number of edges, $n$ the number of vertices and $k$ the number of connected components of a graph G.

Prove that:

$m$ $\leq$ $\frac{(n-k+1)*(n-k)}{2}$

Thanks!

Answer 1

The maximum number of edges is clearly achieved when all the components are complete.

Moreover the maximum number of edges is achieved when all of the components except one have one vertex. The proof is by contradiction. Suppose the maximum is achieved in another case. Then there exist two components with more than one vertex say the number of vertices are $n$ and $m$ . Pick the one with the less vertices suppose it is $m$ vertices. Take one of it vertices and delete it. removing $m-1$ edges. now add a new vertex to the component with $n$ vertices and join it to all its vertices, adding $n$ edges. This graph has more edges, contradicting the maximality of the graph.

Hence the maximum is achieved when only one of the components has more than one vertex. How many vertices does this graph have? the big component has $n-k+1$ vertices and is the only one with edges. So it has $\frac{(n-k+1)(n-k)}{2}$ edges.

Answer 2

A component should have at least 1 vertex, so give 1 vertex to the k-1 components. Now n-(k-1) = n-k+1 vertices remain. For the maximum edges, this large component should be complete. Maximum edges possible with n-k+1 vertex = $ {n-k+1 \choose 2} = \frac{(n-k+1)(n-k)}{2}$

Answer 3

Below is the proof replicated from the book by Narsingh Deo, which I myself do not completely realize, but putting it here for reference and also in hope that someone will help me understand it completely. Things in red are what I am not able to understand.

Proof

Let the number of vertices in each of the $k$ components of a graph G be $n_1,n_2,...,n_k$. Thus we have,

$$n_1+n_2+...+n_k=n$$ $$n_i\geq 1$$

The proof of the theorem is based on the inequality $$\sum^k_{i=1}n_i^2\leq n^2 -(k-1)(2n-k)$$

This inequality can be proved as follows.

$$\sum_{i=1}^k(n_i-1)=n-k$$ Squaring both side, $$\left(\sum_{i=1}^k(n_i-1)\right)^2=n^2+k^2-2nk$$ or $$\color{red}{\sum_{i=1}^k(n_i^2-2n_i)+k+\text{nonnegative cross terms}= n^2+k^2-2nk}$$

because $(n_i-1)\geq 0$, for all $i$.

Therefore, $$\color{red}{\sum_{i=1}^kn_i^2\leq n^2+k^2-2nk-k+2n=n^2-(k-1)(2n-k)}$$

Thus the required inequality is proved.

Now the maximum number of edges in $i^{th}$ component of G (which is simple connected graph) is $\frac{1}{2}n_i(n_i-1)$. Therefore, the maximum number of edges in $G$ is

$$\frac{1}{2}\sum^k_{i=1}(n_i-1)n_i=\frac{1}{2}\left( \sum_{i=1}^kn_i^2 \right) - \frac{n}{2}$$ $$\leq \frac{1}{2} \left( n^2-(k-1)(2n-k) \right) - \frac{n}{2}$$ $$=\frac{1}{2}(n-k)(n-k+1)$$