Problema de la conectividad Graph con secuencias de grados

Question

Sea$(d_1, d_2, ..., d_n)$ con$0 \leq d_1 \leq d_2 \cdots \leq d_n$ una secuencia de grados de un gráfico. Mostrar que si

$d_j \geq j+k-1$ para todos $j: 1, 2, ..., n-1-d_{n-k+1}$. Entonces$G$ es$k$ - conectado.

Creo que la forma de hacerlo es por el teorema de Chvátal, pero no puedo averiguar cómo hacerlo.

Answer 1

Un grafo es $k$-conectado al eliminar cualquier conjunto de menos de $k$ vértices deja el gráfico conectado.

Cada vértice tiene más de un borde a cualquier otro vértice. La eliminación de menos de $k$ vértices hojas de cada recupera $d_j$ con un grado mínimo de $j$. Cuando la recupera $d_j$ se reordenan en el aumento de la secuencia de $\{d_i\}$$d_i \geq i$, y el problema se reduce a la $k=1$ de los casos.

Con $k=1$, suponga que la gráfica tiene dos desconectado componentes (un argumento similar se aplica con más de dos componentes). Uno de los componentes ( $A$ ) debe tener al menos $d_{n}+1$ vértices. Ese componente $B$ con $n-1-d_n$ vértices. Pero $d_j>j$ al $j\leq n-1-d_n$ y el máximo grado de $B$ debe ser menor que el número de vértices en $B$.