# 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 'SO- stop being evil' Jan 14 '15 at 19:13
• @Gilles Why don't you add your own answer, then? – Yuval Filmus Jan 14 '15 at 20:01