Suppose a land with a finite number of castles. Each castle is connected (via roads) with exactly 3 other castles.
One knight leaves from his castle and starts travelling. He moves in the following way. 1) When he begins from his home castle (first step) he randomly chooses a road to take. 2)For the second step he randomly chooses the left or right road, but can't go back. 3)Every other step is deterministic. If he came to this castle by taking the left road next he takes the right and vice versa and can never just go back.
Prove that he will eventually return to his original castle.