Balancing out edge multiplicites in a graph

Let G be a multigraph with maximum edge multiplicity t and minimum edge multiplicity 1 (so that there is at least one ‘ordinary’ edge).

Is there some simple graph H such that the t-fold multigraph H(t) edge-decomposes into copies of G?

I believe that Wilson’s theory (under certain hypotheses) gives a solution when H is a certain very large complete graph. For instance, see Draganova, Mutoh, Wilson (2008). Heavy machinery gets used there.

Is there a more direct argument if I don’t care what H is or how large it is?


Let G be an arbitrary graph with 4 edges, with multiplicities 1,2,2,3. Then in any decomposition of an H(3) every triple edge would have to split as {3} or {1,2}. In particular, there would be equal numbers of G-edges of multiplicities 1 and 2, which isn’t the case for any union of copies of G.

Source : Link , Question Author : Peter Dukes , Answer Author : Ben Barber

Leave a Comment