### Peter S. Gemmell

###
EECS Department

University of California, Berkeley

Technical Report No. UCB/CSD-92-719

December 1992

### http://www2.eecs.berkeley.edu/Pubs/TechRpts/1992/CSD-92-719.pdf

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*.

BibTeX citation:

@techreport{Gemmell:CSD-92-719, Author = {Gemmell, Peter S.}, Title = {Infinitely Long Walks on Two Colored Graphs}, Institution = {EECS Department, University of California, Berkeley}, Year = {1992}, Month = {Dec}, URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1992/6015.html}, Number = {UCB/CSD-92-719}, Abstract = {Suppose we have a undirected graph <i>G</i> = (<i>V</i>,<i>E</i>) where <i>V</i> is the set of vertices and <i>E</i> is the set of edges. Suppose <i>E</i> consists of red colored edges and blue colored edges. Suppose we have an infinite sequence <i>S</i> of characters <i>R</i> and <i>B</i>. <p>We take a random walk starting at vertex <i>v</i> on <i>G</i> based on the sequence <i>S</i> as follows: <p>At the <i>i</i>th step, if <i>S</i> has an <i>R</i> at position <i>i</i> the walk traverses a random red edge out of the current vertex (chosen uniformly from the outgoing edges). If <i>S</i> has a <i>B</i> the walk traverses a random blue edge out of the current vertex. <p>We say <i>S</i> covers <i>G</i> starting at vertex <i>v</i> when a random walk using <i>S</i> starting at <i>v</i> covers every vertex of <i>G</i>. <p><strong>Theorem 1</strong> If <i>G</i> is a red-blue colored undirected graph which is connected in red and connected in blue and there exists an <i>RB</i>-sequence <i>S</i> such that starting at some vertex <i>v</i>, <i>Pr</i>[<i>S</i> covers <i>G</i>] < 1, then <i>G</i> contains a proper subgraph <i>H</i> such that <i>H</i>'s vertices can be divided into two sets: <i>U</i> and <i>W</i> where there are no red edges between <i>U</i> and <i>V</i> - <i>W</i> and no blue edges between <i>U</i> and <i>V</i> - <i>U</i>.} }

EndNote citation:

%0 Report %A Gemmell, Peter S. %T Infinitely Long Walks on Two Colored Graphs %I EECS Department, University of California, Berkeley %D 1992 %@ UCB/CSD-92-719 %U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1992/6015.html %F Gemmell:CSD-92-719