Tree Containment Above Minimum Degree is FPT

According to the classic Chvátal's Lemma from 1977, a graph \ (G\) of minimum degree \ ( (G) \) contains every tree on \ ( (G) +1\) vertices. Our main result is the following algorithmic “extension” of Chvátal's Lemma: For any \ (n\) -vertex graph \ (G\), an integer \ (k\), and a tree \ (T\) on at most \ ( (G) +k\) vertices, deciding whether \ (G\) contains a subgraph isomorphic to \ (T\) can be done in time \ (f (k) n^O (1) \) for some function \ (f\) of \ (k\) only. The proof is based on an intricate interplay between extremal graph theory and parameterized algorithms.