Labelled spanning trees without edge crossings - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T07:17:14Z http://mathoverflow.net/feeds/question/49113 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/49113/labelled-spanning-trees-without-edge-crossings Labelled spanning trees without edge crossings Dr Shello 2010-12-12T04:08:45Z 2010-12-13T20:51:05Z <p>Draw the complete graph \$K_n\$ in the plane [<strong>added: in general position</strong>] 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\$?</p> http://mathoverflow.net/questions/49113/labelled-spanning-trees-without-edge-crossings/49171#49171 Answer by Tony Huynh for Labelled spanning trees without edge crossings Tony Huynh 2010-12-12T20:55:42Z 2010-12-13T13:30:26Z <p>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 \$V-p_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\$. </p> http://mathoverflow.net/questions/49113/labelled-spanning-trees-without-edge-crossings/49172#49172 Answer by Konrad Swanepoel for Labelled spanning trees without edge crossings Konrad Swanepoel 2010-12-12T21:03:20Z 2010-12-13T20:51:05Z <p>This is a theorem of Gyula Károlyi, János Pach and Géza Tóth: Ramsey-type results for geometric graphs. I. ACM Symposium on Computational Geometry (Philadelphia, PA, 1996). Discrete Comput. Geom. 18 (1997), no. 3, 247–255. <a href="http://dimacs.rutgers.edu/TechnicalReports/abstracts/1995/95-49.html" rel="nofollow">Link to preprint</a></p> <p>In this paper they indeed give an induction proof, but IMHO not an easy one.</p>