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?
Best Answer
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.