  A mobile agent navigating along edges of a simple connected graph, either
finite or countably infinite, has to find an inert target (treasure) hidden in
one of the nodes. This task is known as treasure hunt. The agent has no a
priori knowledge of the graph, of the location of the treasure or of the
initial distance to it. The cost of a treasure hunt algorithm is the worst-case
number of edge traversals performed by the agent until finding the treasure.
Awerbuch, Betke, Rivest and Singh [3] considered graph exploration and treasure
hunt for finite graphs in a restricted model where the agent has a fuel tank
that can be replenished only at the starting node $s$. The size of the tank is
$B=2(1+\alpha)r$, for some positive real constant $\alpha$, where $r$, called
the radius of the graph, is the maximum distance from $s$ to any other node.
The tank of size $B$ allows the agent to make at most $\lfloor B\rfloor$ edge
traversals between two consecutive visits at node $s$.
  Let $e(d)$ be the number of edges whose at least one extremity is at distance
less than $d$ from $s$. Awerbuch, Betke, Rivest and Singh [3] conjectured that
it is impossible to find a treasure hidden in a node at distance at most $d$ at
cost nearly linear in $e(d)$. We first design a deterministic treasure hunt
algorithm working in the model without any restrictions on the moves of the
agent at cost $\mathcal{O}(e(d) \log d)$, and then show how to modify this
algorithm to work in the model from [3] with the same complexity. Thus we
refute the above twenty-year-old conjecture. We observe that no treasure hunt
algorithm can beat cost $\Theta(e(d))$ for all graphs and thus our algorithms
are also almost optimal.
