Petersen family
In graph theory, the Petersen family is a set of seven undirected graphs that includes the Petersen graph and the complete graph K6. The Petersen family is named after Danish mathematician Julius Petersen, the namesake of the Petersen graph.
Any of the graphs in the Petersen family can be transformed into any other graph in the family by Δ-Y or Y-Δ transforms, operations in which a triangle is replaced by a degree-three vertex or vice versa. These seven graphs form the forbidden minors for linklessly embeddable graphs, graphs that can be embedded into three-dimensional space in such a way that no two cycles in the graph are linked. They are also among the forbidden minors for the YΔY-reducible graphs.
The form of Δ-Y and Y-Δ transforms used to define the Petersen family is as follows:
These transformations are so called because of the Δ shape of a triangle in a graph and the Y shape of a degree-three vertex. Although these operations can in principle lead to multigraphs, that does not happen within the Petersen family. Because these operations preserve the number of edges in a graph, there are only finitely many graphs or multigraphs that can be formed from a single starting graph G by combinations of Δ-Y and Y-Δ transforms.
The Petersen family then consists of every graph that can be reached from the Petersen graph by a combination of Δ-Y and Y-Δ transforms. There are seven graphs in the family, including the complete graph K6 on six vertices, the eight-vertex graph formed by removing a single edge from the complete bipartite graph K4,4, and the seven-vertex complete tripartite graph K3,3,1.
A minor of a graph G is another graph formed from G by contracting and removing edges. As the Robertson–Seymour theorem shows, many important families of graphs can be characterized by a finite set of forbidden minors: for instance, according to Wagner's theorem, the planar graphs are exactly the graphs that have neither the complete graph K5 nor the complete bipartite graph K3,3 as minors.
...
Wikipedia