Always turning left necessarily takes you back to your starting position?

141 Views Asked by At

In a very general street network of two-way roads, if at every intersection you always turn in the same direction, say, leftmost, is it guaranteed that you return to your starting point?

The street network generically corresponds to a finite spatial 2D undirected non-planar graph (due to bridges and tunnels) with nodes at the intersections. I'd guess that this is trivially true for planar graphs (and probably linked to the Right-hand rule or the Wall follower method for maze solving). I've failed so far to find any counter-example, i.e., any graph where I wouldn't go back to the starting position. As going more than once through the same edge or node is allowed, dead ends aren't a problem.

1

There are 1 best solutions below

7
On BEST ANSWER

Yes. Your position is described by a pair $(v,w)$ of intersections, meaning you are on a road connecting $v$ to $w$ and heading towards $w$. Every position $(v,w)$ is preceded by a unique position $(u,v)$, given by heading along the road from $w$ to $v$ and making the nearest right turn. Let's call your sequence of positions $$(x_0,x_1),(x_1,x_2),\dots,(x_n,x_{n+1}),\dots$$ Since there are finitely many positions, this infinite list must have a repeat. Let $i<j$ be the indices of the earliest such repeat, $(x_i,x_{i+1})=(x_j,x_{j+1})$. I claim this means $i=0$, so that $(x_j,x_{j+1})$ is a return to your starting point. If not, then the repeated positions would be preceded by the same position $(x_{i-1},x_i)=(x_{j-i},x_j)$, contradicting the fact that $i,j$ was the earliest such repeat.