A small fact about the Petersen graph

The Petersen graph has 10 vertices and 15 edges, and the complete graph on 10 vertices has 45 edges. However, Allen Schwenk and (independently) O. P. Lossers (Jack van Lint’s problem-solving seminar in Eindhoven) showed that you can’t partition the edges of the complete graph into three Petersen graphs; you can pack two Petersen graphs edge-disjointly, but not three.

I described this here, and went on to explain how Sebi Cioaba and I showed that for any m ≥ 2 it is possible to cover the edges of the complete graph m times with 3m Petersens. In particular, you can cover the edges twice with six Petersen graphs.

This means that five Petersen graphs suffice to cover the edges of the complete graph, since we may omit one of the six. We cannot, however, omit two, since any two have edges in common.

So the minimum number of Petersen graphs required to cover all the edges is either 4 or 5.

In fact it is 4. If you apply four random permutations to the vertices of the Petersen graph you will quickly come up with a way of covering all edges.

But is there a nice way to see this? In particular, is it possible to arrange four Petersen graphs so that they cover each edge once or twice (so that deleting a complete graph leaves a trivalent simple graph remaining)? If so, what is this graph? If not, why not?

Advertisements

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in open problems and tagged , , . Bookmark the permalink.

4 Responses to A small fact about the Petersen graph

  1. Here is (hopefully) an answer to your question of if you can cover each edge once or twice:

    gap> perms := [ (), (1,3,5)(2,10,6,4,9), (1,7)(2,9,8,4,6,10)(3,5), (1,9,7,10)(2,6,8,4,5,3) ];;

    gap> peterson := [ [1,2],[2,3],[3,4],[4,5],[1,5], [6,7],[7,8],[8,9],[9,10],[6,10], [1,6],[2,7],[3,8],[4,9],[5,10]];;

    gap> images := List(perms, x -> OnSetsSets(peterson, x));;

    gap> List(Combinations([1..10], 2), edge -> Length(Filtered(images, x -> edge in x)));
    [ 1, 2, 1, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 2, 2, 1, 2, 2, 1, 1 ]

  2. Wrong graph! Let me try with the right one…

    • gap> peterson := [ [1,2],[2,3],[3,4],[4,5],[1,5], [6,8],[7,9],[8,10],[6,9],[7,10], [1,6],[2,7],[3,8],[4,9],[5,10]];;

      gap> perms := [ (), (1,7,6,5,3,2,10)(4,9,8), (1,7,10,9,4,8,5)(2,6,3), (1,7,3,2,8,5,4,9,10,6)];;

      gap> images := List(perms, x -> OnSetsSets(peterson, x));;

      gap> List(Combinations([1..10], 2), edge -> Length(Filtered(images, x -> edge in x)));
      [ 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 2, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 2, 1, 1, 2 ]

  3. Thanks Chris. I probably won’t have time to look at it today…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s