A note on collapsible graphs and super-Eulerian graphs

A graph is called super-Eulerian if it has a spanning closed trail. Let G be a graph with n ≥ 4 vertices. Catlin in (1987) [3] proved that if d ( x ) + d ( y ) ≥ n for each edge x y ∈ E ( G ) , then G has a spanning trail except for several defined graphs. In this work we prove that if d ( x ) + d ( y ) ≥ n − 1 − p ( n ) for each edge x y ∈ E ( G ) , then G is collapsible except for several special graphs, which strengthens the result of Catlin’s, where p ( n ) = 0 for n even and p ( n ) = 1 for n odd. As corollaries, a characterization for graphs satisfying d ( x ) + d ( y ) ≥ n − 1 − p ( n ) for each edge x y ∈ 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).