Draw the complete graph $K_n$ on a plane 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 edgelabels either all $0$ or all $1$?

This is a theorem of Gyula Károlyi, János Pach and Géza Tóth: Ramseytype results for geometric graphs. I. ACM Symposium on Computational Geometry (Philadelphia, PA, 1996). Discrete Comput. Geom. 18 (1997), no. 3, 247–255. Link to preprint In this paper they indeed give an induction proof, but IMHO not an easy one. 


Here is a proof under the assumption that the vertices $V$ are the vertices of a convex polygon. Label these as $p_1, \dots, p_n$ in cyclic order (the subscripts should be read modulo $n$). If all the edges $p_ip_{i+1}$ are red, then we are done. Otherwise, we may assume that $p_1p_2$ is red, and $p_n p_1$ is blue. By induction, we have that $Vp_1$ has a spanning red or blue plane tree $T$. In either case, we can extend $T$ to a spanning monochromatic plane tree of $V$. 

