Tag Archives: Petersen graph

A small fact about the Petersen graph

Posted on 02/05/2017 by

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 … Continue reading →

Posted in open problems | Tagged , , | 4 Comments

A puzzle for you

Posted on 09/04/2016 by

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 … Continue reading →

Posted in Uncategorized | Tagged , , | 7 Comments

Counting colourings of graphs

Posted on 12/04/2012 by

Every graph theorist knows that the colourings of a graph with a given number of colourings are counted by a certain polynomial, the chromatic polynomial of the graph. My purpose here is to point out that there is more to … Continue reading →

Posted in exposition, open problems | Tagged , , , | 1 Comment