There is a finite set of points $S$ in the plane with $ |S| = n$. MST is the minimal spanning tree of S. "Minimal" here refers to the Euclidean distance between the points of $S$, so the MST is the minimum spanning tree with the lowest overall distance.
I want to prove that the degree of every node is in O(1).
I tried to use Euler's Theorem but unfortunately this did not lead to a solution. Any ideas?
Here is a proof sketch from Robins and Salowe, On the Maximum Degree of Minimum Spanning Trees. Let $x$ be some vertex in the MST. We want to show that its degree $d$ is small.
Let $y_1,\ldots,y_d$ be its neighbors. Draw a small circle of radius $\epsilon$ around $x$, and "project" each $y_i$ to a point $z_i$ on the circle: the point $z_i$ is just the intersection of the line $\overline{x y_i}$ and the circle. The idea is to show that all of these projections are far from each other.
Indeed, consider any pair of points $y_i,y_j$, and suppose without loss of generality that $\|x-y_i\| \leq \|x-y_j\|$. Repeat the same process as before, but with a circle of radius $\|x-y_i\|$. The projections are $w_i = y_i$ and $w_j$. The triangle $\Delta xz_iz_j$ and $\Delta xy_iw_j$ are similar, and so $\|z_i-z_j\|/\epsilon = \|y_i-w_j\|/\|x-y_i\|$.
On the other hand, consider the circle $\Delta xy_iy_j$. Two of the edges are in the minimum spanning tree, so the remaining edge must be a heaviest edge. Since we assumed that $\|x-y_i\| \leq \|x-y_j\|$, this means that $\|y_i-y_j\| \geq \|x-y_j\|$. Therefore $\|x-y_j\| \leq \|y_i-y_j\| \leq \|y_i-w_j\| + \|w_j-y_j\|$. Since $w_j$ is on the line from $x$ to $y_j$, we have $\|x-y_j\| = \|x-w_j\| + \|w_j-y_j\|$, and so $\|x-w_j\| \leq \|y_i-w_j\|$. Since $w_j$ is on the circle of radius $\|x-y_i\|$ centered at $x$, this shows that $\|x-y_i\| \leq \|y_i-w_j\|$.
Combining the formula $\|z_i-z_j\|/\epsilon = \|y_i-w_j\|/\|x-y_i\|$ with the inequality $\|x-y_i\| \leq \|y_i-w_j\|$, we deduce that $\|z_i - z_j\| \geq \epsilon$. Summarizing, $z_1,\ldots,z_d$ are points on a circle of radius $\epsilon$ which are at distance at least $\epsilon$ from each other. This forces $d \leq 6$.
Perhaps the following diagram will be useful:
Suppose that the inner circle has radius $\epsilon$. We want to show that $\|z_i-z_j\| \geq \epsilon$. Due to the MST property, we know that $\|y_i-y_j\| \geq \|x-y_j\|$. Thus necessarily $\|y_i-w_j\| \geq \|x-w_j\|$. This implies $\|z_i-z_j\| \geq \|x-z_j\|$ due to similarity of triangles.
Robins and Salowe note that when $d = 6$, the points are packed tightly. It turns out that there is always an MST in which there is always some jiggle room, and so some MST has maximum degree at most $5$.
The same argument works in $D$ dimensions and in any metric, as long as there is a bound on the number of points on a unit ball which are at least a unit distance away from each other. This property holds in all $L_p$ metrics (for finite $p$!) in any dimension.
