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