Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

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

3 Answers 3

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!

share|improve this answer
    
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.

share|improve this answer

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:

The graphs isomorphic to the Petersen graph; the last two share 6 edges.

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.