For proving that graph is connected we can also use this theorem

Let G be an n-vertex graph. If every vertex has a degree of at least (n-1) / 2 then G is connected.

Proof: https://books.google.co.in/books?id=g6X2VWuB8qIC&lpg=PP1&pg=PA38#v=onepage&q&f=false

PS: But here we have $2^n$ vertices and Each one has degree n. So here the above theorem is not applicable. To be applicable each vertex should have degree at least ($2^n$ - 1) / 2.