On a conjecture of Thomassen and Toft
Matthias Kriesell · Journal of Graph Theory · 1999
This article is motivated by a conjecture of Thomassen and Toft on the number s2(G) of separating vertex sets of cardinality 2 and the number υ2(G) of vertices of degree 2 in a graph G belonging to the class 𝒢 of all 2-connected graphs without nonseparating induced cycles. Let ‖G‖ denote the number of edges of the graph G. Thomassen and Toft conjectured in [C. Thomassen & B. Toft, J. Combin. Theory B 31 (1981), 199–224] the existence of a positive constant c satisfying s2(G) + υ2(G) > c · ‖G‖ for all G ∈ 𝒢. We shall see that this is not true in general. Restricting ourselves to planar graphs, we obtain s2(G) + υ2(G) > · ‖G‖ for all planar G ∈ 𝒢, where is best-possible. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 118–122, 1999