Spanning 2‐trails from degree sum conditions

Suppose G is a simple connected n‐vertex graph. Let σ₃(G) denote the minimum degree sum of three independent vertices in G (which is ∞ if G has no set of three independent vertices). A 2‐trail is a trail that uses every vertex at most twice. Spanning 2‐trails generalize hamilton paths and cycles. We prove three main results. First, if σ₃G)≥ n ‐ 1, then G has a spanning 2‐trail, unless G ? K_1,3. Second, if σ₃(G) ≥ n, then G has either a hamilton path or a closed spanning 2‐trail. Third, if G is 2‐edge‐connected and σ₃(G) ≥ n, then G has a closed spanning 2‐trail, unless G ? K_2,3 or K (the 6‐vertex graph obtained from K_2,3 by subdividing one edge). All three results are sharp. These results are related to the study of connected and 2‐edge‐connected factors, spanning k‐walks, even factors, and supereulerian graphs. In particular, a closed spanning 2‐trail may be regarded as a connected (and 2‐edge‐connected) even [2,4]‐factor. © 2004 Wiley Periodicals, Inc. J Graph Theory 45: 298–319, 2004