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.
Problem
Source: IRAN RMM TST 2019 p5
Tags: combinatorics, graph cycles, graph
11.03.2020 23:25
parmenides51 wrote: 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. Where can we find other IRAN RMM TST 2019
11.03.2020 23:29
all the contest problems have been posted in aops, look here
13.03.2020 15:39
What does complete cycle means? For instance, there exists a planar graph without any cycle.
14.03.2020 18:26
bumjoooon wrote: What does complete cycle means? For instance, there exists a planar graph without any cycle. It means that 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.
19.03.2020 15:35
Assume that there are no complete cycles that change color at most twice. Addding arbitrary edges to the graph only weakens the possibility of finding a complete cycle, so we can assume that all of the edges consisting the graph is part of a face, and that the faces are all triangles. (If not, add an arbitrary edge to satisfy the assumptions) Now call a set $\{A,B,C\}$ "cherry" if $AB,BC,CA$ are all edges of the graph and $AB, BC$ has a different color. Let the number of faces in this graph be $f$, vertices be $v$, and edges be $e$. We double count the number of cherries. Counting on each vertice $B$, since there are no complete cycles that changes color at most twice, the number of cherries are at least $4v$. Counting of triangle faces $ABC$, the number of cherries are at most $2f$. So we get $4v \leq 2f$ On the other hand, by Euler's theorem $v-e+f=1$ and that $3f \leq 2e$, we obtain $f \leq 2v-2$ which is a contradiction with the inequality above.
05.04.2020 15:38
Above solution is similar to my solution. First, I tried number of vertex induction and nuber of edge induction. But, 20 minutes later, I know prove this problem only all face is triangle. And done. One triangle has at most two changing color.
11.08.2020 13:32
@Contradiction, by Euler's theorem $v-e+f=2!!!$. You assume that the faces are all triangles (you can do it only for $n \geq 3$) $\implies 3f = 2e \implies 2f = 4v-8$. I say that vertex $v$ is $good$ if $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, and overwise say that vertex $v$ is $bad$. Let the number of $bad$ vertices be $k$, number of "cherry" be $c$. We have $4k \leq 2c \leq 2f = 4v-8 \implies k \leq v-2$. $\implies$ there are at least two $good$ vertices(if $n \geq 3$).