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 K_6) by del -Y or Y-del transforms.
Here, the del -Y transform corresponds to replacing the three graph edges forming a triangle graph C_3 are by three graph edges and a new graph vertex that form a Y, and the del -Y transform to the reverse operation of this.
As illustrated above and enumerated in the following table, the Petersen family graphs include the Petersen graph P, complete tripartite graph K_(1,3,3), complete graph K_6, and complete bipartite graph minus edge K_(4,4)-e.
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.
See also
Apex Graph, Forbidden Minor, Generalized Petersen Graph, Intrinsically Linked Graph, Linklessly Embeddable Graph, Petersen Graph, Robertson's Apex GraphExplore 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.Barrett, W.; Hunnell, M.; Hutchens, J.; and Sinkovic, J. "The Classification of Graphs on 8 vertices with Coinciding Zero Forcing number and Maximum Nullity." 12 Jun 2025. https://arxiv.org/abs/2506.10726.House of Graphs. Petersen Family Graphs. Petersen Graph, Complement of the Fritsch Graph, 3-Petersen Family Graph, 3K1 + (K3 U K1), K3,3,1, K6, and K4,4 - e.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.Referenced on Wolfram|Alpha
Petersen Family GraphsCite this as:
Weisstein, Eric W. "Petersen Family Graphs." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/PetersenFamilyGraphs.html