- #1

lemonthree

- 51

- 0

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.