On minimum degree conditions for supereulerian graphs
Hajo J. Broersma, Liming Xiong · University of Twente Research Information · 1999
A graph is called supereulerian if it has a spanning closed trail. Let $G$ be a 2-edge-connected graph of order $n$ such that each minimal edge cut $E \\subseteq E (G)$ with $|E| \\le 3$ satisfies the property that each component of $G-E$ has order at least $(n-2)/5$. We prove that either $G$ is supereulerian or $G$ belongs to one of two classes of exceptional graphs. Our results slightly improve earlier results of Catlin and Li. Furthermore our main result implies the following strengthening of a theorem of Lai within the class of graphs with minimum degree $\\delta\\ge 4$: If $G$ is a 2-edge-connected graph of order $n$ with $\\delta (G)\\ge 4$ such that for every edge $xy\\in E (G)$ , we have $\\max \\{d(x),d(y)\\} \\ge (n-7)/5$, then either $G$ is supereulerian or $G$ belongs to one of two classes of exceptional graphs. We show that the condition $\\delta(G)\\ge 4$ cannot be relaxed.