On the optimality of a simple strategy for searching graphs

Consider a search Same with an immobile hider in a graph. A Chinese postman tour is a closed trajectory which visits all the points of the graph and h as minimal length. We show that encircling the Chinese postman tour in a ra ndom direction is an optimal search strategy if and only if the graph is we akly Eulerian (i.e it consists of several Eulerian curves connected in a tr eelike structure).