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