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

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?

• If the sizes of the $k$ components are fixed and known, can you answer the question? If so, then the question reduces to finding the best choice of sizes of the components. Nov 17, 2019 at 7:19

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}$$.

• This is because $\displaystyle \binom{x}{2}=\displaystyle \frac{x^2-x}{2}$ grows quadratically with respect to $x$, so you gain more edges by "investing" as many vertices in one component, than distributing them among many components Nov 17, 2019 at 7:21
• It's easier to see intuitively on a micro level. If more than one component had extra vertices, you would get a net gain edges by erasing all the connections from an extra vertex and joining to al the edges in a larger component. Therefore, the maximal number of edges comes when every component but one has only one vertex.
– user694818
Nov 17, 2019 at 9:42
• that's the whole point of forming a friends group @MatthewDaly Nov 17, 2019 at 18:09

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