Spanning Eulerian Subgraphs and Catlin’s Reduced Graphs

Abstract

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(\frac{n}{15}–1)$ 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].