Sea $k < n$ y $G$ un grafo con $n$ vértices, donde la suma de los grados de cualquier $k$ vértices del grafo es menor que $n - k$. Demuestra que $\alpha(G) > k$.
Nota: $\alpha(G)$ representa el tamaño del conjunto independiente máximo.
Intento: Para demostrar que $\alpha(G) > k$, donde $k < n$ y la suma de los grados de cualquier $k$ vértices del grafo es menor que $n - k$, podemos utilizar el concepto de contradicción. Supongamos, para efectos de contradicción, que $\alpha(G) \leq k$. Esto significa que existe un conjunto independiente en $G$ de tamaño $k$ o menos. Sea $S$ dicho conjunto independiente. Dado que $S$ es un conjunto independiente, ningún par de vértices en $S$ son adyacentes en $G$. Por lo tanto, la suma de los grados de los vértices en $S$ es menor o igual que la suma de los grados de cualquier $k$ vértices de $G$. Sin embargo, según la condición dada, la suma de los grados de cualquier $k$ vértices de $G$ es menor que $n - k$. Por lo tanto, la suma de los grados de los vértices en $S$ es menor que $n - k$. ¿Voy por buen camino? ¿Cómo debo continuar?
