The problem of finding a minimum-weight k-connected spanning subgraph of a complete graph, assuming that the edge weights satisfy the triangle inequality, is studied. It is shown that the class of minimum-weight k-edge connected spanning subgraphs can be restricted to those subgraphs which, in addition to the connectivity requirements, satisfy the following two conditions: (I) Every vertex has degree k or ; (II) Removing any or k edges does not leave the resulting connected components all k-edge connected. For the k-vertex connected case, the parallel result is obtained with “k-edge” replaced by “k-vertex,” with the added technical restriction that for condition (I) to hold. This generalizes recent work of Monma, Munson, and Pulleyblank for the case .