The figure below shows a cube with edge 1.

![](https://cdn.mathpix.com/cropped/2024_05_01_cc59d970f26105cc4ca1g-09.jpg?height=494&width=540&top_left_y=455&top_left_x=861)

a) What is the minimum possible length for a path formed by the edges of the cube that passes through all 8 vertices?

The figure below shows a cube with edge 1 in which all 12 face diagonals have been drawn. Thus, a network has been created with 14 vertices (the 8 vertices of the cube and the 6 centers of the faces) and 36 edges (the 12 of the cube and 4 more on each of the 6 faces).

![](https://cdn.mathpix.com/cropped/2024_05_01_cc59d970f26105cc4ca1g-09.jpg?height=494&width=568&top_left_y=1346&top_left_x=844)

b) What is the minimum possible length for a path formed by the edges of this network that passes through all 14 vertices?
Solution

a) The figure below represents a piece of paper, containing eight squares of side 1 positioned side by side.

![](https://cdn.mathpix.com/cropped/2024_05_01_cc59d970f26105cc4ca1g-32.jpg?height=494&width=605&top_left_y=1232&top_left_x=631)

Notice that, by folding the paper along the edges that are common to two squares, we will obtain a cube of side 1 as described in the exercise. Thus, it is equivalent to think of paths in this figure or in the cube described in the exercise. To facilitate the description of the paths, we will always think of this figure.

The vertices of the resulting cube are numbered as shown in this figure. Notice that the numbers 8, 7, 2, 3, 4, and 5 appear twice in this numbering. This is because, when we fold the paper, the two vertices marked with the same number will coincide.

Since the distance between each pair of adjacent vertices in the figure above is equal to 1, any path passing through 8 distinct vertices must have a minimum length of 7.

Consider the path

$$
1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 6 \rightarrow 7 \rightarrow 8
$$

drawn in the figure below.

![](https://cdn.mathpix.com/cropped/2024_05_01_cc59d970f26105cc4ca1g-33.jpg?height=491&width=614&top_left_y=234&top_left_x=824)

This path passes through all the vertices of the cube and has a length of 7. Thus, the answer to the exercise is 7.

b) As in the solution to part a), consider the figure below, which represents a piece of paper containing eight squares of side 1 positioned side by side.

![](https://cdn.mathpix.com/cropped/2024_05_01_cc59d970f26105cc4ca1g-33.jpg?height=479&width=614&top_left_y=1174&top_left_x=824)

This time, we have also added the vertices located at the centers of each of the squares, as well as the diagonals of the squares that pass through these vertices.

As in the previous part, by folding the paper along the edges that are common to two squares, we will obtain a cube of side 1 as described in this part of the exercise. Thus, it is equivalent to think of paths in this figure or in the cube described in this part of the exercise. To facilitate the description of the paths, we will always think of this figure.

We use the numbers 1 to 8 to mark the vertices that are on the edges of the cube, and the letters from $a$ to $f$ to mark the vertices located at the centers of the faces of the cube. Thus, the total number of vertices is 14. Notice that the numbers appear twice in this numbering, due to the fact that, when we fold the paper, the two vertices marked with the same number will coincide.

Consider the path

$$
1 \rightarrow a \rightarrow 2 \rightarrow b \rightarrow 3 \rightarrow c \rightarrow 4 \rightarrow 5 \rightarrow d \rightarrow 6 \rightarrow e \rightarrow 7 \rightarrow f \rightarrow 8
$$

highlighted in the figure below:

![](https://cdn.mathpix.com/cropped/2024_05_01_cc59d970f26105cc4ca1g-34.jpg?height=480&width=602&top_left_y=231&top_left_x=630)

This path consists of 12 segments connecting a vertex marked with a number to a vertex marked with a letter (for example, the segment $1 \rightarrow a$) and only one segment connecting two vertices marked with numbers (namely, the segment $4 \rightarrow 5$). Note that each segment connecting a vertex marked with a number to a vertex marked with a letter has a length of $\sqrt{2} / 2$. On the other hand, the segment connecting vertex 4 to vertex 5 has a length of 1. Thus, the total length of the path described above is $12 \times \sqrt{2} / 2 + 1 = 6 \sqrt{2} + 1$.

We will now show that no other path containing the 14 vertices can have a length smaller than the path we highlighted above. Indeed, any path containing the 14 vertices must, necessarily, contain a minimum of 13 segments. Each segment could, in principle, be of three different types:

- connecting a vertex marked with a number to a vertex marked with a number;
- connecting a vertex marked with a number to a vertex marked with a letter.

In the first case, the segment has a length of $\sqrt{2} / 2$, while in the second, it has a length of 1. Thus, to minimize the length of the paths, we should use the maximum possible number of segments with a length of $\sqrt{2} / 2$.

A path that only contained segments connecting a vertex marked with a number to a vertex marked with a letter would have to contain the same number of vertices of each type, since each segment starts at a number and ends at a letter. Since we have a total of eight vertices marked with numbers and only six marked with letters, any path that passes through all 14 vertices must contain a segment connecting two vertices marked with numbers, i.e., a segment of length 1.

Thus, the path we highlighted above is an example of a path containing all the vertices of the cube and that contains the minimum allowed number of segments with a length of 1, so it has the smallest possible length. Therefore, the answer to this part is $6 \times \sqrt{2} + 1$.