# Labelled spanning trees without edge crossings

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 edge-labels either all $0$ or all $1$?

-
Is this homework? There is an easy induction proof. – Aaron Meyerowitz Dec 12 '10 at 5:14
That was going to be my question, too. What got you to this question, and can you show us what you tried to do to solve it and where you got stuck? What effort have you put into this thus far? – sleepless in beantown Dec 12 '10 at 6:16
I agree with Aaron. See the FAQ for sites that are more appropriate for this question. – S. Carnahan Dec 12 '10 at 17:46
Hmm. I find this question being quite interesting (and do not see easy inductive argument, which Aaaron mentions). Vote for reopen. – Fedor Petrov Dec 12 '10 at 18:12
Should the points be in general position? If I put all the points on a line, colour the edge between the first and second point of the line blue, and the rest of the edges red, then I can't do it without edges intersecting. I am guessing your definition of edge crossing precludes this? – Tony Huynh Dec 12 '10 at 20:20

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.

-
G-x is not triangulation... – Fedor Petrov Dec 12 '10 at 21:08
I don't see how to fix this easily, so instead I'll add a reference to the literature.... – Konrad Swanepoel Dec 12 '10 at 22:46
thanks for the link! it is brilliant proof – Fedor Petrov Dec 12 '10 at 23:27
Awesome. For the historians, that paper mentions this problem is originally due to Bialostocki and Dierker. I learned about this problem from a friend of mine many years ago who was doing his PhD on cage graphs, was re-reading our notes from when I visited him and found it with a few (failed) attempts at proof (hence the MO post). I'd forgotten about it and I guess he never solved it... – Dr Shello Dec 13 '10 at 0:19
I've now deleted my own incorrect attempt at a proof. – Konrad Swanepoel Dec 13 '10 at 20:51

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

-
This is such a strong assumption that I would not call this an "answer". The question, as I understand it, starts with a god-given realization and asks for the property. I agree that the question seems quite interesting. – Igor Rivin Dec 12 '10 at 21:04
Igor, looking at geometric graphs in convex position is quite natural. So this is a good start. – Gil Kalai Dec 12 '10 at 22:07
Yes, adding the assumption of convexity makes it much easier; but I don't know if this proof can be extended to general position. – Dr Shello Dec 12 '10 at 22:50