Graphs without spanning closed trails Original Research Article

Jaeger (1979) proved that if a graph has two edge-disjoint spanning trees, then it is supereulerian, i.e., that it has a spanning closed trail. Catlin (1988) showed that if G is one edge short of having two edge-disjoint spanning trees, then G has a cut edge or G is supereulerian. Catlin conjectured that if a connected graph G is at most two edges short of having two edge-disjoint spanning trees, then either G is supereulerian or G can be contracted to a K2 or a K2,t for some odd integer t ⩾ 1. We prove Catlinʹs conjecture in a more general context. Applications to spanning trails are discussed.