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.

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

  • $\begingroup$ Why does the smallest component have at most $n-k+1\over 2$ vertices? $\endgroup$ – Mike Feb 26 '14 at 22:19
  • $\begingroup$ @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. $\endgroup$ – bof Feb 26 '14 at 23:45
  • $\begingroup$ I see, I was thinking something crazy that didn't make sense. Thank you for your help. Everything is crystal clear now. $\endgroup$ – Mike Feb 26 '14 at 23:57
  • $\begingroup$ Oops, where I wrote "$G$ has $n-k+1$ vertices" I meant $G-S$. $\endgroup$ – 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.

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

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.