Prove that the vertex degree of a minimum spanning tree is in $\mathcal{O}(1)$

Question

I have given a set of points $S$ in $\mathbb{R}^2$. From the this points I create a mininum spanning tree MST.

• The euclidean distance of the points is used as the weight for the edges.
• The connecting edges between the points are straight.
• The edges do not overlap in the MST.
• By MST I mean that I want a spanning tree where the sum of the distances is minimal.
• By spanning tree I mean that the it is a tree and all its vertices are connected.

I want to prove that for every MST like in the upper definition the vertex degree is in $\mathcal{O}(1)$.

Any ideas?

Answer 1

One can show that each vertex of your minimal spamming tree has less than 7 child.

Lets prove this by contradiction.

Assume that you have a minimal spamming tree $T=(V,E)$ and a vertex $v$ such that $v$ as 7 children, i.e. there exists $v_1$ ... $v_7$ all different such that $(v,v_i)\in E$ for all $i\in\{1...7\}$.

We denote $d(v',v'')$ the distance from $v'$ to $v''$, and $\measuredangle(v_i,v,v_j)$ the angle formed by the point $v_i,v,v_j$. Since $v$ has 7 children we know that there is to child (assume here that it is $v_1$ and $v_2$) such that $\measuredangle(v_1,v,v_2)<60°$. Assume that $d(v,v_1)\leq d(v,v_2)$.

We can deduce from $\measuredangle(v_1,v,v_2)<60 °$ and $d(v,v_1)\leq d(v,v_2)$ that $d(v_1,v_2)<d(v,v_2)$. Hence the tree $(V,E')$ with $E'=(E\setminus\{(v,v_2)\})\cup\{(v_1,v_2)\}$ is a smaller spamming tree. Contradiction with $T$ the minimal spamming tree.

I hope it's clear and it help.

EDIT: I missed the part: 'The edges do not overlap in the MST' in my last proof

We know from the previous part that if a Tree is a MST then each of it's vertex have less than 7 children. We now show that the edges of an MST do not overlap.

Again by contradiction. Assume we have an MST $T=(V,E)$ and two edges $(v_1,v_2)$ and $(v_1',v_2')$ that overlap.

Then considering the (may be flat) quadrilateral $v_1,v_1',v_2,v_2'$, $(v_1,v_2)$ and $(v_1',v_2')$ are the diagonals hence $d(v_1,v_2')+d(v_1',v_2)<d(v_1,v_2)+d(v_1,v_2')$ hence the tree $(V,E')$ with $E'=(E\setminus\{(v_1,v_2),(v_1',v_2')\})\cup\{(v_1,v_2'),(v_1',v_2) \}$ is smaller. Contradiction.

EDIT2 The edges $(v_1,v_1')$ and $(v_2,v_2')$ I chose in my previous answer may not preserve the tree property. I edited it in $(v_1,v_2'),(v_1',v_2)$ the do preserve the tree. (Thx DRF for the comment).