Familia de Petersen

Lleva el nombre del matemático danés Julius Petersen.

Debido a que estas operaciones conservan el número de aristas en un grafo, solo hay un número finito de grafos o multigrafos que se pueden formar a partir de un solo grafo inicial G mediante combinaciones de transformadas Δ-Y e Y-Δ.

Como muestra el teorema de Robertson-Seymour, muchas familias importantes de grafos se pueden caracterizar por un conjunto finito de menores prohibidos: por ejemplo, según el teorema de Wagner, los grafos planos son exactamente aquellos que no tienen un grafo completo K5 ni un grafo bipartito completo K3,3 como menores.

[1]​ Horst Sachs había estudiado previamente tales incrustaciones, y demostró que los siete grafos de la familia de Petersen no tienen tales incrustaciones, planteando la cuestión de caracterizar los grafos embebibles sin enlaces mediante subgrafos prohibidos.

Por ejemplo, el grafo completo K4 se puede reducir a un solo vértice mediante una transformada Y-Δ que lo convierte en un triángulo con aristas duplicadas, la eliminación de las tres aristas duplicadas, una transformada Δ-Y que lo convierte en una garra K1,3, y la eliminación de los tres vértices de grado uno de la garra.