# A bicolored plane graph contains a vertex with low oscillation

$G$ is a planar graph, and all edges of $G$ are colored white or black. Prove that in any drawing of $G$ there exists a vertex $v$ such that going around the edges incident with $v$ in the clockwise direction, we encounter no more than two changes of color.

I think if I suppose this is not true, then I can find contradiction - there is a subgraph of $G$ which is isomorphic with $K_{3,3}$ - but it's just a idea. I really don't know how to solve.

-

It seems the following.

Assume the converse. Suppose that there exists a plane graph $G$ (that is, a planar graph with its fixed plane drawing) and a coloring of all edges of $G$ into two colors (white and black) such that for each vertex $v$ of the graph $G$ going around the edges incident with $v$ in the clockwise direction, we encounter more than two changes of color. If necessary, adding to $G$ edges, without loss of generality we may assume that $G$ is a maximal planar graph, that is a triangulation.

For each vertex $v$ of the graph $G$ let $w(v)$ be the number of changes of color which we count going around the edges incident with $v$ in the clockwise direction. Similarly, for each face (which is a triangle) of the graph $G$ let $w(f)$ be the number of vertices of $v$ which have their edges if $f$ of different color, that is $w(f)=0$ if all edes of $f$ have the same color and $w(f)=2$ otherwise. By construction we have

$$\sum \{w(v):v\mbox{ is a vertex of }G\}=\sum \{w(f):f\mbox{ is a face of }G\}.$$

Let $V$, $E$, and $F$ denote the number of vertices, edges, and faces of the graph $G$ respectively. We write Euler formula:

$$V-E+F=2.$$

Since $G$ is a triangulation,

$$3F=2E.$$

So $F=2V-4$ and $\sum \{w(f):f\mbox{ is a face of }G\}\le 4V-8.$ Therefore there exists a vertex $v$ of the graph such $w(v)<4$. Since $w(v)$ is even, we have $w(v)=2$.

-