A Simple Proof of the Steiner Ratio Conjecture for Five Points

Abstract

The Steiner ratio conjecture of Gilbert and Pollak states that for any set of n points in the Euclidean plane, the ratio of the length of a Steiner minimal tree and the length of a minimal spanning tree is at least √3/2. This is shown to be true for n = 3 by Gilbert and Pollak [SIAM J. Appl. Math., 16 (1968), pp. 1–29], for n = 4 by Pollak [J. Combin. Theory Ser. A, 24 (1978), pp. 278–295], and for n = 5 by Du, Hwang, and Yao [J. Combin. Theory Ser. A, 38 (1985), pp. 230–240]. In this paper a simple and powerful approach is used to prove the conjecture for n = 5 by arguing simultaneously with minimal spanning trees and Steiner minimal trees.