A town-planner has built an isolated city whose road network consists of $2N$ roundabouts, each connecting exactly three roads. A series of tunnels and bridges ensure that all roads in the town meet only at roundabouts. All roads are two-way, and each roundabout is oriented clockwise. Vlad has recently passed his driving test, and is nervous about roundabouts. He starts driving from his house, and always takes the first edit at each roundabout he encounters. It turns out his journey incluldes every road in the town in both directions before he arrives back at the starting point in the starting direction. For what values of $N$ is this possible?
I have tried to turn this into an equivalent graph theory problem in which we can apply some results on Euler circuits or similar, but with no such rephrasals seem useful. Any help appreciated!
$\text{Partial answer}$
Let the vertices of our graph (the roundabouts) be $v_1,v_2,...,v_{2N}$. We will prove that every odd $N$ works and discuss about even $N$.
$\text{For odd }N$
Of course, cases $N=3$ and $N=5$ work ($N$ must be $\geq 2$ for the graph to make sense, so we cannot discuss about $N=1$). Here are $2$ configurations which show that $N=3$ and $N=5$ work:
We will now show that if $N_1$ and $N_2$ work, then $N_1+N_2+1$ works. Suppose we have $2$ graphs $G_1$ and $G_2$, one with $2N_1$ vertices and the other with $2N_2$ vertices, which both work. Select $2$ vertices which are connected from $G_1$, $v_1$ and $v_2$ and $2$ vertices that are connected from $G_2$, $u_1$ and $u_2$. Add $2$ more vertices, $w_1$ and $w_2$.
If we prove we can connect some vertices such that the new graph works (which has $2\cdot(N_1+N_2+1)$), we proved that if $N_1$ and $N_2$ are valid numbers, then so is $N_1+N_2+1$.
We will do the folowing operations:
So from this initial configuration
we reach this configuration
I will not actually explain step by step why it works, but a simple analysis of the trip the car will make with these new little changes will, indeed, confirm that this new graph works.
Thus, $N_1$, $N_2$ work implies that $N_1+N_2+1$ works. We have shown $3$ and $5$ work, so every odd $N$ works. $\text{ }\blacksquare$
$\text{For even }N$
To my dissapointment, I have failed to come up with either a contradiction or a proof for one of the small cases. Note that is $2k$ is a solution, then any even number greater $\geq 2k+4$ is clearly a solution (using the above result, $N_1$ and $N_2$ work $\Rightarrow$ $N_1+N_2+1$ works).
$N=2$ clearly does not work and, well, for $N=4$ I spent about one hour testing configurations and didn't manage to find one that works. I do not think there is a way to prove such a graph exists without at least one example, which is nowhere to be found when $N$ is even, so I tried to prove that even $N$ does not work.
I tried several approaches such as edge colorings, invariants and some other tricks, but again I did not manage to get a contradiction. I just want to point out that it is impossible to control configurations while trying to disprove that even $N$. It is hard, just because you have to talk purely theoretically and you cannpt rely on any configuration. Take a look at this:
Suppose you are coming from the blue edge towards $v$. In the first case, you would leave on the green edge, $vv_1$4, but in the second case you would leave on the red edge $vv_2$:
That is why the positionning of the points is crucial, so disproving that even $N$ works is pretty hard, as we cannot make configuration-related observations.
To be honest, I am not even sure if even $N$ should or should not work. On one hand, out of the (ver very) many possible configurations, one might work, but on the pther hand, there might be a little condition which prevents it from working. I hope this "disection" of the problem helped in any way.