3
$\begingroup$

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!

$\endgroup$
7
  • $\begingroup$ Is Vlad's.. erm.. my starting point arbitrary or can we choose it? $\endgroup$
    – user799688
    Dec 7, 2020 at 18:47
  • $\begingroup$ @Vlad I think this doesn’t matter, since your journey should be a closed tour. $\endgroup$ Dec 7, 2020 at 20:55
  • $\begingroup$ The starting point is fixed (Vlad's house), but anyway as @AlexRavsky said - this does not matter. $\endgroup$ Dec 7, 2020 at 21:14
  • 1
    $\begingroup$ Thanks! I have a better understanding $\endgroup$
    – user799688
    Dec 9, 2020 at 7:24
  • $\begingroup$ If a road returns to the same roundabout from which it started, then in one direction of travel Vlad travels that one road forever; in the other direction he will leave the roundabout via a different road. For all even $N$ it is possible to find configurations with journeys that travel every road in both directions except for one looping road, which is traveled in only one direction. If you start with an $N=2$ configuration that has such a journey, the argument in wece's and Vlad's answers should work for proving that such configurations exist for all even $N$. $\endgroup$ Dec 11, 2020 at 14:57

3 Answers 3

4
$\begingroup$

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

$\endgroup$
2
+50
$\begingroup$

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

a

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

enter image description here

we reach this configuration

enter image description here

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

enter image description here

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.

$\endgroup$
4
  • 2
    $\begingroup$ I guess this little condition should be that the journey includes every road, because such characteristics as edge coloring or invariants should be the same both for a required journey and for two disjoint journeys on two cubic graphs with $2N_1$ and $2N_2$ vertices, respectively and both $N_1$ and $N_2$ odd. $\endgroup$ Dec 9, 2020 at 14:49
  • 1
    $\begingroup$ I thought of that too and indeed, when i tested models out almost every time the car would not travel on every road. The orientation of the roads didn't seem to cause as much of a problem as the requirement to travel on all roads. $\endgroup$
    – user799688
    Dec 9, 2020 at 15:28
  • 2
    $\begingroup$ For what it's worth, even $N$ seems never to work. I've generated hundreds of random examples for every $N$ up to $N=33$ and invariably a handful of those couple hundred will work when $N$ is odd, but never when $N$ is even. $\endgroup$ Dec 9, 2020 at 16:47
  • $\begingroup$ That's great news. Unfortunately, all the testing I did was manual (It took me about 2 hours...) because I do not know how to make such adcanced programs. I am pretty sure that even $N$ must not work. $\endgroup$
    – user799688
    Dec 9, 2020 at 18:13
2
$\begingroup$

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.

$\endgroup$
13
  • 1
    $\begingroup$ I was envisaging starting with the graph drawn on a sphere, with a specified clockwise ordering of edges at each roundabout (vertex), and then adding handles as needed to get rid of crossings. But now I'm thinking this kind of embedding isn't strong enough: to use Euler's formula, I think I need a 2-cell embedding, which requires that each face be homeomorphic to a disk. I am fairly certain that a 2-cell embedding always exists, but I don't see a simple proof of that at the moment. $\endgroup$ Dec 14, 2020 at 0:13
  • 1
    $\begingroup$ I ran across this answer of yours, and the paper of Youngs seems like it might have what is needed, particularly Section 3 on the capping operation. I have not fully understood that section yet. Henning Makholm's answer at the same post gives a two-handle solution that produces a 2-cell embedding for the utilities problem with one face; the one-handle solution in your answer also gives a 2-cell embedding, this time with three faces. This is all consistent with Euler's formula. Although the underlying graph is the same for both solutions... $\endgroup$ Dec 14, 2020 at 16:14
  • 1
    $\begingroup$ @AlexRavsky Whatever misgivings I had about the embedding were, I think, based on misapprehensions. I've added a description of the embedding to my post. Let me know if you see anything amiss. I'm certainly no topologist, of any kind. $\endgroup$ Dec 15, 2020 at 15:54
  • 1
    $\begingroup$ OK, but why given the constructed 2-cell embedding (for instance, provided by Theorem 2) into a surface with possible holes, “If a tour like the one you've described exists, then the embedding can be regarded as a map with a single face”? $\endgroup$ Dec 16, 2020 at 7:43
  • 1
    $\begingroup$ @AlexRavsky Just in case I've been unclear, I mean "map" in the sense of map of the countries of the world, not "map" in the sense of mapping between two sets. If I walk along the boundary of a country (face) in my map, always keeping the boundary to my right, then I will eventually return to my starting point without ever crossing any boundary. There will be one such walk in each face in the map and, when the union of all such walks is considered, each edge will have been walked along twice, once on each side in opposite directions. For the tour described, with a left turn made at each... $\endgroup$ Dec 16, 2020 at 8:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.