Gilbert-Pollak conjecture (Steiner ratio)

Description of constant

$C_{43}$ is defined as the infimum of the ratio of the length of the Steiner Minimal Tree to the length of the Euclidean Minimum Spanning Tree over all finite sets of points $V \subseteq \mathbb{R}^2$: $C_{43} = \inf_{V}L_S(V)/L_M(V)$, where $L_S(V)$ and $L_M(V)$ denote the lengths of Steiner Minimal Tree and Minimum Spanning Tree, respectively.

Consider a set $V$ of $n$ points in the Euclidean plane $\mathbb{R}^2$. A spanning tree on $V$ is a connected, acyclic graph with vertex set $V$. When the length of each edge is defined as the Euclidean distance between its endpoints, a spanning tree that minimizes the total length is called a Minimum Spanning Tree. The shortest network interconnecting all points in $V$, where the length of each edge is measured by Euclidean distance, is necessarily a tree, referred to as a Steiner Minimal Tree. A Steiner Minimal Tree may contain auxiliary vertices not in $V$.

Known upper bounds

Known lower bounds

Additional comments

• In 1968, Gilbert and Pollak conjectured that Steiner ratio is $\sqrt{3}/2 \approx 0.866$, but this remains unproven. More information can be found at Wikipedia page on the Gilbert-Pollak conjecture.

References

• [GP1968] Gilbert, E. N. and Pollak, H. O. Steiner minimal trees. SIAM Journal on Applied Mathematics, 16(1):1–29, 1968.
• [GH1976] Graham, R. L. and Hwang, F. K. Remarks on steiner minimal trees. Bull. Inst. Math. Acad. Sinica, 4(1):177–182, 1976.
• [CH1978] Chung, F. and Hwang, F. A lower bound for the steiner tree problem. SIAM Journal on Applied Mathematics, 34(1): 27–36, 1978.
• [DH1983] Du, D.-Z. and Hwang, F. K. A new bound for the steiner ratio. Transactions of the American Mathematical Society, 278(1):137–148, 1983.
• [CG1985] Chung, F. R. and Graham, R. L. A new bound for euclidean steiner minimal trees. Annals of the New York Academy of Sciences, 440(1):328–346, 1985.
• [KHSHGW2026] Ke, Y., Huang, T., Shu, Y., He, D., Gai, J., and Wang, L. Towards Solving the Gilbert-Pollak Conjecture via Large Language Models. arXiv:2601.22365. Preprint (2026).