Published by the Department of Computer Science, The University of Chicago.
The cover time of a graph is the time it takes for a random walk on it
to visit all
vertices. This note shows that for any tree on n vertices,
the probability that the cover time of the tree is linear in n is
exponentially small in n. This is true for any starting vertex.
Submitted November 26, 2010, revised June 20, 2012, 2, published July 1, 2012.