Graphic vertices of the metric polytope (Q1916387)

The paper studies the polytope called the metric polytope \(\text{MP}_n\) defined by the triangle inequalities: \(x_{ij}- x_{ik}- x_{jk}\leq 0\) and \(x_{ij}+ x_{ik}+ x_{jk}\leq 2\) for all \(i, j, k\in \{1, 2,\dots, n\}\). It studies the fractional vertices of \(\text{MP}_n\), many of which are constructed from graphs. Several constructions for one-third-integral vertices are presented, and, in particular, the graphic vertices arising from the suspension of a tree are characterized. The paper describes the symmetries of \(\text{MP}_n\) and obtains that the vertices are partitioned into switching classes. It is shown that, with the exception of the cuts which are pairwise adjacent, no two vertices of the same switching class are adjacent on \(\text{MP}_n\). In fact, all the vertices of \(\text{MP}_n\) for \(n\leq 6\) are described.