Tree Containment Above Minimum Degree is FPT

According to the classic Chvátal's Lemma from 1977, a graph 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, 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 of our main result is based on an interplay between extremal graph theory and parameterized algorithms.