Prove the minimum and maximum edges in a graph

[lemonthree]

Hello! I am having trouble solving the right part of the inequality.

For left part of the inequality $n-k \le m$, here’s how I did it

Let $ n = v_{1} + v_{2} + v_{3}...+v_{k}$, the sum of vertices of each component in G

least number of edges = $(v_{1}-1) + (v_{2}-1) + (v_{3}-1)...+(v_{k}-1)$

$= n - k$

so $n-k \le m$Now the part that I am having trouble.

Most number of edges = $\frac{v_{1}(v_{1}-1)}{2} + \frac{v_{2}(v_{2}-1)}{2} ... +\frac{v_{k}(v_{k}-1)}{2}$

$= \frac{v_{1}^{2}-v_{1}+v_{2}^{2}-v_{2}...v_{k}^{2}-v_{k}}{2}$

$= \frac{v_{1}^{2}+v_{2}^{2}...v_{k}^{2}+(-n)}{2}$

but this does not get me anywhere near (n-k)(n-k+1) in the numerator, although I am quite sure that my equation is on the right track... How can I introduce the k in? I only know that there are k terms since there are k connected components.

 

[Evgeny.Makarov]

I agree with your proof of the left inequality. You used the same fact, but for $k=1$: the least number of edges in a connected graph on $n$ vertices is $n-1$. We can also prove the left inequality for arbitrary $k\ge 1$ as follows. Consider an empty graph on $n$ vertices. It has $n$ connected components. We need to reduce the number of components to $k$. Adding an edge reduces the number of components by 1 or leaves it unchanged. Therefore, eliminating $n-k$ components requires at least $n-k$ edges.

For the right inequality, you correctly require each connected component to be a complete graph $K_{v_i}$. First prove the following lemma: if $n_1\ge n_2>1$, then $K_{n_1}$ and $K_{n_2}$ together have fewer edges than $K_{n_1+1}$ and $K_{n_2-1}$ together. Therefore, to maximize the number of edges one should collect as many vertices as possible in one large component.

This works because the maximum number of edges grows quadratically with the number of vertices, so adding a vertex to a large component has a bigger effect than subtracting it from a smaller component. The same principle is used in the game with an unusual name "SameGame". The goal is to eliminate contiguous group of marbles of the same color. For a group of $n>1$ marbles you get $(n-2)^2$ points. So instead of eliminating them in small groups it is advantageous to try to collect all marbles of the same color into one large group and go "Boom!".

 

[lemonthree]

Thank you for the hint. I think it's cool that you mentioned about SameGame too, I played that game when I was younger and never really thought that you could link it to this topic.

In any case, I followed as per your comment and got this:
Let $n_{q} \ge n_{p} \gt 1$
$K_{n_{q}} + K_{n_{p}} \lt K_{n_{q+1}} + K_{n_{p-1}}$
$\frac{n_{q}(n_{q}-1)}{2} + \frac{n_{p}(n_{p}-1)}{2} \lt \frac{n_{q}(n_{q}+1)}{2} + \frac{n_{p}-1(n_{p}-2)}{2}
= \frac{n_{q}^{2}-n_{q}+n_{p}^{2}-n_{p}}{2} \lt \frac{n_{q}^{2}+n_{q}+n_{p}^{2}-3n_{p}+2}{2}$

Now let us assume the case where $n_{q} = n_{p}$, so $-2n_{q} \lt -2n_{q}+2$
Therefore $K_{n_{q}} + K_{n_{p}} \lt K_{n_{q+1}} + K_{n_{p-1}}$
How can I link this result of the lemma to the right hand side equation?
From the result, I can see that $K_{10} + K_{9} \lt K_{11} + K_{8} ... \lt K_{17} + K_{2} $(let's say n = 19 so total of 19 vertices)

And from this I get that the most number of edges will be in the case where $K_{17} + K_{2}$. I know the right hand side equation is related to C(n-k,2), and how should we link them together?

 

[Evgeny.Makarov]

Two graphs $K_{17}$ and $K_2$ should be further transformed to $K_{18}$ and $K_1$ where $K_1$ is an isolated vertex. Therefore, if we have $n$ vertices, the graph with $k$ components and maximum number of edges is $K_{n-k+1}$ and $k-1$ copies of $K_1$.

 

[lemonthree]

Thank you! I understand it now. Since $K_{1}$ is an isolated vertex, there will be no edges anyway. And so we just look at $K_{n-k+1}$ which leads us to C(n-k+1,2).

 

[Evgeny.Makarov]

A couple of additional remarks about message 3 in this thread.

1. It makes sense to introduce notations $n_p$ and $n_q$ if we have a sequence $n_1,n_2,\ldots$. Then $p$ and $q$ can be indices of two elements in this sequence. However, if there are only two graphs, then the number of vertices in them are better denoted by $n_1$ and $n_2$.

2. Equivalence of inequalities can be denoted by $x<y\iff u<v$. Writing $x<y=u<v$ suggests that $y=u$.

3. There is no need to assume $n_p=n_q$. The required inequality only uses the fact that $n_q\ge n_p>1$. This can be shown with minimum algebra: if $p\ge q>1$, then moving a vertex from $K_q$ to $K_p$ removes $q-1$ edges from the first graph and adds $p$ edges to the second one. The net change is $p-q+1>0$.

 

[lemonthree]

A couple of additional remarks about message 3 in this thread.

1. It makes sense to introduce notations $n_p$ and $n_q$ if we have a sequence $n_1,n_2,\ldots$. Then $p$ and $q$ can be indices of two elements in this sequence. However, if there are only two graphs, then the number of vertices in them are better denoted by $n_1$ and $n_2$.

2. Equivalence of inequalities can be denoted by $x<y\iff u<v$. Writing $x<y=u<v$ suggests that $y=u$.

3. There is no need to assume $n_p=n_q$. The required inequality only uses the fact that $n_q\ge n_p>1$. This can be shown with minimum algebra: if $p\ge q>1$, then moving a vertex from $K_q$ to $K_p$ removes $q-1$ edges from the first graph and adds $p$ edges to the second one. The net change is $p-q+1>0$.

Alright, noted, thank you very much for the comments! I never thought that $x<y=u<v$ could be seen in that way too :)