Given a graph , the metric polytope is defined by the inequalities for , odd, C cycle of G, and for . Optimization over provides an approximation for the max-cut problem. The graph G is called 1/d-integral if all the vertices of have their coordinates in . The authors prove that the class of 1/d-integral graphs is closed under minors, and we present several minimal forbidden minors for -integrality. In particular, they characterize the -integral graphs on seven nodes. The authors study several operations preserving 1/d-integrality, in particular, the k-sum operation for . They prove that series parallel graphs are characterized by the following stronger property. All vertices of the polytope are -integral for every choice of -integral bounds , u on the edges of G.
