A note on graphs spanned by Eulerian graphs
William R. Pulleyblank · Journal of Graph Theory · 1979
Abstract We show that the problem raised by Boesch, Suffel, and Tindell of determining whether or not a graph is spanned by an Eulerian subgraph is NP‐complete. We also note that there does exist a good algorithm for determining if a graph is spanned by a subgraph having positive even degree at every node.