Degree-Splittability of Multigraphs and Caterpillars

摘要

A multigraph is degree-splittable if it decomposes into two sub-multigraphs whose degree lists are the same, plus one leftover edge when the total number of edges is odd. We prove that a connected multigraph is degree-splittable if each odd number appears in its degree list an even number of times. For caterpillars, we characterize the splittable caterpillars with diameter at most 4, provide a general sufficient condition for splittability of caterpillars, and prove that the smallest maximum degree of a non-splittable caterpillar is 5.