Rooted \(K_4\)-minors (Q396793)

Summary: Let \(a,b,c,d\) be four vertices in a graph \(G\). A \(K_4\) minor rooted at \(a,b,c,d\) consists of four pairwise-disjoint pairwise-adjacent connected subgraphs of \(G\), respectively containing \(a,b,c,d\). We characterise precisely when \(G\) contains a \(K_4\)-minor rooted at \(a,b,c,d\) by describing six classes of obstructions, which are the edge-maximal graphs containing no \(K_4\)-minor rooted at \(a,b,c,d\). The following two special cases illustrate the full characterisation: (1) A 4-connected non-planar graph contains a \(K_4\)-minor rooted at \(a,b,c,d\) for every choice of \(a,b,c,d\). (2) A 3-connected planar graph contains a \(K_4\)-minor rooted at \(a,b,c,d\) if and only if \(a,b,c,d\) are not on a single face.