# Problem of Graph connectivity with degree sequences

Let $(d_1, d_2, ..., d_n)$ with $0 \leq d_1 \leq d_2 \cdots \leq d_n$ be a degree sequence of a graph. Show that if

$d_j \geq j+k-1$ for all $j: 1, 2, ..., n-1-d_{n-k+1}$. Then $G$ is $k$-connected.

I think the way to do it is by Chvátal theorem, but I can't figure out how to do it.

-
A clarification. Is the "Chvatal Theorem" referring to the Art Gallery Theorem? –  Torsten Hĕrculĕ Cärlemän Jul 23 '13 at 17:37
I believe it refers to Bondy-Chvátal –  Peter Košinár Jul 24 '13 at 11:44

A graph is $k$-connected when deleting any set of fewer than $k$ vertices leaves the graph connected.
Each vertex has at most one edge to any other vertex. Deleting fewer than $k$ vertices leaves each undeleted $d_j$ with a degree at least $j$. When the undeleted $d_j$ are reordered into the increasing sequence $\{d_i\}$ then $d_i \geq i$ and the problem reduces to the $k=1$ case.
With $k=1$, suppose the graph has two disconnected components (a similar argument applies with more than two components). One of the components (call it $A$) must have at least $d_{n}+1$ vertices. That component $B$ with at most $n-1-d_n$ vertices. But $d_j>j$ when $j\leq n-1-d_n$ and the maximum degree of $B$ must be less than the number of vertices in $B$.