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 :) .
$\endgroup$ 112 Answers
$\begingroup$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$.
$\endgroup$ 0 $\begingroup$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.
$\endgroup$
