# $G^k$ is $k$-connected

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.

• The claim doesn't say that $G^k$ is not $l$ connected for $l \ge k$, it just says that it is $k$ connected. – ctlaltdefeat Dec 26 '14 at 15:45
• I'm not sure what you mean by edge weights, the question refers to a simple undirected graph. ${K_5}^1=K_5$ is 5-connected so it is also $k$-connected for $k\le n-1$ – ctlaltdefeat Dec 26 '14 at 15:51
• Sorry! I shouldn't have commented before the morning coffee. – ml0105 Dec 26 '14 at 15:52

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.

• Why must $S$ take away at least $k$ consecutive vertices? How do we know that taking out just one of the internal vertices isn't enough to separate $v$ from $w$? – ctlaltdefeat Dec 26 '14 at 18:10
• If the path is $v_1,v_2,\ldots,v_n$, in $G_2$ we can jump from $v_1$ immediately to $v_3$, in $G_k$ we can jump from $v_1$ to $v_{k+1}$, so to block our path in $G_k$, $k$ consecutive vertices must be removed. (Jump from $v_1$ to $v_3$ meaning: $v_1$ and $v_3$ are adjacent). – Leen Droogendijk Dec 26 '14 at 18:28
• Thanks, simpler than I expected, was approaching it the wrong way :) In order to help future readability you could correct the $x$ and $y$ to $v$ and $w$ – ctlaltdefeat Dec 26 '14 at 20:17
• Done, thanks... – Leen Droogendijk Dec 27 '14 at 5:58