Supereulerian Planar Graphs

Hong-Jian Lai1, Deying Li2, Jingzhong Mao3, Mingquan Zhan4
1Department of Mathematics West Virginia University, Morgantown, WV 26506, USA
2School of Information Renmin University of China, Beijing 100872, P.R. China
3Department of Mathematics Central China Normal University, Wuhan, P. R. China
4Department of Mathematics Millersville University, Millersville, PA 17551, USA

Abstract

We investigate the supereulerian graph problems within planar graphs, and we prove that if a \(2\)-edge-connected planar graph \(G\) is at most three edges short of having two edge-disjoint spanning trees, then \(G\) is supereulerian except for a few classes of graphs. This is applied to show the existence of spanning Eulerian subgraphs in planar graphs with small edge cut conditions. We also determine several extremal bounds for planar graphs to be supereulerian.