8
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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