On the toughness index of planar graphs
Michael B. Dillencourt · Journal of Graph Theory · 1994
Abstract 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.