Graham's problem on shortest networks for points on a circle (Q1186796)

Given a finite set of points \(x_ 1,x_ 2,\dots,x_ n\) in the Euclidean plane. The problem of finding a network of smallest total length which connects up the points is called the Steiner problem and a solution is a Steiner tree or a Steiner minimum tree. When the points are located on a circle of radius \(r\) with \(x_ i\) adjacent to \(x_{i+1}\), \(1\leq i\leq n-1\) and at most one edge \(x_ ix_{i+1}\) and \(x_ nx_ 1\) has length greater than \(r\), the authors prove that a Steiner tree consists of all edges \(x_ ix_{i+1}\) plus \(x_ nx_ 1\), \(1\leq i\leq n-1\) with the longest edge removed.