A reduction method to find spanning Eulerian subgraphs 论文

摘要

Abstract We ask, When does a graph G have a subgraph Γ such that the vertices of odd degree in Γ form a specified set S ⊆ V ( G ), such that G ‐ E (Γ) is connected? If such a subgraph can be found for a suitable choice of S , then this can be applied to problems such as finding a spanning eulerian subgraph of G . We provide a general method, with applications.