Characterizations of postman sets Original Research Article

Using results by McKee and Woodall on binary matroids, we show 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 image-joins and blocks of the underlying graph, obtaining a decomposition of postman sets in terms of blocks. We conclude by giving several characterizations of image-joins which are postman sets.