There is a lovely algebraic argument to prove that the complete graph on ten vertices (which has 45 edges) cannot be partitioned into three copies of the Petersen graph (which has 15 edges). Sebastian Cioaba asked me: for which m is it possible to partition the edges of the m-fold K10 into 3m copies of the Petersen graph? We had fun showing that this holds for every positive integer m except m = 1. It may well be that this is already known, but I am old enough not to mind.
The case m = 1
I am not sure who first thought of this gem.
Suppose that we had a partition of K10 into three graphs Gi, for i = 1,2,3. Suppose that G1 and G2 are Petersen graphs. What can we learn about G3?
Let Ai be the adjacency matrix of Gi. They satisfy I+A1+A2+A3 = J, the all-1 matrix.
The Petersen graph has eigenvalues 3, 1, −2, with multiplicities 1, 5, 4 respectively; the 1-dimensional eigenspace is spanned by the all-1 vector. Now the 5-dimensional eigenspaces for A1 and A2 lie inside the 9-dimensional space orthogonal to the all-1 vector; so they have non-zero intersection. Let v be a vector in this intersection. Then A1v = A2v = v. Since Jv = 0, we have A3v = −3v. Now a graph of valency 3 with an eigenvalue −3 is necessarily bipartite; certainly not isomorphic to the Petersen graph.
The case m = 2
No work is required in this case; the groups do it for us!
The automorphism group of the Petersen graph is the symmetric group S5, acting on 10 points. It is a subgroup of index 6 in S6, also acting on 10 points; so there are six images of the Petersen graph under S6. Since this group is doubly transitive, each pair of vertices is covered the same number of times by edges of the six Petersen graphs, necessarily twice.
The case m = 3
This case requires a little work. We take a permutation of order 9 on the ten vertices, fixing one point ∞ and permuting the others as (0,1,2,3,4,5,6,7,8). The Petersen graph has three edges from ∞ to the other points; clearly the nine images will cover each pair {∞,x} three times.
We need to draw the Petersen graph minus a vertex on the other nine points so that each of the four distances in the cycle is realised by three edges; then the nine images will cover each edge three times. I couldn’t do this by hand, but the computer only took a moment to find dozens of solutions. One of them has edges {∞,1}, {∞,4}, {∞,8}, {0,2}, {0,3}, {0,4}, {1,3}, {1,5}, {2,5}, {2,8}, {3,7}, {4,6}, {5,6}, {6,7}, {7,8}.
The general case
Every positive integer m > 1 can be written as a sum of 2s and 3s. Now any such representation tells us how to decompose mK10 into 3m Petersens.
Other graphs
K16 can be partitioned into three Clebsch graphs. This uses the fact that, in the finite field GF(16), the fifth power of any non-zero element lies in the subfield GF(4). Now partition the pairs {a,b} according to the value of (a−b)5. This was first done by Greenwood and Gleason in the context of Ramsey theory; we have coloured the edges of K16 with three colours without creating a monochromatic triangle (and 16 is the largest number for which this can be done).
What about other cases? Sebastian suggests partitioning mK55 into 3m copies of the triangular graph T(11) (the line graph of K11).
Peter Cameron's Blog 
Dear Peter,
Thank you for mentioning these problems on your blog and for the beautiful exposition. I have some historical comments.
The problem of partitioning the edge-set of the complete graph on 10 vertices into 3 copies of the Petersen graph was proposed by Allen Schwenk as Problem 6434 in American Math Monthly 90, No.6. in 1983 and its solution by Schwenk and O.P. Lossers appeared in American Math Monthly 94, 885-886 in 1987. This result is described many books on algebraic graph theory including the one by Chris Godsil and Gordon Royle and the recent book by Andries Brouwer and Willem Haemers and I use it to attract students to algebraic graph theory.
An interesting open problem is whether one can decompose the complete graph on 50 vertices into 7 copies of the Hoffman-Singleton graph. Siagiova and Meszka (J. Combin.Des. 11 (2003), 408-412) used voltage coverings to pack 5 edge-disjoint copies of the Hoffman-Singleton graph.
The more general problem of partitioning a complete graph on v vertices into 3 edge-disjoint copies of a given strongly regular graph on v vertices is Exercise 9.7 in Brouwer-Haemers book and is due to Peter Rowlinson, Certain 3-decompositions of complete graphs, with an application to finite fields, Proc. Roy. Soc. Edinburgh Sect. A 99 (1985), no. 3-4, 277–281.
Interestingly enough, the review on AMS Mathscinet of Rowlinson’s paper is written by Jack van Lint and makes references to a paper of van Lint and Schrijver constructing some beautiful strongly regular graphs and to the Greenwood and Gleason construction showing the Ramsey number R(3,3,3)=17.
For any graph G, we can trivially partition some multiple of the complete graph into copies of G: simply take all images under the symmetric group. So for given G we could ask: what is the smallest number of copies we need? Which multiples of the complete graph can be partitioned into copies of G? There might be a general theory lurking here.
Thanks for your comment, and for the references.
It’s maybe worth pointing out that O. P. Lossers was the pen name of Jack van Lint’s problelm solving group in Eindhoven. (“oplossers” is Dutch for “solvers”.) I sat in on a couple of their meetings in the 1970s. Sometimes real papers grew out of their deliberations – it may be that the van Lint-Schrijver paper was one of those.
By the way, it is impossible to find even two disjoint T(11)s inside K55. T(11) has cliques of size 10, but the largest clique in its complement has size only 5.
Several questions to the non-expert immediately come to mind.
1. What is meant by the “$m$-fold $K_{10}$”?
2. Surely one the case of decomposing $K_{10}$ into three Petersens is settled, the next natural case to consider is the question of decomposing $K_{16}$ in five Petersens, or is the analogous argument obviously similar to the $K_{10}$ case or is the famously well known or what?
3. Another infinite family of cases where decomposition into strongly regular graphs seems plausible is the decomposition of $K_{n^2}$ when $n$ is odd into $\frac{n+1}{2}$ copies of the $n\times n$ rook graph (this is just the name Wikipedia seems to favour: I simply mean the graph defined by arranging the vertices in an $n\times n$ grid and adjoining vertices if and only if they lie in the same row or column). Note these are strongly regular. The $n=1$ case is obvious and the n=3 case is easily settled since the $3\times3$ rook graph is isomorphic to its complement. The case $n=5$ is simply the a special case of the aforementioned Rowlinson paper. I have no idea about the $n=7$ case. Clique number considerations do not appear to rule anything out. I get the feeling this is the sort of thing that’s well known to latin squares people, but I know even less about those than I do about graphs. Any ideas?
My apologies if this is all in the Brouwer and Haemers book – I’ve been having a little trouble getting hold of a copy.
Sorry if I wasn’t very clear.
By m-fold complete graph, I just mean that you cover every edge of the complete graph m times. (You can think of taking the complete graph, replacing every edge by m parallel edges, and then decomposing the resulting edge set into copies of your target graph.)
K16 has 120 edges, so you would need 8 copies of Petersen to partition its edge set. I have stuck mainly to the case where the graph into which you are partitioning uses all the vertices, but the complementary case is very interesting too.
If n is odd, then the complete graph on n2 vertices can be decomposed into copies of the rook graph if and only if there exists an affine plane of order n. (Simply take the parallel classes two at a time.) If n is even, the best you could do would be to cover each edge twice; you can certainly do this if there is an affine plane, but I don’t know whether the converse is true.
So the Shrikhande graph is the smallest strongly regular graph for which I don’t know the answer.
Why is it that things like seeing when a question is obviously stupid is something that never happens until *after* you hit the “post comment” button – my apologies for question 2! I suspect I mean a decomposition into eight edge-disjoint Petersens, with each vertex meeting just five of them.
There is another strategy. There are people (some of whom describe themselves as “lurkers” who email me their comments rather than post them publicly.
I said that I thought someone probably did this before, and indeed they did:
Peter Adams, Darryn E. Bryant and A. Khodkar, The spectrum problem for lambda-fold Petersen graph designs, Journal of Combinatorial Mathematics and Combinatorial Computing 34 (2000), 159-176. The result is much more general, and answers Ben’s question as well.
The same nice proof works to show that if we pack two disjoint (16,6,2,2) strongly regular graphs $G_1$, $G_2$ in $K_{16}$ then the rest is $K_4+K_4+K_4+K_4$ (each of $G_1$, $G_2$ can be the Shrikhande graph or $K_4\times K_4$, and there are 4 non-isomorphic cases).