Prove the minimum and maximum edges in a graph

In summary, the conversation discusses the proof of the inequality $n-k \le m$ and the maximum number of edges in a connected graph on $n$ vertices. The first part shows how the proof for the left inequality is extended to arbitrary $k \ge 1$. The second part introduces a lemma and discusses how to maximize the number of edges by collecting as many vertices as possible in one large component. The final part clarifies the relationship between the lemma and the right hand side equation, concluding that the most number of edges is achieved in the graph $K_{n-k+1}$ and $k-1$ isolated vertices. Some additional remarks are made regarding notation and equivalence of inequalities.
  • #1
lemonthree
51
0
1615823219959.png

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.
 
Physics news on Phys.org
  • #2
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!".
 
  • #3
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?
 
  • #4
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$.
 
  • #5
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).
 
  • #6
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$.
 
  • #7
Evgeny.Makarov said:
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 :)
 

Related to Prove the minimum and maximum edges in a graph

1. What is a graph?

A graph is a data structure that consists of a set of vertices (nodes) connected by edges. It is used to represent relationships or connections between different objects or entities.

2. What is the minimum edge in a graph?

The minimum edge in a graph is the smallest number of edges that must be present in order for the graph to be connected. It is also known as the minimum degree of a graph.

3. What is the maximum edge in a graph?

The maximum edge in a graph is the largest number of edges that can be present without creating a complete graph. It is also known as the maximum degree of a graph.

4. How do you prove the minimum and maximum edges in a graph?

The minimum and maximum edges in a graph can be proven using the handshaking lemma, which states that the sum of the degrees of all vertices in a graph is equal to twice the number of edges. By using this lemma, we can determine the minimum and maximum edges in a graph.

5. Why is it important to know the minimum and maximum edges in a graph?

Knowing the minimum and maximum edges in a graph can help us understand the structure and connectivity of the graph. It can also be useful in various graph algorithms and applications, such as finding the shortest path between two vertices or identifying the most influential nodes in a network.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
3K
  • Introductory Physics Homework Help
Replies
15
Views
363
  • Introductory Physics Homework Help
Replies
15
Views
383
  • Differential Equations
Replies
3
Views
1K
  • Introductory Physics Homework Help
Replies
2
Views
275
  • Introductory Physics Homework Help
Replies
10
Views
995
  • Engineering and Comp Sci Homework Help
Replies
0
Views
723
  • Introductory Physics Homework Help
Replies
6
Views
867
Replies
2
Views
833
  • Introductory Physics Homework Help
Replies
1
Views
186
Back
Top