If edges of $G$ are two colored, then there is a vertex of $G$ with at most two col0or changes in the cyclic order of the edges around the vertex.

Question

Hello there i am reading proofs from the book of Gunter M ziegler. The chapter is called Three applications of eulers formula. Know there is a proposition which i don't fully understand and help would be much appreciated.

proposition: Let G be a simple plane graph with n>2 vertices then:

If edges of $G$ are two colored, then there is a vertex of $G$ with at most two col0or changes in the cyclic order of the edges around the vertex.

I don't exactly understand what one means with this proposition. Especially the last part "Then there is a vertex of $G$ with at most two color changes in the cyclic order of the edges around the vertex." I tried writing this out by for example drawing pictures but i don't seem to get what it means.

Kees Til

Answer 1

The graph is planar, so imagine it's embedded in the plane. Stand at some vertex in the plane. There are, say, seven edges emanating from you (like spokes radiating from the hub of a bicycle wheel), and they can be ordered, say, clockwise (but the order "wraps around" when you get back to the beginning). So their colors, in order, might look like

1 2 3 4 5 6 7
R G R R R G G

Here there are four color changes, from R to G between 1 and 2, and back to R between 2 and 3, from R to G bewteen 5 and 6, and from G to R between 7 and 1.

The claim your author's making (which I don't know how to prove, offhand) is that there's a vert whose edges in order look like

R R G G R

for instance, where there are only two color changes.