4
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .