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 \sqrt{n-1} . In the special case where n is of the form a^2+1 for some even integer a \geq 4, f-t is at most n - 2 \sqrt{n-1} - 1. We also prove that these bounds are tight. In addition, letting alpha denote the stability number of G, we show that alpha - t is at most n + 1 - 2 \sqrt{2n}; this bound is also tight. Keywords: induced forest, induced tree, stability number, extremal graph theory. MSC: 05C05, 05C35, 05C69.