The k-edge connected subgraph problem I: Polytopes and critical extreme points

AbstractIn this paper we consider the linear relaxation of the k-edge connected subgraph polytope, P(G,k), given by the trivial and the so-called cut inequalities. We introduce an ordering on the fractional extreme points of P(G,k) and describe some structural properties of the minimal extreme points with respect to that ordering. Using this we give sufficient conditions for P(G,k) to be integral