For a graph G , let O ( G ) denote the set of odd degree vertices of G . A graph G is collapsible if for any subset R ? V ( G ) with | R | ? 0 (mod 2), G has a spanning connected subgraph H R such that O ( H R ) = R . The reduction of G is the graph obtained from G by contracting all maximally collapsible subgraphs until no collapsible subgraph is left. Let G be a graph on n ? 8 vertices. In this paper, we prove that if d ( x ) + d ( y ) ? n - 2 - p ( n ) for each x y ? E ( G ) , then G is collapsible or G is one of 43 special graphs or the reduction of G is K 1 , t where t ? 2 or G is a class of well-characterized graphs, where p ( n ) = 0 for n even and p ( n ) = 1 for n odd, which generalizes the earlier results by Catlin (1987), and by Li and Yang (2012).
['Xiangwen Li', 'Yan Xiong']
Collapsible graphs and Hamilton cycles of line graphs