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
    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 Herman2012-05-15
  • 0
    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.2012-05-15
  • 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.