A note on the last new vertex visited by a random walk

A “cover tour” of a connected graph G from a vertex x is a random walk that begins at x , moves at each step with equal probability to any neighbor of its current vertex, and ends when it has hit every vertex of G . The cycle C n is well known to have the curious property that a cover tour from any vertex is equally likely to end at any other vertex; the complete graph K n shares this property, trivially, by symmetry. Ronald L. Graham has asked whether there are any other graphs with this property; we show that there are not. © 1993 John Wiley & Sons, Inc.