Question: For a connected graph $G = (V, E)$ and a positive integer $k$, let $G^k$ be the graph with vertex set $V$ , where two vertices are connected by an edge if and only if their distance in $G$ is at most $k$. Prove: if $G$ is a connected graph on $n$ vertices and $1 \leq k \leq n − 1$ is an integer, then $G^k$ is $k$-connected.
My Answer: (I would love some feedback , is this solution correct? I'm not sure) The diameter of a graph $d$ is defined as the maximal distance between two vertices.
In a complete graph $K_n$ or a $k$-connected graph of $k<n$, the question is trivial (or trivial for steps $1...k$ of raising in power), so let's assume that $G$ is $1$-connected. Note: $G^1=G.$
We notice that $\forall 1\le k \le n-1$ and $\forall v \in V(G) : 1\le \deg_{G^1}(v) \le \deg_{G^2}(v) \le \ldots \le \deg_{G^d}(v)=\deg_{G^n}(v)=n-1$ This is true because $G$ is connected and for every raise in the Power of $G$ we're only adding more edges, thus possibly increasing the degree of each vertex by at least $1$, after reaching the power that equals the diameter, no more edges would be added in raising powers because the maximum length has been covered - thus it is $n$-connected. This implies that $\forall 1\le k \le n-1: k\le \delta(G^k) $.
But $k = \delta(G^k)$ must hold , because if $k$ were smaller then it would contradict the previous inequality in that there were possible for example a vertex with degree $1$ in $G^2$ (this is not possible in a graph $G$ with diameter $>2$, by definition of $G^2$).
But we saw in class that $\kappa(G) < \delta(G)$ therefore by defintion of $\kappa$ and $k$-connectivity $G$ is $k$-connected.
Here's the requested more direct proof by directly verifying that $G^k$ is $k$-connected.
Let $R \subseteq V$ consist of less than $k$ vertices that should be removed from $G^k$. We need to check, that $G^k \setminus R$ (i.e. the graph obtained by removing $R$ from $G^k$), is still connected.
For arbitrary two vertices $f, t$ from $G^k \setminus R$ there is a path from $f$ to $t$ in $G$, because $G$ is connected. We may safely assume that every vertex occurs at most once in this path (i.e. the path is free of loops):
Now consider this path in $G^k\setminus R$. It may have gaps (because of removing the vertices $R$). Each such gap is at most $k-1$ vertices large (because the path was loop-free and because $|R| \le k-1$): $$ f- \cdots - v_l - \underbrace{v_{l+1} - \cdots - v_{l+g}}_{\in R, \quad g \le k-1 \text{vertices}} - v_{l+g+1} - \cdots - t $$ However, by the definition of $G^k$, there is an edge from $v_l$ to $v_{g+1}$ in $G^k$, and thus also in $G^k\setminus R$ (because their distance is at most $g+1$, i.e. at most $k$). So each gap in $G^k\setminus R$ is closed again by an edge from $G^k$. In total, we have a path from $f$ to $t$ in $G^k\setminus R$, hence $G^k\setminus R$ connected and $G^k$ is $k$-connected.