Can the Complete Graph on ten vertices be edge covered by three copies of the Petersen Graph? Put another way ... Colour the edges of the complete graph with 3 colours, so that three subgraphs are each a copy of the Petersen Graph.
I heard somewhere that it can be done (Maybe I should not go on MathOverFlow !) but I have spent all weekend trying and have convinced myself it is impossible. Thanks in advance for your comments.
 A: Section 1.5.1 in Spectra of Graphs by Brouwer and Haemers says that there is no such decomposition. (Downloadable PDF here)
I am not going to pretend to understand the proof, but it is at the very beginning of the book, so it might be possible to read just a little bit and understand what is going on.
I found this result cited in a couple of places as a surprising application of linear algebra to graph theory.
Addendum: Here's another, possibly more readable description of the same technique. (PDF)
Addendum: However, this page says that you can partition a double $K_{10}$ into six Petersen graphs!
A: A proof of impossibility is also given in Thirty-three Miniatures: Mathematical and Algorithmic Applications of Linear Algebra, specifically Minature 13, "Three Petersens are not enough".  I was able to view a substantial portion of this as a Google Books result.
A: This can be checked computationally.  Here is my GAP code:
F:=[[1,2],[2,3],[3,4],[4,5],[1,5],[6,8],[8,10],[7,10],[7,9],[6,9],[1,6],[2,7],[3,8],[4,9],[5,10]];

In the above, F is the edge set of the Petersen graph.
count:=0;
S:=[];
for alpha in SymmetricGroup(10) do
  F2:=OnSetsSets(F,alpha);
  count:=count+1;
  if(Intersection(F,F2)=[]) then
    S:=Concatenation(S,[F2]);
    Print(Size(S)," out of ",count," out of ",Factorial(10),"; expecting: ",1.0*Factorial(10)*Size(S)/count,"\n");
  fi;
od;

The above generates a list S of graphs isomorphic to the Petersen graph F which do not share an edge.
B:=[S[1],S[1]];
best:=Size(Intersection(B[1],B[2]));
for i in [1..Size(S)] do
  for j in [i+1..Size(S)] do
    F1:=S[i];
    F2:=S[j];
    int:=Size(Intersection(F1,F2));
    if(int<best) then
      best:=int;
      B:=[F1,F2];
      Print("Best thus far: ",best,"\n",B[1],"\n",B[2],"\n\n");
    fi;
  od;
od;

The above attempts to find two members of S, denoted F1 and F2, which are edge disjoint.  It doesn't find any.  The best it finds is the following:

Here the last two graphs share the 6 edges highlighted in bold.
