1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ It never hurts to explain you notation: what is $\delta$? $\endgroup$ Commented Feb 26, 2014 at 5:55
  • $\begingroup$ Sorry, $\delta(G)$ is the minimum degree of $G$. $\endgroup$
    – Mike
    Commented Feb 26, 2014 at 5:56
  • 2
    $\begingroup$ Include all relevant information in the question itself (you can edit the question to add to it): it works best that way. $\endgroup$ Commented Feb 26, 2014 at 5:57

2 Answers 2

12
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Why does the smallest component have at most $n-k+1\over 2$ vertices? $\endgroup$
    – Mike
    Commented Feb 26, 2014 at 22:19
  • 1
    $\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
    Commented Feb 26, 2014 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
    Commented Feb 26, 2014 at 23:57
  • $\begingroup$ Oops, where I wrote "$G$ has $n-k+1$ vertices" I meant $G-S$. $\endgroup$
    – bof
    Commented Feb 27, 2014 at 0:28
4
$\begingroup$

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .