In this problem, Show that given n red points and n blue points in the plane such that no three points lie on a common line, it is possible to draw

In this problem, Show that given n red points and n blue points in the plane such that no three points lie on a common line, it is possible to draw line segments between red-blue pairs so that all the pairs are matched and none of the line segments intersect. Assume that there are n red and n blue points fixed in the plane.

A matching M is a collection of n line segments connecting distinct red-blue pairs. The total length of a matching M is the sum of the lengths of the line segments in M. Say that a matching M is minimal if there is no matching with a smaller total length.

Let IsMinimal(M) be the predicate that is true precisely when M is a minimal matching. Let HasCrossing(M) be the predicate that is true precisely when there are two line segments in M that cross each other. Give an argument in English explaining why there must be at least one matching M so that IsMinimal(M) is true, i.e.

∃MIsMinimal(M)

Give an argument in English explaining why

∀M(HasCrossing(M) → ¬IsMinimal(M))

Now use the two results above to give a proof of the statement: ∃M¬HasCrossing(M).