TOPICS

# Petersen Family Graphs

The Petersen family of graphs, not to be confused with generalized Petersen graphs, are a set of seven graphs obtained from the Petersen graph (or complete graph ) by - or - transforms.

Here, the - transform corresponds to replacing the three graph edges forming a triangle graph are by three graph edges and a new graph vertex that form a , and the - transform to the reverse operation of this.

As illustrated above and enumerated in the following table, the Petersen family graphs include the Petersen graph , complete tripartite graph , complete graph , and complete bipartite graph minus edge .

 index vertex count graph 1 10 Petersen graph 2 9 Petersen family graph 3 8 Petersen family graph 4 7 Petersen family graph 5 7 complete tripartite graph 6 6 complete graph 7 8 complete bipartite graph minus edge

Sachs (1983) showed that the seven graphs of the Petersen family are intrinsically linked, i.e., no matter how they are embedded in space, they have cycles that are linked to each other. He also suggested characterization of these graphs via forbidden subgraphs. Robertson et al. (1993) resolved this question by establishing that intrinsically linked graphs are characterized by having a member of the Petersen family as a graph minor.

In addition, the Petersen family graphs are among the forbidden minors of apex graphs.

Apex Graph, Forbidden Minor, Generalized Petersen Graph, Intrinsically Linked Graph, Linklessly Embeddable Graph, Petersen Graph, Robertson's Apex Graph

## Explore with Wolfram|Alpha

More things to try:

## 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.Sachs, H. "On a Spatial Analogue of Kuratowski's Theorem on Planar Graphs--An Open Problem". In Graph Theory: Proceedings of a Conference held in Łagòw, Poland, February 10-13, 1981 (Ed. M. Horowiecki, J. W. Kennedy, and M. M. Sysło). New York: Springer-Verlag, pp. 230-241, 1983.

## Cite this as:

Weisstein, Eric W. "Petersen Family Graphs." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/PetersenFamilyGraphs.html