Problem 1155

We distinguish based on the parity of $n$ and consider $G$ the graph whose vertices are the roundabouts (all of degree 3) and the edges are the roads. Already, for the statement to make sense, we need $n \geqslant 2$.

For $n$ odd: First, we note that $n=3$ and $n=5$ work (draw a picture). Next, we will show that if $n_{1}$ and $n_{2}$ are solutions, then $n_{1}+n_{2}+1$ is also a solution. Let $G_{1}, G_{2}$ be two graphs with $2 n_{1}$ and $2 n_{2}$ vertices that satisfy the statement. Let $u_{1}, v_{1}$ be two connected vertices in $G_{1}$ and $u_{2}, v_{2}$ be two connected vertices in $G_{2}$. Add two additional vertices $u_{3}$ and $v_{3}$. We proceed as follows:

1. Erase the edges $u_{1}-v_{1}$ and $u_{2}-v_{2}$.
2. Connect $u_{1}$ and $u_{2}$ to $u_{3}$.
3. Connect $v_{1}$ and $v_{2}$ to $v_{3}$.
4. Connect $u_{3}$ to $v_{3}$.

We can verify that the graph $G$ obtained satisfies the conditions on the degree of the vertices, and that the paths traveled by Headless Horseman in each of the graphs can be joined to form a path that works. Thus, every $n \geqslant 3$ odd works.

For $n$ even: Let's show that there is no solution in this case. The graph is not necessarily planar, but it can be drawn on a surface of genus $g$. According to Euler's formula,

$$S-A+F=2-2 g$$

With $S=2 n$ the number of vertices, $A=3 n$ the number of edges, and $F=1$ the number of faces. $F$ must therefore be even, but the existence of a path such as the one traveled by Headless Horseman means that the graph can be drawn with a single face.