Problem 6
Given a finite set of points in the plane, each with integer coordinates, is it always possible to color the points red or white so that for every line parallel to one of the coordinate axes, the absolute difference between the numbers of white and red points on is at most ?
Step 2 of 4: Handle the all-even component
In plain words
An even-degree connected component has an Euler circuit, whose consecutive edges can be colored alternately.
Detailed analysis
In a connected component where every vertex has even degree, take an Euler circuit. Because the graph is bipartite, the circuit has even length. Color its edges alternately red and white. At every vertex, incident edges occur in consecutive entering/leaving pairs, one of each color, so the difference is .