``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.

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).

**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.

© 1996-9

1999-05-26