Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose we have a 3x3x3 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.

share|improve this question
    
You seem to be asking questions on the same topic. Are we doing your homework for you? –  Aryabhata Sep 23 '10 at 16:41
    
Sorry, I'm just going through a text on graph theory and asking my questions here. They are problems in the text but it doesn't give solutions. Are such questions not allowed here? –  user1960 Sep 23 '10 at 16:57
4  
If you just mention that, people would be more willing to help you, especially when the questions sound like homework. I hope you understand. btw, I just undeleted an answer which I had added. –  Aryabhata Sep 23 '10 at 16:59

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer
    
This is really clever, could you explain the motivation behind it? Had you seen the problem before? –  user1960 Sep 23 '10 at 17:03
1  
@user: Yes, I had heard this before. Considering parity like this is a useful trick. In terms of graph theory, it is a bipartite graph. For a classic, see this: en.wikipedia.org/wiki/Mutilated_chessboard_problem –  Aryabhata Sep 23 '10 at 17:06

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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