Spanning Eulerian Subgraphs and Catlin’s Reduced Graphs

A graph \( G \) is collapsible if for every even subset \( R \subseteq V(G) \), there is a spanning connected subgraph \( H_R \) of \( G \) whose set of odd degree vertices is \( R \). A graph is reduced if it has no nontrivial collapsible subgraphs. Catlin [4] showed that the existence of spanning Eulerian subgraphs in a graph \( G \) can be determined by the reduced graph obtained from \( G \) by contracting all the collapsible subgraphs of \( G \). In this paper, we present a result on 3-edge-connected reduced graphs of small orders. Then, we prove that a 3-edge-connected graph \( G \) of order \( n \) either has a spanning Eulerian subgraph or can be contracted to the Petersen graph if \( G \) satisfies one of the following:

1. \( d(u) + d(v) > 2\left(\frac{n}{15} – 1\right) \) for any \( uv \notin E(G) \) and \( n \) is large;
2. the size of a maximum matching in \( G \) is at most 6;
3. the independence number of \( G \) is at most 5.

These are improvements of prior results in [16], [18], [24], and [25].