By $K_v$ I mean the minimun amount of vertices to be removed from a connected graph such that it loses its connectivity
We define the Graph $G_n$ as a graph with $3^n$ vertices, where each vertex has an assigned string of $n$ digits 0, 1 or 2, and two vertices are connected if and only if they differ in exactly one bit
I want to prove that the Graph $G_n, n \ge 2$ is $2n$-connected, but I always get stuck
I tried to show that between any two vertices there are $2n$ disjoint paths that connect them, but I can't find an easy way of proving it.
I also tried by induction, saying that $G_n$ is connected and then building $G_{n+1}$ with 3 copies of $G_n$, but I also can't seem to go anywhere
What else can I try?
Let the enemy erase $2n-1$ vertices and select two of the remaining vertices. Put a token on each of the selected vertices; our job is now to move the tokens along the graph until they meet. (This will prove that there was a path between the two selected vertices).
If the two tokens have no coordinate in common, show that it is possible to move one of them a single step such that they now have a coordinate in common.
We can thus assume that the two tokens have at least one coordinate in common. Without loss of generality let's suppose they are both in layer $0$.
If fewer than $2(n-1)$ nodes have been erased in layer $0$, then we can (by induction) connect the two vertices in layer $0$ alone. But otherwise there can be at most one erased node in layers $1$ and $2$, so one of these layers is completely without erasures. Move each token up to that layer and then the rest is easy.
Specialized base cases will be needed for $n\le 2$; I will leave those to you.