Large Spanning Eulerian Subgraphs of Simple 5-Regular Supereulerian Graphs

For a graph G, let V(G) and E(G) denote its vertex and edge sets, and put n=|V(G)| and m=|E(G)|. For a supereulerian graph G, let ℓ(G) be the maximum number of edges in a spanning Eulerian subgraph of G. Haghparast and Kiani proved that each simple 5-regular supereulerian graph with m edges satisfies ℓ(G)≥1930m+43. We improve this estimate to ℓ(G)≥4975m+1615. Furthermore, we give a stronger integral bound ℓ(G)≥32n+⌈2n+1615⌉. In particular, the 23 estimate holds when n≤42. The proof studies the forest complementary to a maximum spanning Eulerian subgraph and combines cycle-space averaging, bridge counting, and density bounds for the blocks of a quotient multigraph.