= Solution
\b[<Depth-first tree search> is complete under the stated initial <reachability> assumption, but is not bonus-optimal.]
Let $d_t$ be the <graph distance> between fox and rabbit after round $t$, with $d_0$ their initial <graph distance>. Initial <reachability> makes $d_0$ finite, and ordinary moves preserve membership in their common <connected component of a graph>. After the rabbit's next move, the <triangle inequality> gives intermediate separation at most $d_t+1$. If that separation is at most two, the fox catches the rabbit that round. Otherwise the fox takes two steps along a <shortest path>, leaving
$$
1\le d_{t+1}\le d_t-1.
$$
Thus a successful surviving history has at most $d_0-1$ rounds; if it does not escape by then, the next round captures it. The <shortest-path pursuit distance bound> excludes infinite live branches, even when the rabbit stays. Together with the finite <branching factor>, it makes the whole relevant <search tree> finite, so <depth-first tree search> eventually finds an escape whenever one exists.
For nonoptimality, take the corridor of part (g) and let <depth-first tree search> try left first. It immediately returns the one-round escape with bonus $1$, whereas trying right twice earns $2$. The decreasing separation proves termination, \b[not optimality of the first returned escape].
Back to article page
