Iranian Mathematical Olympiad

For $n=6$ there are 16 combinatorially different point sets (order types). It is easy to check that all these 16 cases allow for 3 edge-disjoint plane spanning trees.

Let $S$ be a set of $n$ points in the plane and let $e=(r,b)$ be an edge spanned by $S$ having exactly 4 points of $S$ on one side (i.e., on one side of the straight line ${\ell }_e$ supporting $e$). Let $S^{\prime }$ be the set of 6 points containing $r,b$, and the exactly 4 points on one side of $e$. By the above claim, $S^{\prime }$ contains 3 edge-disjoint plane spanning trees. For sake of simplicity, we call them red, blue, and green. Without loss of generality, assume that $e$ is a part of the red tree. Note that each point of $S^{\prime }$ is incident to all three trees, and that $r$ and $b$ are extremal points for $S\setminus (S^{\prime }\{r,b\})$. We construct a red and a blue plane spanning trees by connecting $r$ and $b$, respectively, with all points in $S\setminus S^{\prime }$.

Next, we shall construct the third (green) plane spanning tree on $S$. Note that the green plane spanning tree on $S^{\prime }$ can be completed by a triangulation $T$. Let $q$ be a point of $S^{\prime }\setminus \{r,b\}$, such that $qrb$ is a triangle in $T$. Observe that any edge incident to $q$ and crossing $e$ does not cross a green edge. Assume that there exists a point $q^{\prime }\in (S{\S }^{\prime })$ such that the edge $q{q}^{\prime }$ crosses $e$. Then we connect $q$ and $q^{\prime }$ with a green edge and complete the green plane spanning tree by connecting all points in S\(S'\cup\{q'\}) with $q^{\prime }$. If such a point $q^{\prime }$ does not exist, then there must be an edge $e^{\prime }$ of the convex hull of $S$, such that $e^{\prime }$ crosses ${\ell }_e$. Denote by $p$ the endpoint of $e^{\prime }$ in $S{\S }^{\prime }$. We shall color $e$ by green and complete the green plane spanning tree by connecting all points in S\(S'\cup\{p\}) with $p$.