Proving that the cover time for graph is exponential in the worst case
You do it in two steps:


First you think of a graph which you can expect to be difficult.
Then you prove your suspicion.


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