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

where, $$\delta(G) = \text{minimum degree of a vertex in } G.$$

• It never hurts to explain you notation: what is $\delta$? Commented Feb 26, 2014 at 5:55
• Sorry, $\delta(G)$ is the minimum degree of $G$.
– Mike
Commented Feb 26, 2014 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. Commented Feb 26, 2014 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
Commented Feb 26, 2014 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
Commented Feb 26, 2014 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
Commented Feb 26, 2014 at 23:57
• Oops, where I wrote "$G$ has $n-k+1$ vertices" I meant $G-S$.
– bof
Commented Feb 27, 2014 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. Commented Feb 26, 2014 at 6:40