Prove that the edges of a finite simple planar graph (with no loops, multiple edges) may be oriented in such a way that at most three fourths of the total number of dges of any cycle share the same orientation. Moreover, show that this is the best global bound possible. Comment: The actual problem in the TST asked to prove that the edges can be $2$-colored so that the same conclusion holds. Under this circumstances, the problem is wrong and a counterexample was found in the contest by Marius Tiba.
Problem
Source: Romania TST 7 2009, Problem 2
Tags: combinatorics proposed, combinatorics
17.05.2012 22:32
Let $G$ is the given planar graph. Then we can colour vertices of G in $5$ colours so that equally coloured vertices are not connected. (Five colour theorem, a proof could be found in Diestel's Graph theory). The idea is to orient every edge $uv \in E(G)$, depending only on the colour of $u$ and $v$. Define an oriented graph $G_1$ in the following way. $V(G_1)=\{1,2,3,4,5\}$ and oriented edges of $G_1$ are $1\to 2, 1\to 3, 1\to 4, 2 \to 3, 2 \to 4, 4 \to 3, 1 \to 5, 5 \to 2, 5 \to 3, 5 \to 4$ Now if $uv \in G$ we orient $uv$ as $u \to v$ or $v \to u$ iff $c(u) \to c(v)$ or $c(v) \to c(u) $ in $G_1$. Here $c(u)$ denotes the colour of $u$. Notice that if $u_1u_2, u_2u_3, u_3u_4, u_4u_5$ is a path in $G_1$, where $u_1,u_2,\cdots,u_5$ are not necessary different, then at least two of edges are with different orientations, i.e. it is impossible that all four edges share the same orientation. This means that the same is true with respect to $G$, from which immediately follows the problem statement. The case when $G= K_4$ shows that the bound could not be improve. Comment. Of course it is easier to use that $G$ can be coloured in four colours (Four colour theorem), but as shown above an weaker colouring suffices. We can not use the same approach in case of the actual problem given- to $2$-colour the edges of $G$ with the same requirement.