# A $3 \times 3 \times 3$ cube has no Hamiltonian path starting at the corner.

We have a $$3\times3\times 3$$ cube which has $$27$$ cubes each $$1\times1\times1$$ stuck together as usual. $$2$$ cubes are neighbours if they have a common face. The corner cubes are the $$8$$ cubes at the corners of the big cube. Can the worm start from a corner cube and eat its neighbour cube, continuing until at the end the last cube eaten is the one in the center of the big cube which has 6 neighbour cubes?

Let me give a graphic theoretical argument

Hamiltonian Path: A path that visits each vertex exactly once

The problem statement is equivalent to determining whether there exists a Hamiltonian path on the 3-cube starting from a corner and ending at the center. We can describe the 3-cube as 27 lattice points. Without loss of generality, let the corner in which the mouse starts be the point $(0,0,0)$. Note that every edge along a path in the 3-cube will change the parity of the coordinate the mouse is at. A Hamiltonian path that traverses 27 vertices must contain exactly 26 edges.Therefore the origin and terminus of any Hamiltonian path on a 3-cube will be of the same parity. Since the center point is at $(1,1,1)$,there is no Hamiltonian path that starts at a corner and ends at the center. Done.

HINT: Color the small cubes alternately black and white, like a three-dimensional checkerboard. Say the eight corner cubes are black.

• How many ‘steps’ from one cube to a neighbor must the worm make in order to eat all of the cubes?
• What color cube must the worm eat last?
• What color is the centre cube?

(Note that I’m assuming that you want the worm to eat all of the cubes, though you didn’t say so. If I’m wrong, please clarify the statement of the problem.)

This appears as a question in Graph Theory in the sections discussing Hamiltonian graphs. A Hamiltonian graph is a graph containing a closed path which spans all the vertices of the graph. We can intuitively relate the vertices to be the cheese blocks. Hence if the graph constructed by assuming the cheese blocks to be vertices had a Hamiltonian path, the worm could traverse through it. Note I have mentioned a Hamiltonian path not a cycle. In the context of the proof, we need a Hamiltonian cycle hence we need to add a hypothetical edge between his first cheese block and the last cheese block(the vertex at the centre).

Any undergraduate level text in graph theory will have a theorem more or less like:
A non-Hamiltonian graph is degree majorised by some $$\mathbb C_{mn}$$ $$\forall$$ $$m \in(0, {\frac n2})$$.

Where the $$\mathbb C_{mn}$$ graph is defined as $$\mathbb K_m\land(\mathbb K_m^c + \mathbb k_{n-2m})$$. Where $$\mathbb K_m$$ is a complete graph on m vertices.

It is easily seen that for some $$m \in (0, 13)$$ {e.g. m=5} there exists a $$\mathbb C_{m27}$$ that degree majorises our graph. Hence we conclude our graph is non-Hamiltonian, and there exists no way in which the worm can burrow his way through the cheese cube in the desired manner. For proof and better understanding of the theorem look up Graph Theory and Applications Chapter 4.

• Could you elaborate the theorem about non-Hamiltonian graph majorization? I don't get the meaning of $\mathbb{K}_m^c$ and the "or" and "+" symbol in terms of graphs. – Lada Dudnikova Aug 30 '19 at 11:25