Description
We take a random walk starting at vertex v on G based on the sequence S as follows:
At the ith step, if S has an R at position i the walk traverses a random red edge out of the current vertex (chosen uniformly from the outgoing edges). If S has a B the walk traverses a random blue edge out of the current vertex.
We say S covers G starting at vertex v when a random walk using S starting at v covers every vertex of G.
Theorem 1 If G is a red-blue colored undirected graph which is connected in red and connected in blue and there exists an RB-sequence S such that starting at some vertex v, Pr[S covers G] < 1, then G contains a proper subgraph H such that H's vertices can be divided into two sets: U and W where there are no red edges between U and V - W and no blue edges between U and V - U.