If G = (V, E) is a connected, undirected, non-bipartite with n vertices and
m edges we can define a Markov chain, M_{G}, on G by defining
the transition probability from vertex u to vertex v to be
P_{uv} = 1/d(u) when (u,v) is an edge of G and 0 otherwise.
(A graph is bipartite if its vertices can be partitioned into two non-empty
sets so that no edge connects vertices within the same set.)

- Hitting time
- h
_{uv} = expected time for a random walk starting
at u to first reach v

- Commute time
- C
_{uv} = h_{uv} + h_{vu}

- Cover time
- If C
_{u}(G) is the expected amount of time for a random
walk starting at u to visit every vertex of G, the cover time is the
maximum of this over all starting vertices

### Reference:

Randomized Algorithms, by Rajeev Motwani and Prabhakar Raghavan,
Cambridge University Press, 1995