Path decompositions of multigraphs

Let G be a loopless finite multigraph. For each vertex x of G , denote its degree and multiplicity by d ( x ) and μ( x ) respectively. Define Ø( x ) = the least even integer ≥ μ( x ), if d ( x ) is even, the least odd integer ≥ μ( x ), if d ( x ) is odd. In this paper it is shown that every multigraph G admits a faithful path decomposition —a partition P of the edges of G into simple paths such that every vertex x of G is an end of exactly Ø( x ) paths in P. This result generalizes Lovász's path decomposition theorem, Li's perfect path double cover theorem (conjectured by Bondy), and a result of Fan concerning path covers of weighted graphs. It also implies an upper bound on the number of paths in a minimum path decomposition of a multigraph, which motivates a generalization of Gallai's path decomposition conjecture. © 1995 John Wiley & Sons, Inc.