Orientability of planar graph
Source: Romania TST 7 2009, Problem 2
May 5, 2012
combinatorics proposedcombinatorics
Problem Statement
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 -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.