Solving a puzzle: Graph where each node has degree 3

Question

I am trying to solve this puzzle:

Problem: The Park is covered by a network of hiking paths.

Goal: Find an algrithm by which you'll find (in finite time) the crossing at which the restaurant is located.

Rules:

1. The paths form a finite connected graph in which each crossing (that is, each crossing of paths) is of degree 3.
2. The crossings are indistinguishable one from another: it is not possible to know which crossing one has arrived at, to identify the paths meeting there, or to recognize whether one has been there before.
3. Strict rule against leaving markings in the park. It is not ok to mark crossings or path in any way.
4. If you enter a crossing by one path you must leave it by a different path. You have initially arrived at some node by one of its incident paths.

My questions:

For rule 1: I cannot find any graph where every node has a degree of 3. At least one node has degree 2.

2nd question: If I cannot mark the paths where I have been, what can I do to find a sufficient solution? Just go right, right right and one time left?

Answer 1

Define a hypothesis to consist of the following:

• a $3$-regular graph representing a hypothetical map of the park;
• a vertex $r$ in that graph representing a hypothetical location of the restaurant;
• a vertex $s$ in that graph representing a hypothetical starting location;
• an edge incident to $s$ representing the hypothetical path by which you arrived at $s$.

There are infinitely many hypotheses, but countably many: for each natural number $n$, there are only finitely many hypotheses in which the park has $n$ vertices. So we may number the hypotheses $H_1, H_2, H_3, \dots$.

One of the hypotheses represents the true map of the park, location of the restaurant, and your starting position: call that hypothesis $H_N$. You don't know which hypothesis this is, but $N$ is some finite number.

---

Now, here is the strategy that will get you to the restaurant. For each $i=1,2,3,\dots$, you:

1. Assume hypothesis $H_i$ is true for the time being.
2. Given the steps you've taken so far, determine the location in $H_i$'s graph where you would now be, if hypothesis $H_i$ were true.
3. From that location, find directions in $H_i$'s graph that would take you to $H_i$'s restaurant location $r$.
4. Follow those directions in the actual physical park.

For the first $N-1$ iterations of this procedure (for $i=1, 2, \dots, N-1$), you're going to be following directions based on a false premise, and they're unlikely to get you to the restaurant except by chance.

On the $N^{\text{th}}$ iteration of the restaurant, you'll assume a true hypothesis: the graph you take will be the correct graph, with the restaurant and your starting location and starting direction marked correctly. Then the location you work out in step 2 will happen to be your actual location in the park, and the directions you work out in step 3 will actually take you to the restaurant.