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$?
Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)
|
9
3
|
||||||||||||||||||||||||
|
|
2
|
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$. |
|||||||||||||
|
You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.
|
8
|
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. |
|||||||||||||||||||
|
