Edge Contractions in \(3\)-Connected Graphs

William McCuaig1
1Department of Combinatorics and Optimization University of Waterloo Waterloo, Ontario, N2L 3G1 CANADA

Abstract

For \(v \geq 4\) we determine the largest number \(f(v)\), such that every simple \(3\)-connected graph on \(v\) vertices has \(f(v)\) edge contractions which result in a smaller \(3\)-connected graph. We also characterize those simple \(3\)-connected graphs on \(v\) vertices which have exactly \(f(v)\) such edge contractions.