If G is k-vertex-connected then G-v is k-1-connected

Question

Prove that if $G$ is k-vertex-connected then for every $v$ in $V(G)$, $G-V$ is (k-1)-vertex connected. I will appreciate any hints.

Answer 1

Suppose $S$ is a vertex set with $k-2$ vertices in $G\setminus\{v\}$. We want to prove that $(G - \{v\})\setminus S$ is still connected. Now assume for a contradiction that $(G - \{v\})\setminus S$ is not connected, say, there are $2$ components $A$, $B$ in $(G - \{v\})\setminus S$. Consider that in $G$, the vertex $v$ is not in $S$, and $G$ is $k$-connected, which means that $v$ must be in $A$ or $B$ or connecting both $A$ and $B$. If $v$ is in $A$ and not in $B$, then $G\setminus S$ must be disconnected, and likewise if $v$ is in $B$ and not in $A$.

Consider if $v$ is in both $A$ and $B$, then in $G\setminus S$, $v$ is a cut-vertex. So, together with $S$ (that is, $S \cup \{v\}$) it will form a vertex cut-set of size $k-2+1=k-1$ in $G$, contradicting our assumption that $G$ is $k$-connected.