In the diagram, $A B C D E F G H$ is a cube with an edge length of $12 \mathrm{~cm}$. An ant sits on the cube at vertex $A$. The ant can only walk along the edges of the cube, and cannot walk along any edge more than once. What is the greatest distance that the ant can walk before it cannot continue?
(A) $96 \mathrm{~cm}$
(B) $144 \mathrm{~cm}$
(C) $84 \mathrm{~cm}$
(D) $108 \mathrm{~cm}$
(E) $132 \mathrm{~cm}$

![](https://cdn.mathpix.com/cropped/2024_04_20_e85ef69091c57cb633f3g-118.jpg?height=422&width=430&top_left_y=1075&top_left_x=1373)
This problem requires a fair amount of fiddling around. After some work, we can see that the ant can walk along 9 edges without walking along any edge for a second time. (For example, it could walk $A$ to $B$ to $F$ to $E$ to $A$ to $D$ to $C$ to $G$ to $H$ to $D$. It is then stuck.) In fact, 9 edges, or $108 \mathrm{~cm}$, is the maximum.

Justifying this fact takes us into a really neat area of mathematics called "graph theory". (Graph theory was first developed by Euler when he was working on the Königsberg bridge problem.)

What if the ant could actually walk along 10 edges?

If the ant had done this, it would have walked in and out of a vertex 20 times in total (once at each end of each of the 10 edges). The cube has 8 vertices and each vertex has 3 edges meeting at it, so since the ant has not walked along the same edge twice, then it can only have been in and out of any given vertex at most 3 times.

But for 20 ins and outs with 8 vertices in total, there must be 4 vertices that have been used 3 times.

This is impossible, though, because other than the starting vertex and the ending vertex in the path, the ant must go both in and out of a vertex, so each vertex other than the starting and ending vertices must be used an even number of times. So we cannot have more than 2 vertices being used an odd number of times.

Therefore, the ant cannot walk along 10 edges, so $108 \mathrm{~cm}$ must indeed be the maximum.

Answer: (D)