Grado medio en el gráfico

Question

Deje $G=(V,E)$ en al menos k+1 vértices de Asumir por parte de todos los $u\neq v \in V$ s.t. $(u,v) \notin E$ tenemos $deg(u)+dev(v) \geq 2k$ . Demostrar que el grado medio es, al menos,$k$.

He intentado buscar en $G$'s del complemento , pero fue inútil.

También traté de contar , pero estoy pensando que me falta algo.

Voy a ser feliz si alguien podría suministrar una sugerencia :) .

Answer 1

Deje $|E|=e$; el grado medio es el $a=\frac{2e}{n}$.

La suma de la enfermedad sobre todo en los bordes de la complementer, $$ \sum_{(u,v)\no\en E}(\deg(u)+\deg(v)) \ge \left(\binom{n}{2}-e\ \ derecho)\cdot 2k. $$ Observe que para cada vértice $u$, el plazo $\deg(u)$ es tomada $n-1-\deg(u)$ veces en el lado izquierdo. Por lo tanto, $$ \sum_{u\V} (n-1-\deg(u))\deg(u) \ge \left(\binom{n}{2}-e\ \ derecho)\cdot 2k. $$ A partir de la doble contabilización de los bordes que hemos $\sum \deg(u) = 2e$, y a partir de Cauchy-Schwarz $\sum \deg^2(u) \ge \frac{(2e)^2}{n}$. Así, $$ 2(n-1)e - \frac{4e^2}{n} \ge \sum_{u\V} (n-1-\deg(u))\deg(u) \ge \left(\binom{n}{2}-e\ \ derecho)\cdot 2k = n(n-1)k-2ke, $$ $$ \left(\frac{2}n\right)^2 - (n+k-1)\frac{2}n + (n-1)k \le 0. $$ $$ (a-k)(y+1) \le 0. $$ Debido a $n\ge k+1$,$a-k\ge a-n+1$, lo $a-k$ canot ser negativo, $a\ge k$.

Answer 2

Aquí es una solución alternativa (creo...).

Considerar todos los pares de vértices $v_i, v_j$ tal que $v_i, v_j$ no están conectados por una arista. Llamar a estos pares 'especial'. ¿Cuántos de esos pares hay?

Considere la posibilidad de un vértice $v^{\star}$. No está conectado a $V-\deg(v^{\star})$ vértices. Sumando sobre todos los vértices y dividiendo por $2$ (ya que nos cuente cada par de veces), obtenemos que el número de pares es $$\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$.

Ahora para cada par de vértices $v_1, v_2,$ hemos $$\deg(v_1) + \deg(v_2) \ge 2k.$$ As noted above, each vertex $v^{\estrella}$ is part of $V-\deg(v^{\estrella})$ special pairs. If we sum this relation over all vertices, each vertex $v^{\estrellas}$ will contribute $$\deg(v^{\star})\cdot \frac{V-\deg(v^{\star})}2$$ a la suma ya que se han considerado cada uno de los par dos veces. Por lo tanto, hemos

$$\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.$$

Como user141614 señalado, se puede utilizar de Cauchy-Schwarz para decir $$\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.$$ Por lo tanto, podemos sustituir el problema por una declaración más fuerte que el grado medio es al menos k+1.