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.
Can the Complete Graph on ten vertices be edge covered by three copies of the Petersen Graph?
-
0Thanks for posting this question! – 2012-05-14
3 Answers
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!
-
0You'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
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
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.