ON SPARSE SUBGRAPHS PRESERVING CONNECTIVITY PROPERTIES

From a theorem of W. Mader [''Uber minimal n-fach zusam-menhangende unendliche Graphen und ein Extremal problem,'' Arch. Mat., Vol. 23 (1972), pp. 553-560] it follows that a k-connected (k-edge-connected) graph G = (V, E) always contains a k-connected (k-edge-connected) subgraph G' = (V,E') with O(k absolute value of V) edges. T. Nishizeki and S. Poljak [''K-Connectivity and Decomposition of Graphs into Forests,'' Discrete Applied Mathematics, submitted) showed how G' can be constructed as the union of k forests. H. Nagamochi and T. lbaraki [A Linear Time Algorithm for Finding a Sparse k-Connected Spanning Subgraph of a k-Connected Graph,'' Algorithmica, Vol. 7 (1992), pp. 583-596] constructed such a subgraph G(k) in linear time and showed for any pair x,y of nodes that G(k) contains k openly disjoint (edge-disjoint) paths connecting x and y if G contains k openly disjoint (edge-disjoint) paths connecting x and y (even if G is not k-connected (k-edge-connected)). In this article we provide a much shorter proof of a common generalization of the edge- and node-connectivity versions showing that the subgraph G(k) has a certain mixed connectivity property.