Spanning subgraph with Eulerian components

A graph is kk-supereulerian if it has a spanning even subgraph with at most kk components. We show that if GG is a connected graph and G′G′ is the (collapsible) reduction of GG, then GG is kk-supereulerian if and only if G′G′ is kk-supereulerian. This extends Catlin’s reduction theorem in [P.A. Catlin, A reduction method to find spanning Eulerian subgraphs, J. Graph Theory 12 (1988) 29–44]. For a graph GG, let F(G)F(G) be the minimum number of edges whose addition to GG create a spanning supergraph containing two edge-disjoint spanning trees. We prove that if GG is a connected graph with F(G)≤kF(G)≤k, where kk is a positive integer, then either GG is kk-supereulerian or GG can be contracted to a tree of order k+1k+1. This is a best possible result which extends another theorem of Catlin, in [P.A. Catlin, A reduction method to find spanning Eulerian subgraphs, J. Graph Theory 12 (1988) 29–44]. Finally, we use these results to give a sufficient condition on the minimum degree for a graph GG to bekk-supereulerian.