3-regular graph and two-way Euler circuit

Question

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!

Answer 1

Partial answer

Let me formalize. If you enter a roundabouts by road $i$ you leave it by road $(i \mod 3) +1$.

Let R.i be the road i of roundabout R.

$N=1$ is a solution of your problem.connect the two roundabout A and B as follow: for all i : A.i is connected to B.i.

We now show that for $N_1,N_2$ solution of your problem then $N_1+N_2+1$ is a solution as well.

Let $T_1,T_2$ be two towA_1s with respectively $2N_1,2N_2$ roundabout. Let $A_1,B_1$ be two roundabout connected in $T_1$ and $A_2,B_2$ connected in $T_2$. We construct a town $T_3$ as follow: we add two roundabout $C$ and $D$ and connect then as follow:

• $A_1$ with $C.1$
• $B_1$ with $C_2$
• $C_3$ with $D_3$
• $A_2$ with $D_1$
• $B_2$ with $D_2$

$T_3$ is a solution of your problem with $2N_1+2N_2+2=2(N_1+N_2+1)$ roundabouts.

Thus every odd $N$ is a solution.

@Alex Ravsky comments tells us that $N=2$ is not a solution. So may be Even numbers are impossible (i don't know yet). I'll try to think a a reduction with the same idea in order to prove this

Answer 2

$\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:

• erase the edge between $v_1$ and $v_2$
• erase the edge between $u_1$ and $u_2$
• connect $v_1$ and $w_1$
• connect $v_2$ and $w_2$
• connect $u_1$ and $w_1$
• connect $u_2$ and $w_2$
• connect $w_1$ and $w_2$

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.

Answer 3

wece and later Vlad provided a proof that such a tour can exist for every odd $N$. We show that there can be no such tour for even $N$.

Embed the graph in a two-dimensional surface. In order for the notion "clockwise" to be well-defined, the surface must be an orientable one. Now the number of vertices is $2N$ and the number of edges is $3N$. If a tour like the one you've described exists, then the embedding can be regarded as a map with a single face (that has $6N$ sides). But the generalization of Euler's formula, $$ V-E+F=2-2g, $$ must hold, where $g$ is the genus of the surface on which the graph is embedded. So we get $$ 2N-3N+1=2-2g. $$ This is a contradiction if $N$ is even.

Added: The desired embedding is achieved by drawing the graph on a sphere with handles, which is an orientable surface. To explain this a bit more, start by drawing the graph on the sphere. There will, in general, be some crossings of edges. The graph should be drawn in accordance with the specified clockwise ordering of edges at each vertex (roundabout). To enforce this ordering, even a planar graph may sometimes need to be drawn with edge crossings.

Remove or reroute edges (without violating edge-ordering constraints) until there are no more crossings. This can be done in such a way that the graph remains connected. Now add the removed edges back, one at a time: if an edge can be drawn within a single face, do so. (The face will be divided into two faces.) If it cannot, the insertion points of the edge lie in two different faces. Cut holes in each of these faces and join the holes with a tube. In this process the faces started as two surfaces each homeomorphic to a disk and ended as a single surface homeomorphic to a cylinder. Now route the edge across the cylinder, which cuts the cylinder so it is again homeomorphic to a disk.

Once all edges have been added back, we have the desired embedding of the graph in an orientable surface. This is a 2-cell embedding, meaning all faces are homeomorphic to disks, a property that is necessary in order to apply Euler's formula.

The ideas in this sketch come from the short article,

J. H. Lindsay, An Elementary Treatment of the Imbedding of a Graph in a Surface. The American Mathematical Monthly 66(2) (1959) 117-118.

and from Jack Edmond's masters thesis

Edmonds, John Robert (1960). A combinatorial representation for oriented polyhedral surfaces. University of Maryland.

A quotation from the latter:

Theorem 2. Given a connected linear graph with an arbitrrarily specified cyclic ordering of the edges to each vertex, there exists a topologically unique, two-sided polyhedron Whose edges and vertices are the given graph and whose clockwise edge orderings at each vertex (with respect to one of the sides) are as specified.

These ideas have a long history, going all the way back to Lothar Heffter in the 1890s. The notion of associating an embedding with a specification of the edge orderings at each vertex of a graph now goes by the name rotation system. If you want to try out the ideas, you can verify that there are essentially three different rotation systems for $K_4$, producing three different embeddings, one spherical (genus $0$) embedding with four triangular faces and two toroidal (genus $1$) embeddings, each with two faces—either a triangle and a nonagon or a quadrilateral and an octagon.