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 :) .
 A: 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)\not\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$.
A: Here is an alternate solution (I think...).
Consider all pairs of vertices $v_i, v_j$ such that $v_i, v_j$ are not connected by an edge. Call these pairs 'special.' How many such pairs are there? 
Consider a vertex $v^{\star}$. It is not connected to $V-\deg(v^{\star})$ vertices. Summing over all vertices and dividing by $2$ (since we count each pair twice), we get that the number of such pairs is $$\sum_{v^{\star} \in V} \frac{V- \deg{v^{\star}}}2 = \sum_{v^{\star} \in V} \frac{V}2 - \sum_{v^{\star} \in V} \frac{\deg{v^{\star}}}2 = \frac{V^2}2 - \frac{S}2$$ where $S$ is the sum of the degrees of the vertices of $G$. We wish to prove $S \ge kV$. 
Now for each special pair of vertices $v_1, v_2,$ we have $$\deg(v_1) + \deg(v_2) \ge 2k.$$ As noted above, each vertex $v^{\star}$ is part of  $V-\deg(v^{\star})$ special pairs. If we sum this relation over all vertices, each vertex $v^{\star}$ will contribute $$\deg(v^{\star})\cdot \frac{V-\deg(v^{\star})}2$$ to the sum since we will have considered each pair twice. Thus, we have
$$\frac{1}2 \sum_{v \in V} \deg(v)(V- \deg(v)) \ge 2k \left( \frac{V^2}2-\frac{S}2 \right)$$
$$\sum_{v \in V}  \deg(v) \cdot V - \sum_{v \in V}\deg(v)^2 \ge 2k(V^2-S)$$
$$SV+2kS -2kV^2 \ge \sum_{v \in V} \deg(v)^2.$$
As user141614 pointed out, we can use Cauchy-Schwarz to say $$\sum_{v \in V} \deg(v)^2 \ge \frac{S}V.$$ Thus, we have $$SV+2kS-2kV^2 \ge \frac{S^2}V$$ or $$0 \ge \frac{S^2}V + S(-V-2k)+2kv^2 = \left(\frac{S}V-V \right)(S-2kV).$$ Thus we know that $S$ lies in the interval between $2kV$ and $V^2$. If $V  \ge 2kV$, we are done since $S \in [2kV, V^2]$ and $S \ge 2kV \ge kV$. If $$2kV \ge V, S \ge V^2 \ge (k+1)V \ge kV.$$ Thus, we can replace the problem by a stronger statement that the average degree is atleast k+1.
