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.

  • $\begingroup$ The claim doesn't say that $G^k$ is not $l$ connected for $l \ge k$, it just says that it is $k$ connected. $\endgroup$ – ctlaltdefeat Dec 26 '14 at 15:45
  • $\begingroup$ 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$ $\endgroup$ – ctlaltdefeat Dec 26 '14 at 15:51
  • 1
    $\begingroup$ Sorry! I shouldn't have commented before the morning coffee. $\endgroup$ – 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.

  • $\begingroup$ 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$? $\endgroup$ – ctlaltdefeat Dec 26 '14 at 18:10
  • $\begingroup$ 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). $\endgroup$ – Leen Droogendijk Dec 26 '14 at 18:28
  • 1
    $\begingroup$ 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$ $\endgroup$ – ctlaltdefeat Dec 26 '14 at 20:17
  • $\begingroup$ Done, thanks... $\endgroup$ – Leen Droogendijk Dec 27 '14 at 5:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.