Labelled spanning trees without edge crossings - MathOverflow

Labelled spanning trees without edge crossings

2010-12-12T04:08:45Z

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$?

Answer by Tony Huynh for Labelled spanning trees without edge crossings

2010-12-12T20:55:42Z

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$.

Answer by Konrad Swanepoel for Labelled spanning trees without edge crossings

2010-12-12T21:03:20Z

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. Link to preprint

In this paper they indeed give an induction proof, but IMHO not an easy one.