# Show that $G$ is $k$-connected?

Let $G$ be a graph of order $n$ and let $k$ be an integer with $1\leq k\leq n-1$. Prove that if $\delta(G)\geq (n+k-2)/2$, then $G$ is $k$-connected.

• It never hurts to explain you notation: what is $\delta$? – Mariano Suárez-Álvarez Feb 26 '14 at 5:55
• Sorry, $\delta(G)$ is the minimum degree of $G$. – Mike Feb 26 '14 at 5:56
• Include all relevant information in the question itself (you can edit the question to add to it): it works best that way. – Mariano Suárez-Álvarez Feb 26 '14 at 5:57

Assume for a contradiction that $G$ is not $k$-connected. Since $n\gt k$, this means there is a set $S\subseteq V(G)$ such that $|S|=k-1$ and $G-S$ is disconnected. Then $G-S$ has $n-k+1$ vertices, and so the smallest component of $G-S$, call it $H$, has at most $\frac{n-k+1}2$ vertices. Let $v$ be any vertex in $H$; then $v$ is joined only to other vertices in $H$ and vertices in $S$, so $$\deg v\le\frac{n-k+1}2-1+(k-1)=\frac{n+k-3}2\lt\frac{n+k-2}2\le\delta(G),$$ a contradiction.

• Why does the smallest component have at most $n-k+1\over 2$ vertices? – Mike Feb 26 '14 at 22:19
• @Paul Since $G$ has $n$ vertices and $S$ has $k-1$ vertices, $G$ has $n-k+1$ vertices. Since $G-S$ is disconnected, it has at least two components; therefore, its smallest component contains at most half of those vertices. – bof Feb 26 '14 at 23:45
• I see, I was thinking something crazy that didn't make sense. Thank you for your help. Everything is crystal clear now. – Mike Feb 26 '14 at 23:57
• Oops, where I wrote "$G$ has $n-k+1$ vertices" I meant $G-S$. – bof Feb 27 '14 at 0:28

Hint: Apply Dirac's Theorem.

Let $K\subset G$ be a set of $k-1$ vertices. Consider $G-K$, which has $n-k+1$ vertices.

The minimum degree is $\frac{ n+k-2}{2} - (k-1) = \frac{n-k}{2}.$

Consider $G-K + v$, where we add a special vertex $v$ that is connected to all vertices of $G-K$. It has $n-k+2$ vertices.

The minimum degree is $\frac{n-k+2} {2}$.

Hence, by Dirac's Theorem, a Hamiltonian circuit exists.

Now delete $v$, and we get a Hamiltonian path. Thus, $G-K$ is connected.

• @bof Ah I'm not too familiar with that term. Thanks! Updated the solution. – Calvin Lin Feb 26 '14 at 6:40