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

-
Thanks for posting this question! – MJD May 14 '12 at 15:38

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.

-
Thanks for putting me out of my misery ! so the answer is negative, confirming my convoluted arguement (that only exists in my mind) is probably correct. Ive just heard that K16 can covered by 3 copies of the Clebsch Graph! Mark: 6 copies of P10 will do 2 copies of K10 will it ? Kindest Regards Herman – Herman May 15 '12 at 15:25
Not exactly. A "double $K_{10}$" is not two disjoint copies of $K_{10}$, which would have 20 vertices and 90 edges. Rather, it is the graph you get by taking $K_{10}$ and replacing each single edge with two edges; it has 10 vertices and 90 edges. This "double" graph can be decomposed into six Petersen graphs. Two disjoint $K_{10}$s clearly can't, since that would imply a decomposition of either component separately. – MJD May 15 '12 at 15:40
You're welcome! Don't forget to "accept" one of the answers. You may also be interested to see Decomposing the Higman-Sims graph into double Petersen graphs. (PDF) The Higman-Sims graph has 100 vertices and 1100 edges. – MJD May 15 '12 at 15:41

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.

-

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.

-