A puzzle for you

The Petersen graph is perhaps the most famous graph of all. It has ten vertices, fifteen edges, valency 3, and no triangles. Since the complete graph on ten vertices has 45 edges and valency 9, one might ask whether the edge set of the complete graph can be partitioned into three copies of the Petersen graph (as Allen Schwenk did in 1983 in the American Mathematical Monthly). Four years later, he and Jack van Lint’s problem solving group O. P. Lossers in Eindhoven independently gave an elegant solution, which I described here.

Indeed, their argument shows more. It is possible to find two edge-disjoint copies of the Petersen graph in K10; the argument shows that the remaining 15 edges necessarily form a bipartite graph. Since the Petersen graph is definitely not bipartite, this settles the original question.

Another graph rather similar to the Petersen graph is the Clebsch graph, which has 16 vertices, 40 edges, valency 5, and no triangles. Indeed, there is a close relationship: the subgraph on the non-neighbours of a vertex in the Clebsch graph is the Petersen graph.

The Clebsch graph can be constructed by taking as vertex set a symbol *, the set {1,…,5}, and the set of ten 2-element subsets of {1,…5}. Join * to all of {1,…,5}; join points in this set to pairs containing them; and join two pairs if they are disjoint.

So here is a puzzle. The solution is here.

Suppose we delete the edges of two edge-disjoint Clebsch graphs from K16. What can we say about the graph formed by the remaining edges?

About Peter Cameron

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

7 Responses to A puzzle for you

  1. Gordon Royle says:

    The answer to this puzzle is rather nice, but what I’d really like to know is what happens if we remove (if possible) the edges of six edge-disjoint copies of the Hoffman-Singleton graph from $K_{50}$.

    Also, do you know how the “Clebsch graph” came to mean either (or both) the (16,5,0,2) strongly regular graph AND its complement. Bill Martin tells me that the first use of the name appears to be from Seidel who refers to the 10-regular graph based on Clebsch’s 16 lines, but in Beth, Jungnickel and Lenz “Design Theory”, they define and refer only to the 5-regular graph.

    • The eigenvalue methods won’t touch six Hoffman-Singletons, I fear.

      I admit my ignorance about what the “Clebsch graph” really is, and how it relates to the Clebsch quartic. Seidel was classifying the strongly regular graphs with smallest eigenvalue -2, so the valency-10 graph was the relevant one for him. (Unfortunately we can’t ask him now, but I will delve into his papers if I have time.) I suspect that almost anyone else who looked at it would regard the valency-5 graph as the more natural — it’s the folded 5-cube, etc. A good history project for someone?

      • Depending on one’s perspective, if the object of interest is the rank-3 permutation representation or the three-class association scheme, both the 5-regular and 10-regular graph give rise to the same object anyway….

  2. Tony Forbes says:

    Looking up my Graph Design records, I see that there exists a decomposition of the edges of K_16 into 3 Clebsch graphs.

    • Yes indeed, but that is not the issue. The question is: Given two edge-disjoint Clebsch graphs, what can you say about the third? [OK, it says that it might be another Clebsch, but can you say more?]

      • Tony Forbes says:

        This is indeed interesting. The third graph always has eigenvalues {5,-3,-3,-3,-3,-3,1,1,1,1,1,1,1,1,1,1}, and the Clebsch graph is the only graph with this spectrum (cf Wiki). Unfortunately the only proof I have at present is brute force. It is so simple to set the computer running, and it takes only a few minutes to try everything. I look forward to your proof. Meanwhile I shall ponder.

      • Gordon Royle says:

        Spectral methods will never say more than what the spectrum of the third graph is, so you’ll have to use the fact that the Clebsch graph is DS (determined by spectrum) at some stage.

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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.