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 3 of 4: Decompose the component with odd vertices

Previous step Next step

In plain words

A connected graph with $2k$ odd-degree vertices can be partitioned into $k$ trails; bipartiteness makes each trail alternate between its two sides.

2k\text{ odd-degree vertices}\Longrightarrow k\text{ edge-disjoint paths}

Detailed analysis

If the component has $2k>0$ odd-degree vertices, the standard path-decomposition theorem partitions its edges into $k$ edge-disjoint paths (or trails). Color the edges of each path alternately red and white. Every internal vertex of a path receives one edge of each color from that path; an endpoint receives one unmatched edge. Summing over paths, each vertex has color discrepancy at most $1$ .