Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.