Skip to main content
MathOverflow

Return to Answer

Removed incorrect attempt at a proof.
Source Link
Konrad Swanepoel
Konrad Swanepoel
  • 3.5k
  • 2
  • 25
  • 23

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.

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.

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.

added 481 characters in body
Source Link
Konrad Swanepoel
Konrad Swanepoel
  • 3.5k
  • 2
  • 25
  • 23

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.

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.

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.

Source Link
Konrad Swanepoel
Konrad Swanepoel
  • 3.5k
  • 2
  • 25
  • 23

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.