Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

3 Answers 3

up vote 2 down vote accepted

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

share|improve this answer
    
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?

share|improve this answer
    
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

enter image description here

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.