# Connecting points in a plane

If I have an even number $n$ of points in a plane (no $3$ of them colinear), half of them red and half of them blue, is there always a way to draw $\frac{n}{2}$ lines to join each red with a blue and each blue with a red in such a way that none of the lines between them intersect?

This was extra credit on an exam and I have no clue where to start. We've done exercises where we counted the number of ways to join red and blue points on a circle, but never something like this. How can I prove/disprove this claim?

Choose a point $P$ in the plane which is in the convex hull of the given points, but is not on any of the (finitely many) lines determined by the given points. Draw a line through $P$ which does not contain any given point. Consider $S$, one of the half planes determined by the line. Let $r(S)$ and $b(S)$ be the number of red and blue points in $S$ and suppose $r(S)-b(S)=m$.
Now rotate $S$ about $P$. Note that $S$ will always contain some, but never all, of the given points. When $S$ has been rotated by $180^{\rm o}$ it will contain precisely the points it didn't contain initially, so we have $r(S)-b(S)=-m$. But $r(S)-b(S)$ can only change by one unit at a time as $S$ rotates, so there must be a specific half plane $S_0$ for which $r(S_0)=b(S_0)$.
Now by induction we may assume that the points in $S_0$ may be connected as desired; also the points not in $S_0$; and lines in the two halves cannot intersect; so we are done.
• I also don't understand how we can say "by induction we may assume that the points in $S_0$ may be connected as desired". Isn't it just as hard of a problem to connect that half set? Or are we doing some sort of infinite regress thing where you then apply the proof to that half plane? – NMister Mar 20 '18 at 11:18