Proof that a n-hypercube is n-vertex-connected

Question

I'm new to graph theory, I'm finding it hard to get upon proofs.

To prove: An n-hypercube is n-vertex connected. Approaches I thought:

• It holds true for n=2, so assume it holds true for n=k-1, and prove it for n=k, so its proved by induction.

• Prove that there are n vertex disjoint paths between every pair of points (u,v) in the n-hypercube, then it's n-vertex connected. (right?)

Can someone please point me in the right direction? What different approaches are possible for this problem?

I'm unable to get think of solutions myself clearly. But after I know a solution, it seems easy. I want to improve my problem solving skills in graphs. Which types of problems would you recommend me to start with? Any resources would be highly appreciated. Thanks!

Answer 1

To show that your approaches work, let's prove that there are $n$ disjoint path's by induction ;-)

It definitely works for $n = 2$, so assume it holds true for $n = k-1$. Let $u = (u_0,u_1,\ldots,u_{n-1})$ and $v = (v_0,v_1,\ldots,v_{n-1})$. Now, there are two cases:

• Vertices $u$ and $v$ have some common index $i$ such that $u_i = v_i$. By removing this index and applying induction hypothesis we get $n-1$ disjoint paths. The $n$th path $$u \leadsto u[i\to 1-u_i] \leadsto^* v[i\to 1-v_i] \leadsto v$$ is surely disjoint, because it differs at index $i$ all the time.
• Vertices $u$ and $v$ differ on all the indexes. WLOG we can assume that $u_i = 0$ and $v_i = 1$ for all $i$. The $k$th path goes like this: $$0 \leadsto e_k \leadsto e_k+e_{k+1} \leadsto^* e_k+\ldots+e_{n-1}+e_0+e_1+\ldots+e_{k-2} \leadsto 1,$$ or equivalently, $j$th vertex of $k$th path equals $$\sum_{i=k}^{k+j-1}e_{i\ \bmod\ n},$$ where $e_i = (0,0,\ldots,0,1,0,0,\ldots)$ has a single $1$ (one) at $i$th place.

I hope it helps ;-)

Answer 2

Hint: Consider that every vertex of an $n$-hypercube is connected to $n$ vertices. What does this mean about deleting any $n - 1$ vertices in the cube?

Answer 3

I found a proof in Introduction to Graph Theory by Douglas B. West

@Joe Zeng, @dtldarek please have a look at this. What are your thoughts on this?