MathLabs

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 LL parallel to one of the coordinate axes, the absolute difference between the numbers of white and red points on LL is at most 11?
Step 1 of 4: Build a bipartite graph
Previous stepNext step
In plain words

A point is naturally an edge: its row and column are the two endpoints. Balancing colors on axis-parallel lines becomes balancing edge colors at graph vertices.

V=H⊔W,p=(h,w)↔hwV=H\sqcup W,\qquad p=(h,w)\leftrightarrow hw
A K3,3 illustration of the row-column bipartition; vertex colors mark the two parts.
A complete bipartite graph with three row-side vertices and three column-side vertices.
Detailed analysis

Make one vertex for every horizontal line containing a point and one for every vertical line containing a point. A point (h,w)(h,w) becomes an edge joining row vertex hh to column vertex ww. The graph is bipartite; coloring the edge red or white colors the point, and each line condition is exactly a vertex condition.