Colouring $2n$ Points in $\mathbb{R}^2 $ Definition: A strip is the area in the plane enclosed between some two parallel lines. An axis-
parallel strip is a strip whose bounding lines are parallel to one of the axes.
Let $P$
be a set of $2n$ points in the plane (for some integer $n$). Prove that the points of $P$
can be colored with 'red' or `blue' such that in any axis-parallel strip the difference
between the number of red points and the number of blue points is at most 2.
The direction I was thinking about is definig monotone non-decreasing seq of the points, relatively to the $x$-axis, and another non-decreasing monotone sequence relatively to y-axis, from the given points. Then I would like taking a graph, such that the vertices are the points and the edges connect consecutive terms of both sequences. Im pretty stuck right now.
 A: Note: here is the hint that I used as a starting point.
We define two nondecreasing orderings of $P$ with $\leq_x$ and $\leq_y$ the component-wise comparisons. We write $P = \{p_1,\ldots,p_{2n}\} = \{\hat{p}_1,\ldots,\hat{p}_{2n}\}$ where $p_i \leq_x p_{i+1}$ and $\hat{p}_i \leq_y \hat{p}_{i+1}$.
Next, we define a graph on $P$ with the edge-set $E = \big\{\{p_{2k-1},p_{2k}\}\big\}_{k=1}^n \cup \big\{\{\hat{p}_{2k-1},\hat{p}_{2k}\}\big\}_{k=1}^n.$ Note that any vertex is a part of exactly 1 or 2 edges. If the vertex is part of 2 edges $e_1, e_2$ and $e_1$ is of the form $\{p_{2k-1},p_{2k}\}$, then $e_2$ is of the form $\{\hat{p}_{2k-1},\hat{p}_{2k}\}$.
We show that any connected component of $P$ has an even number of vertices. Suppose $v_1 v_2 \cdots v_{2k+1} \subsetneq P$ is a connected component with edges between $v_i$ and $v_{i+1}$. Without loss of generality, assume that $v_1 \leq_x v_2$. Since adjacent edges must be of differing types by our previous comment, we know that $v_{2k} \leq_x v_{2k+1}$. Then $v_{2k+1} = p_{2m}$ for some $m$, and we unravel the cahin to find that $v_1 = p_{2j}$ for some $j$. In particular this means that there exists $v_0 = p_{2j-1}$, and so $v_1$ is part of two edges of the same type. The same argument holds in the case where $v_1 \leq_y v_2$. So we know that any connected component of $P$ has an even number of edges.
Now that we have a decomposition of $P$ into components with an even number of edges, color the vertices of each component in an alternating pattern. This coloring satisfies the axis-parallel strip condition since you cannot expand a strip horizontally and pick up more than 2 vertices of a single color without picking up a vertex of the other color by construction, and similarly for expanding a strip vertically.
A: The next answer is not mine' but of my proffesor.
As been offered in the answer above me , we counstruct a graph which it's vertices are our points, and the edges constructed by pairs of points- by a non dec seq in x- axis and y-axis.
Now, since our edges are realy a $ matching$ , every cycle of it has even length.

Our graph is , by the bipartite graph characterization, bipartite, i.e $V= X \cup Y $ where X and Y are disjoint sets. Color X with blue and Y with red.
For given parellel strip, we can see that between every pair of one color points, there is a point colored by the opposite color. Hence, exept the "end pints" of the strip, we have split our strip into pairs of different colors. There are at most 2 end pints to a given strip- so we are done :) 

My proffesor mentioned that it's just an example to much deeper idea in math, called Discrepancy.
