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

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!

-

## 3 Answers

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 ;-)

-
Nice, I just need to ask, does there exist a simpler proof for this? –  Bruce Feb 16 '13 at 3:00
Isn't Joe Zeng's proof simpler? If you were to expand his hint, just do induction again, where the hypothesis is "after removing $n-1$ vertices the $n$-cube stays connected". It is true if all the removed vertices have a common neighbor, and if not, then you split your cube into two parts (there must be an index where they differ) that have at most $n-2$ removed vertices and you apply the inductive hypothesis. –  dtldarek Feb 16 '13 at 7:56

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?

-
Deleting n-1 vertices must result in a bridge in the graph, right? Sorry but I can't figure out how to prove the presence of a bridge with that hint.. –  Bruce Feb 15 '13 at 22:09
I was more thinking that the graph will always stay connected after removing $n-1$ vertices. It doesn't necessarily need to be a bridge. –  Joe Z. Feb 15 '13 at 23:36
And if you remove all $n$ vertices adjacent to one vertex, that one vertex is then disconnected from the rest of the graph. –  Joe Z. Feb 15 '13 at 23:36
Oops I got confused with edge connectivity there. –  Bruce Feb 16 '13 at 2:55
I really need a formal explanation/proof, can you give one? How can it be said that the graph will always remain connected after removing n-1 vertices? I'm unable to understand! –  Bruce Feb 16 '13 at 2:59

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?

-
Well, this is exactly the proof I've given, not the first time of "someone has been here before". –  dtldarek Feb 16 '13 at 7:59