Augmenting hypergraphs by edges of size two

We give a good characterization for the minimum number of edges of size two whose addition to a given hypergraph H makes it k-edge-connected. Our resu lt extends a previous theorem by E. Cheng [4] for the case when H is alread y (k - 1)-edge-connected. We also describe a strongly polynomial algorithm to find both a minimum cardinality augmentation, and a minimum cost augment ation where the cost of an edge is equal to the sum of the weights of its e ndvertices, for some given weight function on V(H). Our proof is based on a new 'splitting' theorem for hypergraphs for the case when the special vert ex s is only incident with edges of size two. This theorem generalizes a 's plitting' result of Lovasz for graphs.