The Chvátal–Erdős Condition for a Graph to Have a Spanning Trail

Chvátal and Erdős proved a well-known result that every graph G with connectivity κ(G) not less than its independence number α(G) is Hamiltonian. Han et al. (in Discret Math 310:2082–2090, 2003) showed that every 2-connected graph G with α(G)≤κ(G)+1 is supereulerian with some exceptional graphs. In this paper, we investigate the similar conditions and show that every 2-connected graph G with α(G)≤κ(G)+3 has a spanning trail. We also show that every connected graph G with α(G)≤κ(G)+2 has a spanning trail or G is the graph obtained from K_1,3 by replacing at most two vertices of degree 1 in K_1,3 with a complete graph or G is the graph obtained from K₃ by adding a pendent edge to each vertex of K₃. As a byproduct, we obtain that the line graph of a connected graph G with α(G)≤κ(G)+2 is traceable. These results are all best possible.