# Proving that the cover time for graph is exponential in the worst case

How can I prove that the cover time for a directed graph $G$ can be exponential in the size of $G$?

The cover time is the expected length of a random walk that visits all vertices.

-
What is the "cover time"? –  Raphael Jun 22 '12 at 14:57
I think cover time means the expected number of steps taken by a random walk to visit every vertex. –  Juho Jun 22 '12 at 21:19
You also have to assume that the graph is strongly connected. –  Yuval Filmus Jan 27 '13 at 6:38

## 1 Answer

You do it in two steps:

1. First you think of a graph which you can expect to be difficult.

2. Then you prove your suspicion.

Let's start with the first step - do you have any graph in mind?

-
To a novice, it might not be at all obvious that when you say “think of a graph”, you really mean “for all $n$ [or at least an infinite number of integers $n$], think of a graph of size $n$” and “prove your suspicion” involves computing the cover size in terms of $n$ and finding an expression that is exponential in $n$. A hint that isn't even didactic is really not useful. –  Gilles Jan 14 at 19:13
@Gilles Why don't you add your own answer, then? –  Yuval Filmus Jan 14 at 20:01