A complete classification of metrizable and strictly metrizable theta graphs

Abstract

Cizma and Linial asked for a classification of the metrizable theta graphs. We solve both their problem and its strict analogue. For $a\le b\le c$, the theta graph ${\Theta }_{a,b,c}$ is metrizable if and only if $a\le 2$ or $(a,b,c)=(3,3,3)$, and it is strictly metrizable if and only if $a\le 2$. Thus ${\Theta }_{3,3,3}$ is precisely the exceptional theta graph that is metrizable but not strictly metrizable. The negative directions follow from the known obstructions ${\Theta }_{3,3,4}$ and ${\Theta }_{3,3,3}$ together with topological-minor closure. The positive direction is constructive. Consistency turns the possible detours through a length-two arm into compatible Ferrers relations, which are represented by one-dimensional potentials; all resulting shortest-path comparisons have positive slack. The exceptional ordinary-metrizable graph ${\Theta }_{3,3,3}$ is handled by a two-threshold weak Ferrers representation. The proof is structural, yields rational edge lengths algorithmically, and uses no enumeration of path systems.

arXiv comment26 pages