A Note on the Maximum Number of Edges of a Spanning Eulerian Subgraph

Abstract

A graph \(G\) is supereulerian if \(G\) has a spanning eulerian subgraph. We use \(\mathcal{SL}\) to denote the families of supereulerian graphs. In 1995, Zhi-Hong Chen and Hong-Jian Lai presented the following open problem [2, problem 8.8]: Determine

\[L=\min\max\limits_{G\in SL-\{K_1\}}\{\frac{|E(H)|}{|E(G)|} : H \text{ is spanning eulerian subgroup of G}\}.\]

For a graph \(G\), \(O(G)\) denotes the set of all odd-degree vertices of \(G\). Let \(G\) be a simple graph and \(|O(G)| = 2k\). In this note, we show that if \(G\in{SL}\) and \(k \leq 2\), then \(L \geq \frac{2}{3}\).