Let G=(V,E) be a simple graph.
Prove that there exists a 2-coloring f of G with the following property: For each vertex v∈V, at most 21degv among the neighbors of v have the same color as v.
[Remark: This problem is often restated as follows: You are given a (finite) set of politicians; some politicians are mutual enemies. (No politician is his own enemy. If u is an enemy of v, then v is an enemy of u. An enemy of an enemy is not necessarily a friend. So this is just a simple graph.) Prove that it is possible to subdivide this set into two (disjoint) parties such that no politician has more than half of his enemies in his own party.]
[Hint: First, pick an arbitrary 2-coloring f of G. Then, gradually improve it until it satisfies the required property.]