What is the maximum possible number of edges of a graph with n vertices and k components?

Question

Following is my attempt:

For maximum possible edges $->$ all k components must be connected sub-graphs

Maximum possible edges in a graph with n vertices = ${n \choose 2}$, I thought of removing k-1 edges, but only to realise that doing so doesn't divide the graph into k components.

How should I proceed now?

Answer 1

Consider this problem combinatorially.

You have $n$ vertices partitioned into $k$ components. Assume $n \geq k$.

Consider the equation $n_1+n_2+\cdots+n_k=n$.

For each component with $n_i$ vertices, the maximum number of edges you can generate is $\displaystyle \binom{n_i}{2}$.

So, you want to maximize $\displaystyle \binom{n_1}{2}+\binom{n_2}{2}+\cdots \binom{n_k}{2}$.

Play with it for a while. The maximum result is obtained when $n_1=n-k+1$, and $n_2=n_3...=n_k=1$, and the maximum number of edges is $\displaystyle \binom{n-k+1}{2}$.

Answer 2

I am assuming your question is the following:

What is the maximum number of edges in a graph with $n$ vertices and $k$ connected components?

This is equivalent to maximizing the function

$$ f(x_1,...,x_k) = \sum_{i} \binom{x_i}{2} =\frac{1}{2} \sum_{i} x_i^2-x_i $$

subject to the constraints

$$ \sum_{i}x_i = n $$ and $x_i \in \mathbb{N}^{>0}$.

Why? Because of none of the components $C_i$ can have an edge between them and $\binom{|C_i|}{2}$ is the maximum edges subject to this constraint; the $x_i \in \mathbb{N}^{>0}$ is necessary to ensure that there are $k$ components.

From here we have two possible approaches:

1. combinatorial optimization
2. Lagrange multipliers

but the first is much nicer.

Combinatorial approach Notice that if we take a "ball" (i.e. vertex) out of the $x_j$ "box" (i.e. component) and place it in the "$x_i$" box then we get that $\Delta f = x_i-x_j+1$. Therefore it seems that the solution is to just place all of the balls in one box because $x_i>x_j$ implies $f'=f+\Delta f = f+ x_i-x_j+1$ is a better solution. This is not allowed because of the condition $x_i \in \mathbb{N}^{>0}$. But we can set

$x_1=n-k+1$ and $x_2=...=x_k=1$.

This is the optimal configuration. Indeed suppose you had any other solution $z_1,...,z_k$ for a contradiction. Order the $z_i$ in decreasing size. Suppose that $z_i >1$ for some $i>2$ then we get that setting $z_i$ equal to $z_i-1$ and $z_1$ equal to $z_1+1$ gives us a better solution contradicting the optimality of the $z_i$.