# Is every graph an isomorphic factor of some complete graph?

Q1: For any given finite simple graph G with e edges, does there always exist an $n$ such that the edges of $K_n$ can be partitioned into $\frac{\binom{n}{2}}{e}$ edge-disjoint copies of $G$? If so, can any upper bounds be placed on the minimal required $n$?

Q2: Similarly for digraphs (with twice as many copies)?

Q3: For any loopless multidigraph with maximum edge multiplicity $m$, it seems clear that for some $M>m$, an $M$-complete multidigraph can be exactly partitioned into isomorphic copies of it, even without increasing $n$: if nothing smaller, one can always overlay $n!$ copies of the original multidigraph with each permutation of the vertices. Can this partition always be accomplished with $M=m$, increasing $n$ instead? If not, can tighter bounds be placed on $M$?

Q4: Does allowing loops (and adjusting edge-counts appropriately) fundamentally change any of the above?

• Dear @Andy Juell: I edited the question slightly; the "more of a 1a+2a+3a, really:" seemed to make no sense (perhaps it meant something like 'Q1,Q2,Q3 again, but for arbitrary multigraphs'). Needless to say, you can re-edit. I also added a condition of 'loopless' in Q3, because otherwise Q4 does not make sense. Apr 4, 2018 at 7:11
• @PeterHeinig: I had meant to admit that the contents of Q4 might have been presented after each previous question (i.e. Q1a: with loops? , Q2a: with loops?) but imagined this to be less redundant. Sorry for the confusion... Apr 4, 2018 at 10:45

## 1 Answer

Q1: yes, this is a theorem by Wilson; see the first paragraph here: https://arxiv.org/abs/1604.07282

Edit: perhaps the book Decomposition of graphs by J. Bosak might be helpful (the preview on google books is quite limited).

• Thanks for the lead...may be a while before I can track down the original reference, but indications are that Wilson settled Q2 in the affirmative also. (alastairfarrugia.net/sc-graph/sc-graph-survey.pdf p. 160) Apr 4, 2018 at 1:39
• It is perhaps worth pointing out that for a complete answer to Q1 one has to provide at least one $n$ for which $e$ divides $\binom{n}{2}$; obviously, $n=e$ works. Smaller $n$ sometimes work (e.g. if $e=6$, then $n=4$ also ensures that $e$ divides $\binom{n}{2}$). However, since Wilson's theorem involves a 'sufficiently large $n$'-clause, I expect that for most given $G$, one needs a much larger $n$ than $e$, though I haven't found a reference for this. Apr 4, 2018 at 7:11
• (In my comment at 2018-04-04 07:11:41Z I made a mistake, or rather, I omitted a case: obviously, if $n$ is odd, then $n$ divides $\binom{n}{2}$, but if $n$ is even then it doesn't. So what I should have said is "obviously, if $e$ is odd, then $n=e$ works, while if $e$ is even, then $n=e+1$ works." Apr 5, 2018 at 12:23
• @PeterHeinig Suppose that $2^k$ is the largest power of 2 that divides $e$ and $k \ge 1$. Then the largest power of 2 that divides $\binom{e+1}{2} = (e+1)\frac{e}{2}$ is $2^{k-1}$, since this is the largest power of 2 that divides $\frac{e}{2}$ and $e+1$ is odd. This mean that $e$ does not divide $\binom{e+1}{2}$, and the same reasoning works for $\binom{e}{2}$. I think you need to use $\binom{2e}{2}$. Apr 12, 2018 at 7:45