\section*{Problem 4 - 161024}

Given is a cube \(A B C D E F G H\).

Determine all different paths composed solely of cube edges that have the following properties:

(1) The path starts and ends at point A.

(2) Each vertex of the cube is reached exactly once when the path is traversed once.

Two paths are considered different if and only if there is a cube edge that is included in one of the paths but not in the other. In particular, paths that differ only in the traversal direction are not considered different.
}

Each of the sought-after paths must contain exactly two edges of the cube emanating from \(A\), i.e., exactly two of the three edges \(A B, A D, A E\). The path can be chosen such that it either starts with \(A B\) or with \(A D\).

1. If it starts with \(A B\), it can only continue with one of the remaining two edges emanating from \(B\), i.e., either as \(A B C\) or as \(A B F\).

1.1 After the continuation \(A B C\), only the possibilities \(A B C D\) and \(A B C G\) remain.

1.1.1 With the choice of \(A B C D\), there is only one possibility for continuation from both \(A\) and \(D\), namely to \(E\) and \(H\), respectively. Then all points are covered, and the path can only be closed by the edge \(F G\).

Thus, in case 1.1.1, there is only the possibility \(A B C D H G F E A\):

![](https://cdn.mathpix.com/cropped/2024_06_06_b85a894aa8dbf722a7b3g-1376.jpg?height=231&width=286&top_left_y=2100&top_left_x=888)

1.1.2 Suppose, with the choice of \(A B C G\), \(H\) could follow \(G\). Then, to reach \(F\) via an unvisited point, only the continuation \(A B C G H E F\) would be possible, and the remaining point \(D\) could only be reached via an already visited point, since \(F\) and \(D\) are not endpoints of a common cube edge.

Due to this contradiction, only \(F\) can follow \(A B C G\), and the only possible continuation is: \(A B C G F E H D A\):

![](https://cdn.mathpix.com/cropped/2024_06_06_b85a894aa8dbf722a7b3g-1377.jpg?height=231&width=282&top_left_y=244&top_left_x=887)

1.2 After the continuation \(A B F\), only the possibilities \(A B F E\) and \(A B F G\) remain. 1.2.1 For \(A B F E\), only the continuation \(A B F E H G C D A\) exists, as in 1.1.1:

![](https://cdn.mathpix.com/cropped/2024_06_06_b85a894aa8dbf722a7b3g-1377.jpg?height=228&width=282&top_left_y=620&top_left_x=887)

1.2.2 For \(A B F G\), with analogous reasoning as in case 1.1.2, only the continuation \(A B F G C D H E A\) exists:

![](https://cdn.mathpix.com/cropped/2024_06_06_b85a894aa8dbf722a7b3g-1377.jpg?height=232&width=282&top_left_y=992&top_left_x=887)

2. If the path starts with \(A D\), it can only continue as \(A D C\) or \(A D H\).

2.1 After \(A D C\), only the continuations \(A D C B\) and \(A D C G\) remain. For each of them, only one continuation exists, as in 1.1.1 and 1.1.2. Since a path starting with \(A D C G\) is already listed in 1.2.1, only \(A D C B\) remains, i.e., \(A D C B F G H E A\):

![](https://cdn.mathpix.com/cropped/2024_06_06_b85a894aa8dbf722a7b3g-1377.jpg?height=229&width=282&top_left_y=1456&top_left_x=887)

2.2 After \(A D H\), only \(A D H E\) and \(A D H G\) remain, and for each of them, only one continuation exists. Since \(A D H E\) is already listed in 1.1.2, only \(A D H G C B F E A\) remains:

![](https://cdn.mathpix.com/cropped/2024_06_06_b85a894aa8dbf722a7b3g-1377.jpg?height=228&width=282&top_left_y=1828&top_left_x=887)

Thus, it has been shown that only the six listed paths satisfy the requirements of the problem. They indeed meet these requirements, as each contains each cube edge exactly once, starts and ends at \(A\), and runs only along the cube edges.

Furthermore, all the paths are distinct from each other, as the following table shows. In the table, for each pair of the mentioned paths, a cube edge is given that appears in one path but not in the other.

\begin{tabular}{c|ccccc} 
& 1.1 .2 & 1.2 .1 & 1.2 .2 & 2.1 & 2.2 \\
\hline 1.1 .1 & \(C D\) & \(B C\) & \(B C\) & \(A B\) & \(A B\) \\
1.1 .2 & & \(B C\) & \(B C\) & \(A B\) & \(A B\) \\
1.2 .1 & & & \(F E\) & \(A B\) & \(A B\) \\
1.2 .2 & & & & \(A B\) & \(A B\) \\
2.1 & & & & & \(D C\)
\end{tabular}

Solutions from the second round of 1976 taken from [5]

\subsection*{7.18.3 Third Round 1976, Class 10}