Characterizations of Postman Sets

Abstract

Using results by McKee and Woodall on binary matroids, we prove that the set of postman sets has odd cardinality, generalizing a result by Toida on the cardinality of cycles in Eulerian graphs. We study the relationship between T-joins and blocks of the underlying graph, obtaining a decom- position of postman sets in terms of blocks. We conclude by giving several characterizations of T-joins which are postman sets and commenting on practical issues.