Subtree of Delaunay Triangulation
All edges of an EMST are edges of a relative neighborhood graph, which in turn are edges of a Gabriel graph, which are edges in a Delaunay triangulation of the points, as can be proven via the equivalent contrapositive statement: every edge not in a Delaunay triangulation is also not in any EMST. The proof is based on two properties of minimum spanning trees and Delaunay triangulations:
- (the cycle property of minimum spanning trees): For any cycle C in the graph, if the weight of an edge e of C is larger than the weights of other edges of C, then this edge cannot belong to a MST.
- (a property of Delaunay triangulations): If there is a circle with two of the input points on its boundary which contains no other input points, the line between those two points is an edge of every Delaunay triangulation.
Consider an edge e between two input points p and q which is not an edge of a Delaunay triangulation. Property 2 implies that the circle C with e as its diameter must contain some other point r inside. But then r is closer to both p and q than they are to each other, and so the edge from p to q is the longest edge in the cycle of points p → q → r → p, and by property 1 e is not in any EMST.
Read more about this topic: Euclidean Minimum Spanning Tree