Proving a 2009 conjecture of Itai Benjamini, we show: For
any C, there is a greater than 0 such that for any simple random
walk on an n-vertex graph G, the probability that the first Cn
steps of the walk hit every vertex of G is at most
exp[-an]. ...