A note on collapsible graphs and super-Eulerian graphs

A graph is called super-Eulerian if it has a spanning closed trail. Let GG be a graph with n≥4n≥4 vertices. Catlin in (1987) [3] proved that if d(x)+d(y)≥nd(x)+d(y)≥n for each edge xy∈E(G)xy∈E(G), then GG has a spanning trail except for several defined graphs. In this work we prove that if d(x)+d(y)≥n−1−p(n)d(x)+d(y)≥n−1−p(n) for each edge xy∈E(G)xy∈E(G), then GG is collapsible except for several special graphs, which strengthens the result of Catlin’s, where p(n)=0p(n)=0 for nn even and p(n)=1p(n)=1 for nn odd. As corollaries, a characterization for graphs satisfying d(x)+d(y)≥n−1−p(n)d(x)+d(y)≥n−1−p(n) for each edge xy∈E(G)xy∈E(G) to be super-Eulerian is obtained; by using a theorem of Harary and Nash-Williams, the works here also imply the previous results in [2] by Brualdi and Shanny (1981), and in [6] by Clark (1984).