A traveling time problem

Question

Given any undirected, connected and simple graph $G(V,E)$,each node of which is considered as a city. We call $j$ a neighbor of $i$ if $(i,j)\in E$. $N_i$ is the set of neighbors of $i$. $|V|=N$

There is a traveler who starts travelling from some city and wants to visit all cities in $G$. But he does not have a map,it means he only knows about the local information,i.e. he only knows the neighbors of a city when staying at that city. Each time, he moves to a neighbor of currently staying city. He can visit one city over once.

Suppose he traveled from city a to b 3 times and b to a 2 times, then we call link (a,b) (or (b,a)) has been used totally 5 times. All these past visiting records are remembered by the relevant city, i.e., each city knows how many times their links have been used till now. For example, both a and b know link(a,b) has been used 5 times. We want to design an algorithm which only depends on these known information such that he can visit all cities in finite times.

I am considering the following algorithm: each time, suppose he stays in some city $i$, and he selects a neighbor city of $i$ whose link between $i$ has been used the least times in the past, except the city he visited at last time, and move to that city. If more than 1, any of them is OK.

I want to know for any graph $G$, after how many times, he will finish visiting all the cities. Whether there exists a function $f$ such that after $f(N)$ times, all the cities will be visited for sure.

Answer 1

Lemma 1: Suppose a city has $d$ incident links, the least-used one(s) having been used $m$ times. Then the city has been visited at most $d(m+1)$ times.

Proof: Every visit to a city increases the use of one of the least-used links incident to the city. Thus, over $d$ visits to the city, the minimum must increase. $\Box$

Lemma 1 bounds the uses of any link in terms of the minimum uses of incident links. Since the graph is connected, this guarantees that every link will be used eventually (and thus every city will be visited).

Lemma 2: Terminate travel as soon as every city is visited at least once. A city of distance $k$ from the final city has been visited at most $N^k$ times.

Proof: The final city is visited exactly $N^0 = 1$ time. Induction: A city at distance $k >0$ has a neighbor that was visited at most $N^{k-1}$ times, so the link between has been used at most $N^{k-1}$ times. Since the number of incident vertices to any city is at most $N-1$, the number of visits to the distance-$k$ city is at most $(N-1)(N^{k-1}+1) < N^k$ by Lemma 1. $\Box$

Since every city is at distance at most $N-1$ from the last city, each of the $N$ cities is visited at most $N^{N-1}$ times. Thus $f(N) = N^N$ suffices.

The minimal function should be much better, but you asked for existence.

Answer 2

You seem to be describing a maze-searching problem. See here, especially Trémaux's algorithm.