Four-terminal reducibility and projective-planar wye-delta-wye-reducible graphs (Q4946544)

In an undirected graph \(G\) a wye is a vertex of degree 3, and a delta is a cycle of length 3. In a \(Y\Delta\) transformation a wye \(w\) and its three incident edges, \(wx\), \(wy\), and \(wz\) are replaced by a delta \(xyz\); in a \(\Delta Y\) transformation a delta \(xyz\) is replaced by a new vertex \(w\), adjacent to all of \(x\), \(y\), \(z\); two graphs are \(Y\Delta Y\)-equivalent if one can be transformed into the other by a sequence of \(Y\Delta\) and \(\Delta Y\) transformations. In a loop reduction a loop is deleted; in a degree-one reduction a vertex of degree 1 and its incident edge are deleted; in a series reduction a vertex \(y\) of degree 2 and its incident edges \(xy\) and \(zz\) are deleted, and replaced by a new edge \(xz\); and, in a parallel reduction one of a pair of parallel edges is deleted; a connected graph is series-parallel reducible it if can be reduced to a single vertex by a sequence of loop, series, parallel, and possibly degree-one reductions. A connected graph is \(Y\Delta Y\)-reducible if it can be reduced to a single vertex by a sequence of series-parallel reductions and \(Y\Delta Y\) transformations. A subset \(T\) of \(V(G)\) of terminals consists of vertices which may not be deleted in degree-one or series reductions, nor in a \(Y\Delta\) transformation. From the authors' abstract: In this article we show that four-terminal planar graphs are \(Y\Delta Y\)-reducible where at least three of the vertices lie on the same face. Using this result we characterize \(Y\Delta Y\)-reducible projective-planar graphs. We also consider terminals in projective-planar graphs, and establish that graphs of crossing-number 1 are \(Y\Delta Y\)-reducible.