7
$\begingroup$

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.

  • 0
    Thanks for posting this question!2012-05-14

3 Answers 3

7

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!

  • 0
    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](http://math.fau.edu/~npace/data/ivanicmag.pdf)*. (PDF) The Higman-Sims graph has 100 vertices and 1100 edges.2012-05-15
2

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.

2

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

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.