On graphs which can or cannot induce Chinese Postman games with a non-empty core

We study the Chinese postman (CP) cooperative game induced by a connected, weighted, undirected graph GG, wherein players reside at the edges of GG and a postman, starting from a post-office location (i.e., a vertex of GG), needs to traverse all edges before returning to the post-office. We provide a complete characterization of all connected graphs for which there exists a positive edge-cost function such that the induced CP game has a non-empty core, and, consequently, we derive a complete characterization of all connected graphs for which there does not exist a positive edge-cost function which induces a CP game with a non-empty core. Membership in these classes of graphs can be verified in strongly polynomial time.