# Partition of Complete Geometric Graph into Plane Trees

 Importance: Medium ✭✭
 Author(s):
 Subject: Geometry
 Keywords: complete geometric graph, edge colouring
 Posted by: David Wood on: October 19th, 2009

\begin{conjecture} Every complete geometric graph with an even number of vertices has a partition of its edge set into plane (i.e. non-crossing) spanning trees. \end{conjecture}

For a set $P$ of $n$ points in the plane with no three collinear, the \emph{complete geometric graph} $K_P$ has vertex set $P$ and edge set consisting of the $\binom{n}{2}$ straight line-segments between each pair of points in $P$.

Since each subtree of $K_P$ has at most $n-1$ edges, every partition of $E(K_P)$ into subtrees has at least $\frac{n}{2}$ parts. The conjecture asks for such a partition into exactly $\frac{n}{2}$ subtrees, such that in addition, no two edges in each subtree cross.

It is folklore that the conjecture is true if $P$ is in convex partition. In fact, the edge set of the complete convex graph can be partitioned into plane Hamiltonian paths. Bose et al. [BHRW] characterised all possible partitions of the complete convex graph into plane spanning trees. Bose et al. [BHRW] also proved that every complete geometric graph on $n$ vertices can be partitioned into at most $n-\sqrt{\frac{n}{12}}$ plane subtrees.