MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

3 Removed incorrect attempt at a proof.

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.

As pointed out by Fedor Petrov, the following induction attempt fails on its own:

That $K_n$ is given, is a bit of a red herring. Replace it by a triangulation $G$ of the $n$ given points. The statement is trivial when all edges are labelled $0$, or all are labelled $1$. So without loss of generality, there is a vertex $x$ incident to a $0$-edge and a $1$-edge. By induction, $G-x$ has a spanning tree with all edges labelled the same, say with label $0$. Put $x$ back together with any $0$-edge incident to it, to obtain a spanning tree of the original set of points with all edges labelled $0$.

And of course the base case $n\leq 3$ is trivial.

2 added 481 characters in body

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.

As pointed out by Fedor Petrov, the following induction attempt fails on its own:

That $K_n$ is given, is a bit of a red herring. Replace it by a triangulation $G$ of the $n$ given points. The statement is trivial when all edges are labelled $0$, or all are labelled $1$. So without loss of generality, there is a vertex $x$ incident to a $0$-edge and a $1$-edge. By induction, $G-x$ has a spanning tree with all edges labelled the same, say with label $0$. Put $x$ back together with any $0$-edge incident to it, to obtain a spanning tree of the original set of points with all edges labelled $0$.

And of course the base case $n\leq 3$ is trivial.

1

That $K_n$ is given, is a bit of a red herring. Replace it by a triangulation $G$ of the $n$ given points. The statement is trivial when all edges are labelled $0$, or all are labelled $1$. So without loss of generality, there is a vertex $x$ incident to a $0$-edge and a $1$-edge. By induction, $G-x$ has a spanning tree with all edges labelled the same, say with label $0$. Put $x$ back together with any $0$-edge incident to it, to obtain a spanning tree of the original set of points with all edges labelled $0$.

And of course the base case $n\leq 3$ is trivial.