Contractions of graphs with no spanning Eulerian subgraphs (Q1112064)

The concept of collapsible graphs introduced by the author in J. Graph Theory 12, 29-44 (1988), is here used to study the existence of spanning Eulerian subgraphs. The following result is given: Let \(p\geq 2\) be a fixed integer, and let G be a connected graph of order n. If \(d(u)+d(v)>2n/p-2\) holds whenever uv\(\not\in E(G)\), and if n is sufficiently large compared to p, then either G has a spanning Eulerian subgraph, or G is contractible to a graph G' of order less than p and with no spanning Eulerian subgraph. The case \(p=2\) was proved by \textit{L. Lesniak-Foster} and \textit{J. E. Williamson} [Can. Math. Bull. 20, 215-220 (1977; Zbl 0357.05060)]. The case \(p=5\) was conjectured by \textit{A. Benhocine, L. Clark, N. Köhler} and \textit{H. J. Veldman} [J. Graph Theory 10, 411-425 (1986; Zbl 0608.05056)] when they proved vitually the case \(p=3\).