Graphic vertices of the metric polytope

The metric polytope MP n is defined by the triangle inequalities: x ij − x ik − x jk ⩽ 0 and x ij + x ik + x jk ⩽ 2 for all triples i, j, k of (1, …, n). The integral vertices of MP n are the incidence vectors of the cuts of the complete graph K n . Therefore, MP n is a relaxation of the cut polytope of K n . We study here the fractional vertices of MP n . Many of them are constructed from graphs; this is the case for the one-third-integral vertices. One-third-integral vertices are, in a sense, the simplest fractional vertices of MP n as MP n has no half-integral vertices. Several constructions for one-third-integral vertices are presented. In particular, the graphic vertices arising from the suspension of a tree are characterized. We describe the symmetries of MP n , and obtain that the vertices are partitioned into switching classes. With the exception of the cuts which are pairwise adjacent, it is shown that no two vertices of the same switching class are adjacent on MP n . The question of adjacency of the fractional vertices to the integral ones is also addressed. All the vertices of MP n for n ⩽ 6 are described.