Edge-Connectivity on the Assignment Polytope

In this paper, a proof is constructed to show tbat assignment polytope of order n is edge N(n) connected where N(n) is the number of adjacent vertices to any vertex on the assignment polytope. This settles the conjecture made by Balinski and Russakeff on the assignment polytope in its weeker form. Furthermore, the set of N(n) edge-disjoint paths need not consist of a path of length greater than four. The result is extended to all polytopes of diameter two and paths can be constructed there of provided the corresponding adjacency rules are known.