# proving Hamiltonian path doesnt exist

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?

• There aren't any Hamiltonian cycles – user399601 Apr 9 '17 at 16:08
• Have you tried your argument when $n=2$? – Patrick Stevens Apr 9 '17 at 16:47
• sorry im an idiot – 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.