On the diameter of cut polytopes

In this paper, we study the diameter of these two families of polytopes. For a connected graph G, we prove that the diameter of CUT(G) is at most |V|−1, improving on the bound of |E| given by F. Barahona and A.R. Mahjoub. We also give its exact value for trees and complete bipartite graphs. Then, with respect to uniform cut polytopes, we introduce sufficient conditions for adjacency of two vertices in CUT=k(G), we study some particular cases and provide some connections with other partition polytopes from the literature.