Supereulerianity Of3-edge-connected Essentially5-edge-connected Graphs

A trail that traverses every edge of a graph is called an Euler trail. A graph is Eulerian if it admits an closed Euler trail. A graph is supereulerian if it has a spanning eulerian subgraph.Two conjectures are about this issue:one is Chen and Lai [4] propose that every3-edge-connected, essentially5-edge-connected graph is supereulerian in1995;the other is that Lai [6] put forward that every3-edge-connected, essentially5-edge-connected graph is supereulerian. In this paper, we firstly show that let G be a graph with minimum degree δ≥3and σ(G)≥8, then|E(G)|≥2|V(G)|. Then we prove that if G be a3-edge-connected, essentially5-edge-connected graph if σ(G)≥8, then G is supereulerian.Following we show exactly how the idea forms. First part:Through the the-orem of Yang [11], we can draw the conclusion under the conditions of δ≥3and σ(G)≥8, only guaranteeing the3-vertex is connected with the vertex of degree more6, then the inequality|E(G)|≥2|V(G)|is proved. Keeping the balance of|E(G)|and|V(G)|, we need to delete the5-vertex which is adjacent to3-vertex, such that3-vertex is connected with the vertex of degree more6and doesn’t change the degree of other vertices. The number of3-vertices can’t be changed. We can analyze the problem from the opposite side, the5-vertex is connected with five3-vertex at most. Second part:Through the theorem of Nash-Williams [8] and Tutte [10], what we need is to prove|S|≥2(ω>(G-S)-1)=2(ω-1). The components of G-S is classified into different categories for some purpose, then contract all the compo-nents to get graph G’. such that it satisfies|S|=|E(G’)|and ω(G-S)=|V(G’)|in G’. Finally, under the conclusion of first part, we prove that G be a3-edge-connected, essentially5-edge-connected graph if σ(G)≥8, then G is supereulerian.This paper is not only the promotion of Yang [11], but also meet nearly the conjecture of Chen an Lai [4] in1995.