# 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
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.

For a set of points in the plane with no three collinear, the complete geometric graph has vertex set and edge set consisting of the straight line-segments between each pair of points in .

Since each subtree of has at most edges, every partition of into subtrees has at least parts. The conjecture asks for such a partition into exactly subtrees, such that in addition, no two edges in each subtree cross.

It is folklore that the conjecture is true if 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 vertices can be partitioned into at most plane subtrees.