Consider a large cube composed of 5 × 5 × 5 smaller cubes. Construct a graph by

Question

Consider a large cube composed of 5 × 5 × 5 smaller cubes. Construct a graph by placing a vertex inside each of the 125 cubes and joining two vertices by an edge if the corresponding cubes are adjacent. Find a simple argument that the resulting graph is not Hamiltonian.
Two cubes are regarded as adjacent if they share a square face. So the "inner" cubes each have six adjacent cubes. The graph in question has 125 vertices -- one for each of the cubes. Two vertices are joined by an edge if and only if the associated cubes are neighbors.

Our teacher said it was one of those "ah ha!" moments. I've been looking/thinking/searching for clues/beating my head on the table for a week and I never got the "ah ha!" moment.

Explanation / Answer

Firstly note that this graph is bipartite, i.e., it has no odd cycles. Hence you can think of the vertex set as partitioned into 2 sets A,B such that every edge is from A to B. The moment you see this, the ah-ha moment is right there. Since the graph is bipartite, it can be Hamiltonian if and only if there are the same number of vertices on each part A, B which means that in particular, there are an even number of vertices in the graph. But this graph has 125 vertices which is odd.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.