1
$\begingroup$

Suppose that a graph G is k-connected. Prove that $ \delta(G) \geq k $

I understand that a graph is k-connected if it is a graph with at least k+1 vertices and remains connected after removing at most k-1 vertices. And also $\delta(G)$ is the minimum vertex degree for vertices in G. I think I am very close to solving this but I am stuck. My approach: Assume for contradiction that there is a vertex v in G such that the degree of v is less than k, $\deg(v) < k$,so v has at most k-1 vertices adjacent to it. Now I feel there is a connection with removing this particular vertex leads to something but I just can not wrap my head around it. Any hint or help would be highly appreciated.

$\endgroup$
5
  • 1
    $\begingroup$ Don’t remove $v$: remove the $\deg(v)$ vertices adjacent to it. $\endgroup$ May 10, 2020 at 22:15
  • $\begingroup$ @BrianM.Scott aha, so by removing the k-1 vertices adjacent to v, G should still be connected since it is a k-connected graph, but by removing those k-1 vertices, the vertex v will have degree 0, so no edges and thus G is disconnected. Is this the contradiction? $\endgroup$
    – Allorja
    May 10, 2020 at 22:26
  • $\begingroup$ Yep, you’ve got it. You could write that up as an answer and in due course accept it. $\endgroup$ May 10, 2020 at 22:28
  • $\begingroup$ @BrianM.Scott oh thank you very much sir. $\endgroup$
    – Allorja
    May 10, 2020 at 22:29
  • $\begingroup$ You’ve very welcome. $\endgroup$ May 10, 2020 at 22:32

1 Answer 1

3
$\begingroup$

Assume for contradiction that there exists a vertex v in G such that $deg(v) < k$. That is $v$ has at most $k-1$ vertices adjacent to it. By removing those $k-1$ vertices adjacent to v, the graph G should still be connected since it is a k-connected graph. But by doing so, the vertex $v$ becomes an isolated vertex in G, so $deg(v) = 0$ and thus G now is disconnected which contradicts the assumption that G is k-connected. So the degree of $v$ must be at least $k$ and thus we must have that $\delta(G) \geq k$.

$\endgroup$

You must log in to answer this question.

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