Let G be a not complet connected graph. Show that G is k- connected iff any 2 vertices at distance 2 are connected by k internally disjoint paths.

Question

How can I show this? To prove the entire statement I need to break it into two smaller statements:

$\Rightarrow$ If $G$ is $k$-connected then any two vertices at distance two are connected by $k$ internally disjoint paths. I'm stuck in this one.

$\Leftarrow$ If any two vertices at distance two are connected by $k$ internally disjoint paths then $G$ is $k$-connected.

If $G$ contains $k$ internally disjoint paths between any two vertices at distance two then $|V(G)| > k$ and G cannot be separated by fewer than $k $ vertices; thus $G$ is $k$-connected.

Answer 1

We will establish the harder direction:

Claim 1: If $G$ is not $k$-connected then there is a pair of vertices $u,v$ of distance 2 such that there are no more than $k-1$ internally vertex-disjoint paths from $u$ to $v$.

Proof: Suppose that $G$ is not $k$-connected. Then let $S$ be a minimum cut-set of $G$ i.e., $S$ is a smallest set of vertices such that $G \setminus S$ has at least 2 components. Then letting $L_1,\ldots, L_c; c \ge 2$ be the components of $G \setminus S$ we note that every vertex in $S$ has a neighbour in $G$ in every one of $L_1,\ldots, L_c$. [Indeed suppose there is a vertex $u \in S$ that does not have a neighbour in $G$ in every one of $L_1,\ldots, L_c$. Then let us assume WLOG that $c$ is such that $u$ has no neighbour in $G$ in $L_c$. Then note that $L_c$ is a component of $G \setminus (S \setminus \{u\})$ [make sure you see why], which contradicts the assumption that $S$ is a minimum cut-set of $G$.]

So now fix any vertex $y \in S$ and let $x_1$ and $x_2$ be vertices adjacent to $y$ also satisfying $x_1 \in L_1$ and $x_2 \in L_2$. Then as $x_1$ and $x_2$ are in different compoenents of $G \setminus S$ it follws that there is no edge between $x_1$ and $x_2$ in $G$, and as $x_1$ and $x_2$ have a common neighbour, it follws that the distance between $x_1$ and $x_2$ in $G$ is precisely 2. However, the maximum number of internally vertex-disjoint paths between $x_1$ and $x_2$ is at most $|S| < k$. So Claim 1 follows.

So, Claim 1 establishes the harder direction. Can you do the other direction i.e., if $G$ is $k$-connected then for every pair of vertices $u,v$ s.t. $d_G(u,v)=2$, there are at least $k$ interally vertex-disjoint paths in $G$ from $u$ and $v$? There is a hint below.

If there are not at least $k$ interally vertex-disjoint paths in $G$ from $u$ and $v$, then there is a cut-set $S$ that has fewer than $k$ vertices such that $u$ and $v$ are in different components of $G \setminus S$. What is the definition of $k$-connected again?

---

Meanwhile I read your original post more closely. What is the definition of $k$-connected again? You did NOT prove that $G$ is $k$-connected as that would require $k$ internally vertex-disjoint paths between any two vertices $u$ and $v$, not just pairs $u$ and $v$ where $u$ and $v$ are of distance 2 from each other in $G$.