A complete classification of metrizable theta graphs

Abstract

Cizma and Linial introduced graph metrizability as the problem of deciding whether every consistent system of prescribed paths in a graph can be realized by shortest paths for some positive edge lengths. They asked for a classification of the metrizable theta graphs. We give the complete classification. If $a\le b\le c$, then the theta graph $\hat{I}{˜}_{a,b,c}$ is metrizable if and only if $a\le 2$ or $(a,b,c)=(3,3,3)$. The non-metrizable direction follows from the known obstruction $\hat{I}{˜}_{3,3,4}$ and topological-minor closure. The positive direction is constructive. For the family $\hat{I}{˜}_{2,b,c}$, consistency forces certain same-arm and cross-arm choices to be Ferrers relations, and these relations are realized by one-dimensional potentials. The exceptional graph $\hat{I}{˜}_{3,3,3}$ is handled by a two-threshold version of the same construction. The proof is structural and does not rely on enumeration of path systems.

27 pages