On the toughness index of planar graphs

The toughness indexτ ( G ) of a graph G is defined to be the largest integer t such that for any S ⊆ V ( G ) with | S | > t , c ( G ‐ S ) < | S | ‐ t , where c ( G ‐ S ) denotes the number of components of G ‐ S . In particular, 1‐tough graphs are exactly those graphs for which τ( G ) ≥ 0. In this paper, it is shown that if G is a planar graph, then τ( G ) ≥ 2 if and only if G is 4‐connected. This result suggests that there may be a polynomial‐time algorithm for determining whether a planar graph is 1‐tough, even though the problem for general graphs is NP‐hard. The result can be restated as follows: a planar graph is 4‐connected if and only if it remains 1‐tough whenever two vertices are removed. Hence it establishes a weakened version of a conjecture, due to M. D. Plummer, that removing 2 vertices from a 4‐connected planar graph yields a Hamiltonian graph.