Week 4

This week I continued attempting to show that size $n$ stars yield the lowest weight Euclidean Steiner trees among all size $n$ graphs, when using our map to point configurations. We have tried a number of techniques to no avail: mathematical programming formulations, fixed points in Smith's algorithm, contraction mappings, etc.

The full proof is still difficult to find, but I have been able to show that, for every graph of diameter more than $2$, there is a graph of the same size with diameter at most $2$ with a Steiner tree of at most the weight of the original graph.

I also managed to prove a number of other nice properties about optimal Steiner trees resultant from this graph mapping, confirming our intuition. For fun, see below the optimal Steiner tree of the point mapping of a size 10 star, generated using Smith's algorithm and the Sage code I have been writing to explore my conjecures.