### Infinitely Long Walks on Two Colored Graphs

**Authors:**

Gemmell, Pete
**Technical Report Identifier:** CSD-92-719
**December 14, 1992**

CSD-92-719.pdf

CSD-92-719.ps

**Abstract:** Suppose we have a undirected graph *G* = (*V*,*E*) where *V* is the set of vertices and *E* is the set of edges. Suppose *E* consists of red colored edges and blue colored edges. Suppose we have an infinite sequence *S* of characters *R* and *B*.

We take a random walk starting at vertex *v* on *G* based on the sequence *S* as follows:

At the *i*th 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*.