# Show that no lines need cross [closed]

There are n red points and n blue points in the plane. Show that you can always join all the red and blue points with straight lines so that no two lines cross. Each point can have exactly one line joining to or from it. No three points are colinear.

## 2 Answers

This is a classic proof:

Pair up each red dot to a blue dot, and connect them with straight line segments. Of course there will probably be intersecting line segments. Whenever you have a pair of crossing segments, you can uncross them (If the segments were R1-B1 and R2-B2, change them to R1-B2 and R2-B1). Doing this may introduce new crossings, but if you keep uncrossing them, eventually you will arrive at an arrangement with no crossings.
To see why, let L be the total length of all the segments. There are only finitely many possible values for L because there are only finitely many arrangments of segments (there are n! possible pairings so at most n! possible values). Furthermore, every uncrossing step reduces the value of L. Therefore there will come a moment where L can not be reduced any further, i.e. a moment when there are no more segments that can be uncrossed.

For red point 𝑖 and blue point 𝑗, let 𝑑𝑖,𝑗 be the Euclidean distance between them. Now consider a minimum-weight matching in the corresponding bipartite graph. It will not have any crossings because otherwise the triangle inequality implies that the matching can be improved. Explicitly, if edges (𝑖1,𝑗1) and (𝑖2,𝑗2) cross, then replacing these edges with (𝑖1,𝑗2) and (𝑖2,𝑗1) yields a matching with a smaller weight.