Petersen graph

A graph that has fascinated graph theorists over the years because of its appearance as a counterexample in so many areas of the subject:

Figure: p120110a

The Petersen graph is cubic, -connected and has vertices and edges. There are exactly connected cubic graphs on vertices. The number of elements in the set of connected cubic graphs on vertices grows rapidly with ; for example, , . The Petersen graph is the only graph in with automorphisms (cf. also Graph automorphism); the only graph in with girth ; the only graph in with diameter ; the only bridgeless graph in with chromatic index (cf. also Graph colouring) and, finally, it is the only bridgeless non-Hamiltonian graph in C.

Typically, however, the importance of the Petersen graph is the way it features as the exceptional graph. It is at least arguable that the development of graph theory was in large extent due to the interest in the four-colour problem. P.G. Tait [a2] showed that every planar graph is -face colourable if and only if every bridgeless cubic planar graph is -edge colourable, that is, if its chromatic index is at most . W.T. Tutte [a3] conjectured that if is a bridgeless cubic graph with chromatic index at least , then is subcontractible to the Petersen graph. Thus, even with the proof of the four-colour theorem there is much to prove beyond the theorem [a4] and typically the Petersen graph features prominently. In the same vein, W.T. Tutte [a3] conjectured that if is a bridgeless graph which does not support a nowhere-zero -flow, then is subcontractible to the Petersen graph: the four-colour theorem guarantees that every bridgeless planar graph supports a nowhere-zero -flow. Let be any orientation of the edges of . A nowhere-zero -flow on a graph is a mapping such that at each vertex , , where the summation is over all oriented edges incident with .

References

[a1]	D. Holton, J. Sheehan, "The Petersen graph" Austral. Math. Soc. Lecture Ser., CLT , 7 (1993)
[a2]	P.G. Tait, "Remarks on the colouring of maps" Proc. R. Soc. Edinburgh , 10 (1878-80) pp. 729
[a3]	W.T. Tutte, "On the algebraic theory of graph colourings" J. Combin. Th. , 1 (1966) pp. 15–50
[a4]	W.T. Tutte, "Colouring problems" Math. Intelligencer , 1 (1978) pp. 72–75