Simple Graph with n Vertices and k Components have at most (n-k)(n-k+1)/2 Edges

In this page, we will show that a simple graph with n vertices and k components have at most (n-k)(n-k+1)/2 edges.

Question: Prove that a simple graph of $n$ vertices and $k$ components can have at most $\dfrac{(n-k)(n-k+1)}{2}$ number of edges.

Answer:

Let the $i$-th component of the graph G is denoted by G_i. Suppose that G_i have $n_i$ vertices ($n_i \geq 1$). As G has k components and n vertices in total, so we have that

$n_1+n_2+\cdots +n_k=n$.

That is, $\displaystyle \sum_{i=1}^k n_i=n$ …(I)

⇒ $\displaystyle \sum_{i=1}^k(n_i-1)=n-k$

Squaring both sides, it follows that

$\left\{\displaystyle \sum_{i=1}^k(n_i-1) \right \}^2=(n-k)^2$

Simplifying the above expression we obtain that

$\left\{\displaystyle \sum_{i=1}^k(n_i-1) \right \}^2=(n-k)^2$

⇒ $\displaystyle \sum_{i=1}^k(n_i-1)^2$ $+2\displaystyle \sum_{i\neq j} (n_i-1)(n_j-1)$ = n²-2nk+k²

⇒ $\displaystyle \sum_{i=1}^k(n_i-1)^2$ ≤ n²-2nk+k²

⇒ $\displaystyle \sum_{i=1}^k(n_i^2-2n_i+1)$ ≤ n²-2nk+k²

⇒ $\displaystyle \sum_{i=1}^k n_i^2$ ≤ n²-2nk+k²+2n-k …(II).

Here we have used the above identity (I)

We know that the maximum number of edges in G_i having n_i edges is equal to $^{n_i}C_2$ = $\dfrac{n_i(n_i-1)}{2}$. Thus the maximum number of edges of the graph G is

= $\dfrac{1}{2} \displaystyle \sum_{i=1}^k n_i(n_i-1)$

= $\dfrac{1}{2} \displaystyle \sum_{i=1}^k n_i^2 -\dfrac{1}{2} \cdot n$, by (I)

≤ $\dfrac{1}{2} (n^2-2nk+k^2+2n-k) -\dfrac{n}{2}$

= $\dfrac{1}{2} (n^2-2nk+k^2+n-k)$

= $\dfrac{1}{2} \big( (n-k)^2+(n-k) \big)$

= $\dfrac{(n-k)(n-k+1)}{2}$.

This shows that a simple graph with n vertices and k components can have at most (n-k)(n-k+1)/2 number of edges. This completes the proof.

Related Articles:

Simple graph with n vertices has a pair of vertices of same degree

Prove that a tree with n vertices has (n-1) edges