Factorization of regular multigraphs into regular graphs

A regular multigraph with maximum multiplicity r and degree rs cannot always be factored into r s-regular simple graphs. It is shown, however, that under general conditions a similar factorization can be achieved if we first allow the addition or deletion of a relatively small number of hamilton cycles. Based on this result, we give extensions of some known factorization results on simple graphs to new results on multigraphs. © 1995 John Wiley & Sons, Inc.