CIIM 2017 Problem 6

Let $G$ be a simple, connected and finite grafo. A hunter and an invisible rabbit play in the graph $G$ . The rabbit is initially in a vertex $w_0$ . In the $k$ -th turn (for $k \geq 0$ ) the hunter picks freely a vertex $v_k$ . If $v_k = w_k$ , the rabbit is capture and the game ends. If not, the rabbit moves invisibly by an edge of $w_k$ to $w_{k+1}$ ( $w_k$ and $w_{k+1}$ are adjacent and therefore distinct) and the game continues. The hunter knows these rules and the graph $G$ . After the $k-$ th turn he knows that $w_k \not = v_k$ , but he gets no more information. Characterize the graphs $G$ such that the hunter has an strategy that guaranties that he can capture the rabbit in at most $N$ turns for some positive integer $N$ . Here $N$ must depend only on $G$ and the strategy should work independently of the initial position and trajectory of the rabbit.