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 monochromatic spanning red or blue plane tree $T$. In either case, we can extend $T$ to a spanning monochromatic plane tree of $V$.
|
3 | added 16 characters in body | ||
|
|
||||
|
|
2 | deleted 62 characters in body | ||
|
Here is a proof under the assumption that $x \notin conv(V-x)$, for all $x \in V$. So, the vertices of $G$ V$ are the vertices of a convex polygonin the plane. 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 monochromatic plane tree $T$. In either case, we can extend $T$ to a monochromatic plane tree of $V$. |
||||
|
|
1 |
|
||
|
Here is a proof under the assumption that $x \notin conv(V-x)$, for all $x \in V$. So, the vertices of $G$ are the vertices of a convex polygon in the plane. 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 monochromatic plane tree $T$. In either case, we can extend $T$ to a monochromatic plane tree of $V$. |
||||
