Suppose we have a $3\times 3\times 3$ cube of cubes (i. e. $27$ cubes) and consider the graph whose vertices are the cubes, and let an edge connect two iff they have touching faces. I'm quite sure there is no Hamilton path that starts at the middle cube and ends in a corner cube, though I'm not sure how to prove it without tedious casework.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
If you give 3D coordinates to the cube nodes $(x,y,z)$. Two nodes are adjacent iff they differ by exactly $1$ in exactly one of the coordinates.
Consider $x+y+z$. The parity(whether it is even or odd) of this flips each time you move to an adjacent node.
The parity of the center cube and the corner cube are different. In 26 moves, you will end up at a node with the same parity as the initial node.
So no Hamiltonian Path can exist which starts at the center cube and ends at a corner cube.
Here is a more general framework for problems of this kind.
A bipartite graph is one for which the vertices can be divided into two sets so that any edges only join vertices which are not in the same same one of these two sets. Bipartite graphs can be vertex colored with two colors and any circuits they have must have even length. If the two color sets of the bipartite graph differ in size then the graph can not have a hamiltonian circuit and if the two color sets differ by two the graph can not have a hamiltonian path. If the two color sets differ by 1 any hamiltonian path must start and end at vertices of the same color. If a bipartite graph has color sets of equal size it may or may not have a hamiltonian circuit. For example the 1x1x1 cube has a hamiltonian circuit but the rhombic dodecahedron does not.
A famous conjecture of David Barnette suggests that every planar 3-connected 3-valent bipartite graph has a hamiltonian circuit. Another way of putting this is that the graphs of 3-valent convex polyhedra all of whose faces have an even number sides have hamiltonian circuits.