Inductive Tools For Maintaining Connectivity in Graphs and Matroids

Tutte proved in 1961 that every 3-connected simple graph g, other than a wheel, has an edge whosedeletion or contraction is both 3-connected and simple. seymour (1980) and negami (1982) independentlystrengthened tutte’s theorem by proving that, for any 3-connected simple proper minor h of g, we candelete or contract an edge from g to get a graph that, in addition to being both 3-connected and simple,maintains a minor isomorphic to h. tutte generalized his theorem to matroids in 1966 while seymour’soriginal proof of his splitter theorem was done in the more general context of matroids. these theoremsgive us powerful inductive tools for working with graphs and matroids provided our structures are 3-connected. a number of authors, including johnson and thomas, and geelen and zhou, have soughtcorresponding results for graphs and matroids of higher connectivity. this talk will discuss the speaker’sjoint work with carolyn chun and dillon mayhew that finds analogues of the theorems of tutte andseymour for internally 4-connected binary matroids and hence for internally 4-connected graphs, wheresuch graphs are 4-connected except for the possible presence of degree-3 vertices. the talk will assumeno prior knowledge of matroid theory.