Connected ( g, f )‐factors

In this paper we study connected ( g, f )‐factors. We describe an algorithm to connect together an arbitrary spanning subgraph of a graph, without increasing the vertex degrees too much; if the algorithm fails we obtain information regarding the structure of the graph. As a consequence we give sufficient conditions for a graph to have a connected ( g, f )‐factor, in terms of the number of components obtained when we delete a set of vertices. As corollaries we can derive results of Win [S. Win, Graphs Combin 5 (1989), 201–205], Xu et al. [B. Xu, Z. Liu, and T. Tokuda, Graphs Combin 14 (1998), 393–395] and Ellingham and Zha [M. N. Ellingham and Xiaoya Zha, J Graph Theory 33 (2000), 125–137]. We show that a graph has a connected [ a, b ]‐factor ( b > a  ≥ 2) if the graph is tough enough; when b  ≥  a  + 2, toughness at least $(a-1) + {a\over b-2}$ suffices. We also show that highly edge‐connected graphs have spanning trees of relatively low degree; in particular, an m ‐edge‐connected graph G has a spanning tree T such that deg T (υ) ≤ 2 + ⌈ deg G (υ)/ m ⌉ for each vertex υ. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 62–75, 2002