On contractible and vertically contractible elements in 3-connected matroids and graphs Original Research Article

An edge e in a 3-connected graph G is contractible if the contraction G/e is still 3-connected. The problem of bounding the number of contractible edges in a 3-connected graph has been studied by numerous authors. In this paper, the corresponding problem for matroids is considered and new graph results are obtained. An element e in a 3-connected matroid M is contractible or vertically contractible if its contraction M/e is, respectively, 3-connected or vertically 3-connected. Cunningham and Seymour independently proved that every 3-connected matroid has a vertically contractible element. In this paper, we study the contractible and vertically contractible elements in 3-connected matroids and get best-possible lower bounds for the number of vertically contractible elements in 3-connected and minimally 3-connected matroids. We also prove generalizations of Tutteʹs Wheels and Whirls Theorem for matroids and Tutteʹs Wheels Theorem for graphs.