# Euclidean Steiner Tree Question in Approximation Algorithms

Given $n$ points in $\mathbf{R}^2$, define the optimal Euclidean Steiner tree to be a minimum (Euclidean) length tree containing all $n$ points and any other subset of points from $\mathbf{R}^2$. Prove that each of the additional points must have degree 3, with all three angles being $120^\circ$.

• This sounds like homework. What have you tried? – adrianN May 8 '13 at 6:56
• It is just an exercise in my course book 'Approximation Algoritms', and I have finished it. – Jessie May 8 '13 at 11:13

Hint 2: For a higher degree $v$, replace two consecutive edges $(v,u_1), (v,u_2)$ by the Euclidean ST spanned between $v,u_1,u_2$.