For a connected graph $G$ on $n$ vertices and $1\le k \le n-1$ prove that the graph $G^k$ (where two vertices are connected if their distance is at most $k$) is $k$(-vertex)-connected.
We need to prove that any removal of $k-1$ vertices still leaves $G^k$ connected, or equivalently from Menger's theorem that between any $v,w$ in $G^k$ there are $k$ internally-disjoint paths. I thought perhaps to use induction, and because $G^{k-1}$ is a subgraph of $G^k$ we get $k-1$ internally disjoint paths from $v$ to $w$, but I still don't see how to get another one, using the fact that $G^k$ has more edges than $G^{k-1}$. I also thought maybe to look at $v,w$ in the original graph $G$ and partition $G$ into level sets based on distance, but I wasn't able to really reach anything.
Suppose $S$ is a vertex cut with less than $k$ vertices and $v$ and $w$ are two vertices separated by $S$. If $d_G(v,w)\leq k$, then $v$ and $w$ are neighbours in $G^k$, so they cannot be separated by $S$. Otherwise the shortest path $P$ (in $G$) has at least $k$ internal vertices. In order to avoid that $P-S$ still contains a path from $v$ to $w$ (in $G^k$) $S$ must take away at least $k$ consecutive vertices and this is impossible. Therefore $G^k$ must be $k$-connected.