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$?
$\begingroup$
$\endgroup$
9
-
1$\begingroup$ Is this homework? There is an easy induction proof. $\endgroup$– Aaron MeyerowitzDec 12, 2010 at 5:14
-
1$\begingroup$ 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? $\endgroup$– sleepless in beantownDec 12, 2010 at 6:16
-
$\begingroup$ I agree with Aaron. See the FAQ for sites that are more appropriate for this question. $\endgroup$– S. Carnahan ♦Dec 12, 2010 at 17:46
-
5$\begingroup$ Hmm. I find this question being quite interesting (and do not see easy inductive argument, which Aaaron mentions). Vote for reopen. $\endgroup$– Fedor PetrovDec 12, 2010 at 18:12
-
1$\begingroup$ 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? $\endgroup$– Tony HuynhDec 12, 2010 at 20:20
|
Show 4 more comments
2 Answers
$\begingroup$
$\endgroup$
4
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.
answered Dec 12, 2010 at 21:03
-
3
-
$\begingroup$ I don't see how to fix this easily, so instead I'll add a reference to the literature.... $\endgroup$ Dec 12, 2010 at 22:46
-
$\begingroup$ 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... $\endgroup$ Dec 13, 2010 at 0:19
-
$\begingroup$ I've now deleted my own incorrect attempt at a proof. $\endgroup$ Dec 13, 2010 at 20:51
$\begingroup$
$\endgroup$
3
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$.
answered Dec 12, 2010 at 20:55
-
1$\begingroup$ 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. $\endgroup$ Dec 12, 2010 at 21:04
-
2$\begingroup$ Igor, looking at geometric graphs in convex position is quite natural. So this is a good start. $\endgroup$ Dec 12, 2010 at 22:07
-
$\begingroup$ Yes, adding the assumption of convexity makes it much easier; but I don't know if this proof can be extended to general position. $\endgroup$ Dec 12, 2010 at 22:50