It is known that the Minimum Spanning Tree (MST) of a finite set of points in the Euclidean plane is contained in the point set's Delaunay triangulation, but is that all that can be said about their relation?



> 
> **Question:**
> 
> 
> can the *longest* side of a triangle in the Delaunay triangulation of a planar point set be an edge of that point set's MST or can these edges be unconditionally ruled out as MST edges?
> 
> 
> 



Relation of MSTs in the Euclidean plane to Delaunay triangulations
It cannot be for any planar triangulation. Say we have a triangle with vertices $x, y, z$ and $xy$ is the longest edge.


Consider a run of [Prim’s MST algorithm](https://en.m.wikipedia.org/wiki/Prim%27s_algorithm) which at each step adds an edge to a growing tree if it is minimum length among all those edges that have exactly one endpoint already in the tree.


Say without loss of generality that $x$ is added to the tree before $y$. If $xy$ gets added to the tree at some step, then it is minimum weight among all edges with exactly one endpoint in the tree.


Because it is longer than $xz$, this means that $z$ must already be in the tree, otherwise we would have chosen to add $xz$ instead since it’s shorter than $xy$.


But if $z$ is already in the tree, then at this step we would choose to add $zy$ over $xy$ because it is shorter.


Thus it’s impossible that we add $xy$ at any step of the algorithm, so it’s not in the MST.


