Sharp bounds for the Chinese Postman Problem in 3-regular graphs and multigraphs
The Chinese Postman Problem in a multigraph is the problem of finding a shortest closed walk traversing all the edges. In a (2r+1) ( 2 r + 1 ) -regular multigraph, the problem is equivalent to finding a smallest spanning subgraph in which all vertices have odd degree. In 1994, Kostochka and Tulai established a sharp upper bound for the solution. In this paper, we give simple proofs of their bounds for 3-regular graphs and 3-regular multigraphs and characterize when equality holds in those cases. We conjecture that a more specific construction characterizes equality for r?2 r ? 2 .
chinese postman problem regular graph parity subgraph balloon