Solving a puzzle: Graph where each node has degree 3 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:

*

*The paths form a finite connected graph in which each crossing (that is, each crossing of paths) is of degree 3.

*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.

*Strict rule against leaving markings in the park. It is not ok to mark crossings or path in any way.

*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?
 A: 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:

*

*Assume hypothesis $H_i$ is true for the time being.

*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.

*From that location, find directions in $H_i$'s graph that would take you to $H_i$'s restaurant location $r$.

*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.
