Large Contractible Subgraphs of a 3-Connected Graph

Abstract

Let m ≥ 5 be a positive integer and let G be a 3-connected graph on at least 2m + 1 vertices. We prove that G has a contractible set W such that m ≤ W ≤ 2m − 4. (Recall that a set W ⊂ V (G) of a 3-connected graph G is contractible if the graph G(W ) is connected and the graph G − W is 2-connected.) A particular case for m = 4 is that any 3-connected graph on at least 11 vertices has a contractible set of 5 or 6 vertices.

Keywords

• connectivity
• 3-connected graph
• contractible subgraph
• 05c40