Show that a MST is a subgraph of the Delauney Triangulation

115 Views Asked by At

I am working on the following exercise:

Let $V$ be a finite set of points in $\mathbb{R}^2$. Consider

$$P_v := \{x \in \mathbb{R}^2 : \lvert\lvert x-v \rvert\rvert = \min_{u \in V} \lvert\lvert x - u \rvert\rvert_2 \}$$

and the Delauney Triangulation $G_D$ (defined as a graph)

$$G_D := \big(V, \quad \big\{ \{u,v\} \subseteq V, v \ne u, \lvert P_u \cap P_v \rvert > 1 \big\}\big).$$

Show that for a complete graph $G(V,E)$ with weights defined by $$w(u,v) := \lvert\lvert u - v \rvert\rvert_2 \quad (\forall e \in E(G))$$ holds that every minimum spanning tree (MST) is a subgraph of the Delauney Triangulation $G_D$.

My attempt looks as follows: Let $T$ be a MST in $G$. It suffices to show that for an arbitrary $e := \{u,v\} \in E(T)$ holds $e \in E(G_D)$. Since the $G$ is assumed to be complete we know that $e$ is the smallest edge incident to $u$ and thus the point $u+(u-v)/2 \in P_u \cap P_v$.

Is it really that simple?