Límite en los bordes del gráfico

Question

Necesito ayuda con el siguiente problema.

Supongamos que tengo un gráfico $G$ $n$ elementos tales que cada borde $e$ falta de ella, está contenida en una copia de $K_s$ (grafo completo os $s$ vértices) en $G$ $e$ añadido. Necesito demostrar que $$ \left| E(G) \right| \geq {n \choose 2} - {n-s+2 \choose 2} $$ $\left| E(G) \right|$ es el número de bordes de $G$

Agradezco cualquier ayuda o ideas, gracias.

Answer 1

He resuelto el problema. Es por inducción sobre el número de vértices.

El caso base donde $n=s$ es trivial. Ahora esto significa que $G$ tiene al menos un par de vértices $x$ $y$ sin bordes y entre ellos. Por la propiedad de la gráfica tiene hay un $K_{s-2}$ $G$ tanto $x$ $y$ están conectados a cada vértice $K_{s-2}$.

Construimos un nuevo gráfico de $G'$ de la siguiente manera, eliminamos $y$$G$, y para cada vértice $z$ que estaba conectado a $y$ que no estaba en ese $K_{s-2}$ añadimos un borde entre el $z$ $x$ (Si no lo estaba ya conectado). De esta manera $G'$ tiene uno menos vértice, y hemos eliminado al menos $s-2$ bordes. Y por $G$ no $K_s$ gráfico contiene tanto $x$$y$, al mismo tiempo, y $x$ puede sustituir a $y$ no alteramos la propiedad. Por lo que la aplicación de la inducción tenemos

$$ \begin{align} |E(G)| &\geq |E(G')| + s - 2\\ &\geq {n-1 \choose 2} - {n-1-s+2 \choose 2} + s - 2\\ &= \left({n-1 \choose 2} + n \right) - \left({n-1-s+2 \choose 2} + n - s + 2 \right)\\ &= {n \choose 2} - {n-s+2 \choose 2} \end{align}$$

Answer 2

Para $n < s$ gráfico $G$ debe ser completa y la desigualdad, obviamente, se mantiene, por lo tanto más $n \ge s$. Vamos a probar la desigualdad por inducción en $n$ para cualquier constante $s$.

La base es $n = s$. En este caso, $|E(G)| \ge \binom n2 - \binom{n-n+2}{2} = \binom n2 - 1$ es verdad, porque si $G$ tiene falta de borde de $e$,$G + e \cong K_s$, por lo que todos los demás bordes están presentes, y en caso contrario, $G$ es completa.

Si $n > s$ vamos a considerar subgrafo $H \subset G$ $n - 1$ vértices y excluidos vértice $v \in V(G) \setminus V(H)$. Tenemos $$\deg_G v \ge s-2,$$ because if $v$ is universal (adjacent to all other vertices), then $\deg_G v = n - 1 > s - 1 \ge s - 2$, and otherwise there is a missing edge $e = vu$ such that $G + e$ has clique $C$ of size $s$ containing vertex $v$, that implies $\deg_{G+e} v \ge s - 1$ and $\deg_G v \ge s - 2$. También por hipótesis de inducción $$|E(H)| \ge \binom{n-1}2 - \binom{n-1-s+2}2.$$ Y, finalmente, $$\begin{align}|E(G)| = |E(H)| + \deg_G v & \ge \binom{n-1}2 - \binom{n-1-s+2}2 + s-2 =\\ &=\binom{n-1}2 +\binom{n-1}1 - \binom{n-1-s+2}2-\binom{n-1-s+2}1 =\\ &= \binom n2 - \binom{n-s+2}2. \end{align}$$