graph theory
In this assignment under chapter 3.7 the following formula is mentioned as an upper bound for the size of an maximum independent set in any given graph:
$$ |I_{max}| \leq \frac{1}{2}\left(1+\sqrt{1-8m-4n+4n^2}\right) $$
Where $n$ is the number of vertices and $m$ is the number of edges.
However the formula is not proven in any way in said text, which is why I ask how one would prove this?
Circulant graphs can be used to realize the $\lfloor n\Delta/2 \rfloor$ bound in a large number of cases, and in the other cases, we can modify them slightly to achieve this bound.
For example, when $n=10$ and $\Delta=6$, we can take the distances $\{1,2,3\}$, which gives:
For example, when $n=10$ and $\Delta=5$, we can take the distances $\{1,2,5\}$, which gives:
For example, when $n=11$ and $\Delta=6$, we can take the distances $\{2,3,4\}$, which gives:
Finally, when $n$ is odd and $\Delta$ is odd (so $\Delta \leq n-2$), $n\Delta/2$ is not an integer, so we can't achieve the maximum with circulant graphs. The best we could possibly do is $\lfloor n\Delta/2 \rfloor$. To achieve this:
We take a $(\Delta-1)$-regular graph as above, but do not take distance $1$ edges (we need to take at most $(\Delta-1)/2 \leq (n-3)/2$ distances, so this is possible).
We observe that the edges of distance $1$ form a Hamilton cycle in the complement of the graph. We pick $(n-1)/2$ disjoint edges from this Hamilton cycle (i.e., no two edges share an endpoint), and add them to our construction.
For example, when $n=11$ and $\Delta=7$, we can take the above $6$-regular graph and add in edges around the outside as follows:
This gives $\lfloor n\Delta/2 \rfloor$ edges in every case (as expected).
It seems the following.
Let $G'$ be the complement graph for $G$, $r$ be the maximal size of a clique of the graph $G$ (which is equal to the maximal size of an independent set of the graph $G'$), and $r'$ be the maximal size of a clique of the graph $G'$ (which is equal to the maximal size of an independent set of the graph $G$).
(1) $\Rightarrow$ (2). The graph $G'$ is $K_{r'+1}$ free and therefore $\frac{n(n-1)}2-e(G)=e(G')\le\frac{r'-1}{r'}\frac{n^2}{2}$. Simplifying the last inequality we obtain (2).
(2) $\Rightarrow$ (1). In this case $r\ge \frac{n^2}{2e(G') + n}= \frac{n^2}{n(n-1)-2e(G)+ n}$. Simplifying the last inequality we obtain (1).
Best Answer
Let there be an independent set $I$ of cardinality $k$. Then there are at most $\binom{n - k}{2}$ edges between vertices not from $I$ and at most $k(n - k)$ edges between vertex from $I$ and vertex not from $I$. But there is no edge between two vertices from $I$. Therefore $$m \le \binom{n - k}{2} + k(n - k),\\ 2m \le (n^2 - 2nk + k^2 - n + k) + 2(kn - k^2),\\ k^2 - k - (n^2 - n - 2m) \le 0,\\ D = 1 + 4n^2 - 4n - 8m,\\ \left(k - \frac{1 + \sqrt{1 + 4n^2 - 4n - 8m}}2\right)\left(k - \frac{1 - \sqrt{1 + 4n^2 - 4n - 8m}}2\right)\le 0,\\ k \ge 0 \ge \frac{1 - \sqrt{1 + 4n^2 - 4n - 8m}}2 \land k \le \frac{1 + \sqrt{1 + 4n^2 - 4n - 8m}}2. $$