Average degree in graph > > Let $G=(V,E)$ on at least k+1 vertices Assume for every $u\neq v \in V$ s.t. $(u,v) \notin E$ we have $deg(u)+dev(v) \geq 2k$ . Prove that the average degree is at least $k$. I tried looking at $G$'s complement , but it was no use. I also tried counting , but I am thinking I am missing something. I'll be happy if someone could supply a hint :) .

Let $|E|=e$; the average degree is $a=\frac{2e}{n}$.

Taking sum of the condition over all edges in the complementer, $$ \sum_{(u,v)\
ot\in E}(\deg(u)+\deg(v)) \ge \left(\binom{n}{2}-e\right)\cdot 2k. $$ Notice that for each vertex $u$, the term $\deg(u)$ is taken $n-1-\deg(u)$ times on the LHS. Therefore, $$ \sum_{u\in V} (n-1-\deg(u))\deg(u) \ge \left(\binom{n}{2}-e\right)\cdot 2k. $$ From double-counting the edges we have $\sum \deg(u) = 2e$, and from Cauchy-Schwarz $\sum \deg^2(u) \ge \frac{(2e)^2}{n}$. So, $$ 2(n-1)e - \frac{4e^2}{n} \ge \sum_{u\in V} (n-1-\deg(u))\deg(u) \ge \left(\binom{n}{2}-e\right)\cdot 2k = n(n-1)k-2ke, $$ $$ \left(\frac{2e}n\right)^2 - (n+k-1)\frac{2e}n + (n-1)k \le 0. $$ $$ (a-k)(a-n+1) \le 0. $$ Due to $n\ge k+1$, we have $a-k\ge a-n+1$, so $a-k$ canot be negative, $a\ge k$.