Consider the n-dimensional cube $Q_n$. In class, we see that $Q_n$ is bipartite by considering the partition $\{V_1, V_2\}$ where $ V_1 $ denotes the set of vertices that have an odd number of 1s and $V_2$ denotes the set of vertices that have an even number of 1s. Suppose n is even. Explain why there is no Hamiltonian path in $Q_n$ that starts at the vertex $00 . . . 0$ and ends at the vertex $11 . . . 1$

My argument was as follows for n even $111...11$ always has an odd number of ones and $0000..000$ obviously has even. now in any bi bipartite graph every cycle is of even length. now in a Hamiltonian path we wish to include every vertex but not land back on our starting point i claim this is only possible when our start and end points belong to the same Vertex set. consider a Hamiltonian cycle starting at $00000$ now step back from the last edge traversed in this cycle we have many options to pick to create a Hamiltonian path in fact w.o loss of generality there is a Hamiltonian path starting at 0000...00 that can end at any vertex in the same vertex set as $000...000$

Why doesn't this work? and is there some way to show this w.o a counting argument?

  • $\begingroup$ There aren't any Hamiltonian cycles $\endgroup$ – user399601 Apr 9 '17 at 16:08
  • $\begingroup$ Have you tried your argument when $n=2$? $\endgroup$ – Patrick Stevens Apr 9 '17 at 16:47
  • $\begingroup$ sorry im an idiot $\endgroup$ – Faust Apr 9 '17 at 19:31

Take a bipartite graph where the two vertex classes $A$ and $B$ are the same size, both even in size. Then a Hamiltonian path which starts in $A$ must end in $B$. (Indeed, the Hamiltonian path matches first an element of $A$ to an element of $B$; then another element of $A$ to another element of $B$; and so on. We can't end the path in $A$, because that means we've missed at least one element of $B$ since $A$ and $B$ are the same size.)

When $n$ is even, the two specified corners of the cube are in the same vertex class, so there can't be a Hamiltonian path between them.

| cite | improve this answer | |

Your Answer

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

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