• You'll want to use a multiplicative Chernoff bound (of the form Pr[|X - E[X]| > delta E[X]] for a random variable corresponding to each subset, then union bound. Aim for a tail bound with (|S| log n) in the exponent, which plays nicely with the union bound.
• The multiplicative factor delta is allowed to depend on the subset S -- recall that the deviation is allowed to be epsilon alpha(G), regardless of the edge density of S.
• Arboricity must be at least m/n because S can always be the entire vertex set.