Contractible edges in 3-connected graphs that preserve a minor

Abstract

Let $G$ be a $3$-connected graph with a $3$-connected (or sufficiently small) simple minor $H$. We establish that $G$ has a forest $F$ with at least $\lceil (|G|-|H|+1)/2\rceil$ edges such that $G/e$ is $3$-connected with an $H$-minor for each $e\in E(F)$. Moreover, we may pick $F$ with $|G|-|H|$ edges provided $G$ is triangle-free. These results are sharp. Our result generalizes a previous one by Ando et. al., which establishes that a $3$-connected graph $G$ has at least $\lceil |G|/2\rceil$ contractible edges. As another consequence, each triangle-free $3$-connected graph has an spanning tree of contractible edges. Our results follow from a more general theorem on graph minors, a splitter theorem, which is also established here.

References in corpus (1)

• A splitter theorem on 3-connected matroids and graphs