1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – angryavian
    Nov 17, 2019 at 7:19

2 Answers 2

3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$ Nov 17, 2019 at 7:21
  • 2
    $\begingroup$ 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. $\endgroup$
    – user694818
    Nov 17, 2019 at 9:42
  • $\begingroup$ that's the whole point of forming a friends group @MatthewDaly $\endgroup$ Nov 17, 2019 at 18:09
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .