Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
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.
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?
Required, but never shown