The Sauer–Shelah lemma. The traces on a set $S$ of at most $k$ vertices form a family of subsets of $S$ whose shattered sets are shattered by the neighborhoods of $G$, so they have size at most $d$. By the Sauer–Shelah lemma of mathlib (via Pajor's bound on the shatterer) the family has at most $∑_{i ≤ d} C(|S|, i) ≤ (|S| + 1)^d ≤ (k + 1)^d$ members.