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)· nO(1)\) for some function \(f\) of \(k\) only. The proof is based on an intricate interplay between extremal graph theory and parameterized algorithms.