Eulerian subgraphs in 3‐edge‐connected graphs and Hamiltonian line graphs

Abstract

Abstract In this paper, we show that if G is a 3‐edge‐connected graph with $S \subseteq V(G)$ and $|S| \le 12$ , then either G has an Eulerian subgraph H such that $S \subseteq V(H)$ , or G can be contracted to the Petersen graph in such a way that the preimage of each vertex of the Petersen graph contains at least one vertex in S . If G is a 3‐edge‐connected planar graph, then for any $|S|\le 23$ , G has an Eulerian subgraph H such that $S\subseteq V(H)$ . As an application, we obtain a new result on Hamiltonian line graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 308–319, 2003