Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.