Summary: Consider the following stochastic process on a graph: initially all vertices are uncovered and at each step cover the two vertices of a random edge. What is the expected number of steps required to cover all vertices of the graph? In this note we show that the mean cover time for a regular graph of $N$ vertices is asymptotically $(N \log N)/2$. Moreover, we compute the exact mean cover time for some regular graphs via generating functions.

60C05

coupon collector's problem, graph, edge cover