Prologue

(In The Elusive Pimpernel by the Baroness Orczy)

Like the Scarlet Pimpernel the Petersen graph turns up all over the place and often unexpectedly. This chapter is a by no means all-inclusive list of some of these venues. There are exactly 19 connected cubic graphs on 10 vertices. The number of elements in the set, C(n), of connected cubic graphs on n vertices grows rapidly with n; for example |C(20)| = 510489, |C(30)| = 845480228069. The Petersen graph is the only graph in C(10) with 120 automorphisms; the only graph in C(10) with girth 5; the only graph in C(10) with diameter 2; the only bridgeless graph in C(10) with chromatic index 4 and finally it is the only bridgeless non-hamiltonian graph in C(10). These many ways in which P is unique within C(10), are also reflected in the unique role that P plays within the theory of graphs. We now show some other sides to Petersen's character, and hope our discussions will not only support our central theme but also expose the reader to some other interesting areas of graph theory. This chapter makes no claim to being exhaustive. Its only claim is to enforce the well known caveat: graph theorists should always consider P and its generalizations before making conjectures.

The ubiquitous nature of the Petersen graph is further pursued in [C–W 85], [C–H–W92].