On the maximum orders of an induced forest, an induced tree, and a stable set

Abstract

Let G be a connected graph, n the order of G, and f (resp. t) the maximum order of an induced forest (resp. tree) in G. We show that f - t is at most n - 2√n-1. In the special case where n is of the form a2 + 1 for some even integer a ≥ 4, f - t is at most n - 2√n-1-1. We also prove that these bounds are tight. In addition, letting α denote the stability number of G, we show that α - t is at most n + 1- 2√2n this bound is also tight.