Problem

Source: IRAN RMM TST 2019 p5

Tags: combinatorics, graph cycles, graph



Edges of a planar graph $G$ are colored either with blue or red. Prove that there is a vertex like $v$ such that when we go around $v$ through a complete cycle, edges with the endpoint at $v$ change their color at most two times. Clarifications for complete cycle: If all the edges with one endpoint at $v$ are $(v,u_1),(v,u_2),\ldots,(v,u_k)$ such that $u_1,u_2,\ldots,u_k$ are clockwise with respect to $v$ then in the sequence of $(v,u_1),(v,u_2),\ldots,(v,u_k),(v,u_1)$ there are at most two $j$ such that colours of $(v,u_j),(v,u_{j+1})$ ($j \mod k$) differ.