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

L

parallel to one of the coordinate axes, the absolute difference between the numbers of white and red points on

L

is at most

1

Step 4 of 4: Return to the point set

Previous step Next step

In plain words

The graph argument is local to each connected component, and the required line condition is exactly the vertex discrepancy bound.

|\#\text{white}(L)-\#\text{red}(L)|\le1

Detailed analysis

Color each connected component independently. Translating edge colors back to point colors gives, for every horizontal or vertical line $L$ , $|\#\text{white}(L)-\#\text{red}(L)|\le1$ . Thus the answer is yes.