We ask, When does a graph G have a subgraph I' such that the vertices of odd degree in form a specified set S C V ( G ) , such that G -E(T) is connected? If such a subgraph can be found for a suitable choice of S, then this can be applied to problems such as finding a spanning eulerian subgraph of G. We provide a general method, with applications.
We shall use the notation of Bondy and Murty (61.
whose union equals G. Nash-Williams [20] proved that, if G is nontrivial,
The arboriciry a(G) of G is the minimum number of edge-disjoint forests where the maximum in (1) is taken over all induced nontrivial subgraphs H of G.
For a graph G with a subgraph H , the contraction GIH is the graph obtained from G by replacing H by a vertex uH, such that the number of edges in GIH
H equals the number of edges joining u in G to 8. This differs from the notation of [ S ] , in that multiple edges can arise in contractions, and no edge ofE(G) -E(H) is lost when H is contracted. V(G), we define an S-subgraph in G to be a subgraph r such that For S (i) G -E ( r ) is connected; and (ii) u E S if and only if d,(u) is odd.
A graph G is collapsible if G has an S-subgraph for every even set S C V(G).
We regard K , as being collapsible. It is equivalent that a graph G is collapsible if and only if, for any even set S ' C V ( G ) , G has a spanning connected subgraph G ' having S ' as its set of odd-degree vertices.