Petersen Graphs

$\begin{figure}\begin{center}\BoxedEPSF{Petersen_graph.epsf}\end{center}\end{figure}$

``The'' Petersen graph is the Graph illustrated above possessing ten Vertices all of whose nodes have Degree 3 (Saaty and Kainen 1986). The Petersen graph is the only smallest-girth graph which has no Tait coloring.

$\begin{figure}\begin{center}\BoxedEPSF{PetersenGraphs.epsf scaled 1000}\end{center}\end{figure}$

The seven graphs obtainable from the Complete Graph by repeated triangle-Y exchanges are also called Petersen graphs, where the three Edges forming the Triangle are replaced by three Edges and a new Vertex that form a Y, and the reverse operation is also permitted. A Graph is intrinsically linked Iff it contains one of the seven Petersen graphs (Robertson et al. 1993).

See also Hoffman-Singleton Graph

References

Adams, C. C. The Knot Book: An Elementary Introduction to the Mathematical Theory of Knots. New York: W. H. Freeman, pp. 221-222, 1994.

Robertson, N.; Seymour, P. D.; and Thomas, R. ``Linkless Embeddings of Graphs in 3-Space.'' Bull. Amer. Math. Soc. 28, 84-89, 1993.

Saaty, T. L. and Kainen, P. C. The Four-Color Problem: Assaults and Conquest. New York: Dover, p. 102, 1986.