I've been reading about YΔY-reducibility today. A connected graph is YΔY-reducible if it can be reduced to a single vertex by YΔ and ΔY transformations (replace a triangle by a degree-three vertex or vice versa) and series-parallel reductions (remove self-loops and multiple adjacencies, delete degree-one vertices, and contract paths of degree-two vertices into single edges). Every planar graph is reducible; it makes an amusing exercise to transform your favorite planar graph (such as a cube) into nothing, using these operations.

It turns out that every minor of a YΔY-reducible graph is itself reducible, which raises the questions of what are the forbidden minors for this family and how is it related to other minor-closed graph families. The forbidden minors include the complete graph \( K_6 \), the Petersen graph, and the other five graphs of the Petersen family (the graphs that can be reached from \( K_6 \) and the Petersen graph by YΔ and ΔY transformations). But these are also the forbidden minors for linkless embedding: a graph can be embedded in three-dimensional space, with no two of its cycles linked together, if and only if it does not contain one of these seven graphs as a minor. So this implies that every YΔY-reducible graph is linkless embeddable.

Are these two classes of graphs the same? No! Truemper (pages 100–101) describes a counterexample due to Neil Robertson of an apex graph (a graph formed by adding one vertex to a planar graph) that is not reducible. The planar graph at the base of Robertson's construction is bipartite, with eight degree-three vertices on one side of the bipartition and six degree-four vertices on the other side. The construction is simply to add a new apex, connecting it to all the degree-three vertices. The resulting graph is still bipartite, so it has no triangles and we can't perform any ΔY transformations. And the minimum degree is four, so we can't perform any of the other transformations or reductions. Therefore, Robertson's example is either itself a forbidden minor for the reducible graphs or it contains smaller forbidden minors. But because it's an apex graph, it's linkless embeddable and doesn't contain the Petersen family graphs as minors, so whatever it does contain must be something different. Yu shows that Robertson's example actually contains 57578 forbidden minors, formed by deleting one of the edges of the example and then performing YΔ and ΔY transformations. Since the forbidden minors for the reducible graphs are a superset of the forbidden minors for linkless embeddable graphs, the reducible graphs themselves are a proper subset of the linkless embeddable graphs.

Ok, so the linkless-embeddable and reducible graphs are different: one class is contained in the other. What about the apex graphs? The apex graphs and the reducible graphs are both subsets of the linkless embeddable graphs, and we already know that there are apex graphs that are not reducible. But there also exist reducible graphs that are not apex: the one below is an example. It's formed by duplicating two opposite vertices of a cube, and some case analysis shows that it's a minimal forbidden minor for the apex graphs. (Other minimal forbidden minors for the apex graphs include the disjoint unions of pairs of Kurotowski graphs \( K_5 \) or \( K_{3,3} \), as well as at least three of the graphs in the Petersen family: \( K_6 \), the Petersen graph itself, and \( K_{3,3,1} \). I suspect the other four Petersen family graphs are also minimal forbidden minors for the apex graphs but I haven't gone through the case analysis needed to check them.) But the graph below is reducible: by performing YΔ transformations on the two leftmost and two rightmost vertices to turn them into triangles, eliminating the parallel edges, and then performing ΔY transformations, we get a cube, which is a planar graph and therefore is reducible.

Double-tipped cube graph

ETA 7/25: Here's another forbidden minor for the apex graphs. Start with a triangular prism, and connect two new vertices to each of the six prism vertices but not to each other. It's the graph of a 4-polytope, the double pyramid over the prism. It's also a YΔ transformation of an apex graph, but not itself an apex graph.