MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

Draw the complete graph $K_n$ in the plane [added: in general position] with every edge a straight line and randomly label the edges $0$ or $1$. Does this graph always have a spanning tree with no edges crossing and edge-labels either all $0$ or all $1$?