Subdivision of G has same connectivity as G

Question

(I am referring to vertex connectivity). It seems intuitive to me that a subdivision of a graph cannot have smaller connectivity, however I am struggling to find a proof of this. Specifically, $K_k$ is $(k-1)$-connected, so shouldn't any subdivision of $K_k$ be at least $(k-1)$-connected as well? Thanks!

**Edit: of course any vertex which is new in the subdivision has degree 2, so deleting those 2 disconnects the graph. But I am looking for the number of vertices whose deletion disconnects the original $k$ vertices of $K_k$.

Answer 1

Hint: think about the edges that are removed when you remove a set of vertices.

In more detail, assume that $G$ is $k$-connected, i.e., that no subset of the vertices of G containing fewer than $k$ vertices separates $G$. Now let $(v, w)$, be an edge of $G$ and let $G'$ be the result of subdividing $(v, w)$, i.e., picking a fresh vertex, $*$ say, and replacing $(v, w)$ by $(v, *)$ and $(*, w)$. If $D$ is a subset of the vertices of $G'$ containing fewer than $k$ vertices that separates $G'$, then clearly we must have $* \in D$ (otherwise $D$ would separate $G$ contradicting our assumption that $G$ is $k$-connected). But then $D' = (D \setminus \{*\}) \cup \{v\}$ has fewer than $k$ vertices and also separates $G'$, because removal of the vertices $D'$ from $G'$ removes all the edges that removal of $D$ removes, with the possible exception of $(*, w)$. So $D'$ must separate $G'$ because removing $(*, w)$ as well as $D'$ can make no difference to the number of connected components, since $(*, w)$ is the only edge containing $*$ when $(v, *)$ has been removed. So $D'$ is a subset of the vertices of $G$ containing fewer than $k$ vertices that separates $G'$ and hence also $G$, contradicting our assumption that $G$ is $k$-connected.