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 |
Petersen graph. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Petersen_graph&oldid=49994