Demostración de que el grado de cada vértice en un Árbol de Mínima Extensión (MST) es constante (es decir, no depende del número de vértices $n$ )

Question

Dado un conjunto de puntos S en $\mathbb{R}^2$ tenemos un MST de estos puntos.

Quiero demostrar que cada vértice tiene un grado en $\mathcal{O}(1)$ es decir, no depende del número de vértices del MST. Intuitivamente puedo ver que esto tiene que ser cierto, ya que de lo contrario habría ciclos y un montón de aristas y por lo tanto probablemente no un MST.

Se agradece cualquier pista.

Answer 1

Sugerencia: Supongamos que tenemos un árbol de expansión mínima $T$ , toma un vértice $v$ con otros dos vértices $v_1,v_2$ junto a $v$ y supongamos que el ángulo $\angle v_1 v v_2$ es $\alpha$ .

Desde $v$ es adyacente a $v_1$ y $v_2$ en el MST, debemos tener $d(v,v_1) + d(v,v_2)$ menos que las dos alternativas $d(v,v_1) + d(v_1,v_2)$ o $d(v,v_2) + d(v_1,v_2)$ . Por lo tanto, sólo tenemos que argumentar que (si $\alpha$ es lo suficientemente pequeño) tendremos que $d(v_1,v_2)$ es menor que el máximo de $d(v,v_1)$ y $d(v,v_2)$ .