How to prove that connectivity of a n dimensional hypercube $H_n$ is n ( $H_n$ is a graph whose vertices are the binary strings of length n, two vertices are adjacent iff they differ in exactly 1 bit) , i tried to do it with induction on n assuming nth dimensional cube is of connectivity n however i got stuck in middle of it (also tried like going down from n+1 to n which is not working too), on a side note while doing this I derived that, no of edges in a hypercube $H_n$ is $n * 2^{n-1}$

  • 1
    $\begingroup$ Are you allowed to approach this question algebraically? If so, then consider that the hypercube is vertex-transitive. Moreover, it is also a minimal Cayley graph and so its connectivity is equal to its valency (=vertex degree). $\endgroup$ – Curiosity Mar 17 '15 at 20:26
  • $\begingroup$ Ty for the reply, I discovered a solution a while ago, used induction with induction hypotheses that a hypercube $H_n$ has connectivity n, divided the $H_{n+1}$ graph into two, one where 1st bit are all 0's and other where 1st bit are all 1's, now both these subgraphs of length n (excluding first bit) has connectivity n and then all the similar type of strings which are present in both the subgraphs will be connected since they differ by 1 bit, thus we have n+1 connectivity for $H_{n+1}$ , is this a valid solution? $\endgroup$ – Cloverr Mar 17 '15 at 20:43
  • $\begingroup$ @Nilanjan: The idea is sound, but it needs a bit of expansion before it becomes an actual proof. $\endgroup$ – Brian M. Scott Mar 18 '15 at 3:04
  • $\begingroup$ @BrianM.Scott: i couldn't get which part of proof you are referring to,can you tell which part needs expansion $\endgroup$ – Cloverr Mar 18 '15 at 18:18
  • 2
    $\begingroup$ @Nilanjan: You need to explain clearly exactly why removing $n$ vertices from $H_{n+1}$ leaves a connected graph. Note that the explanation when all of the removed vertices are in one copy of $H_n$ is different from the explanation when they are not. You should also explain why the connectivity of $H_{n+1}$ is not more than $n+1$. $\endgroup$ – Brian M. Scott Mar 19 '15 at 0:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.