# k-connected graph and min vertex degree

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.

• Don’t remove $v$: remove the $\deg(v)$ vertices adjacent to it. May 10, 2020 at 22:15
• @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? May 10, 2020 at 22:26
• Yep, you’ve got it. You could write that up as an answer and in due course accept it. May 10, 2020 at 22:28
• @BrianM.Scott oh thank you very much sir. May 10, 2020 at 22:29
• You’ve very welcome. May 10, 2020 at 22:32

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