If a graph G contains a vertex v with exactly three neighbors, then the Y-Δ transform of G at v is the graph formed by removing v from G and adding edges between each pair of its three neighbors.
If a graph H contains a triangle uvw, then the Δ-Y transform of H at uvw is the graph formed by removing edges uv, vw, and uw from H and adding a new vertex connected to all three of u, v, and w.
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 graphK4,4, and the seven-vertex complete tripartite graphK3,3,1.
Forbidden minors
A minor of a graphG 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 graphK3,3 as minors. Neil Robertson, Paul Seymour, and Robin Thomas used the Petersen family as part of a similar characterization of linkless embeddings of graphs, embeddings of a given graph into Euclidean space in such a way that every cycle in the graph is the boundary of a disk that is not crossed by any other part of the graph. Horst Sachs had previously studied such embeddings, shown that the seven graphs of the Petersen family do not have such embeddings, and posed the question of characterizing the linklessly embeddable graphs by forbidden subgraphs. Robertson et al. solved Sachs' question by showing that the linkless embeddable graphs are exactly the graphs that do not have a member of the Petersen family as a minor. The Petersen family also form some of the forbidden minors for another family of graphs, the YΔY-reducible graphs. A connected graph is YΔY-reducible if it can be reduced to a single vertex by a sequence of steps, each of which is a Δ-Y or Y-Δ transform, the removal of a self-loop or multiple adjacency, the removal of a vertex with one neighbor, and the replacement of a vertex of degree two and its two neighboring edges by a single edge. For instance, the complete graph K4 can be reduced to a single vertex by a Y-Δ transform that turns it into a triangle with doubled edges, removal of the three doubled edges, a Δ-Y transform that turns it into the clawK1,3, and removal of the three degree-one vertices of the claw. Each of the Petersen family graphs forms a minimal forbidden minorfor the family of YΔY-reducible graphs. However, Neil Robertson provided an example of an apex graph that is not YΔY-reducible, showing that the YΔY-reducible graphs form a proper subclass of the linkless embeddable graphs and have additional forbidden minors. In fact, as Yaming Yu showed, there are at least 68,897,913,652 forbidden minors for the YΔY-reducible graphs beyond the seven of the Petersen family.
