Dengxin Li

A graph $G$ is supereulerian if $G$ has a spanning eulerian subgraph. We use 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=minmax_{G\in SL-K_{1}}\{\frac{|E(H)|}{|E(G)|}\colon$ H is a spanning eulerian subgraph in 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 3$, then $L\geq 2/3$. By the example in [3], the condition $k\leq 3$ cannot be relaxed. Thus, if considering $|O(G)|$ of a graph only, for the problem we have the following result.
Let $G$ be a supereulerian graph, and $O(G)$ denote the set of all vertices of $G$ with odd degrees. Let $|O(G)| = 2k$. Each of the following holds. (i) If $k\leq 3$ and $G$ is a simple graph, then $L\geq 2/3$. (ii) If $k\geq 4$ and $G$ is a simple graph, then $L\leq 3/5$. (iii) If we allow $G$ to have multiple edges, then $L\leq 1/2$.
It is well known that if $G$ has two edge-disjoint spanning trees, then $G$ is supereulerian graph [4]. We present the following conjecture to conclude this article.
Conjecture. Let $G$ be a simple graph. If $G$ has two edge-disjoint spanning trees, then $L\leq 3/5$.