Four problems on graphs with excluded minors

The four problems the authors consider are the Chinese postman, odd cut, co-postman, and odd circuit problems. Seymour’s characterization of matroids having the max-flow min-cut property can be specialized to each of these four problems to show that the property holds whenever the graph has no certain excluded minor. They develop a framework for characterizing graphs not having these excluded minors and use the excluded minor characterizations to solve each of the four optimization problems. In this way, a constructive proof of Seymour’s theorem is given for these special cases. The authors also show how to solve the Chinese postman problem on graphs having no four-wheel minor, where the max-flow min-cut property need not hold.