  We show that a graph with $n$ vertices and vertex cover of size $k$ has at
most $4^k + n$ potential maximal cliques. We also show that for each positive
integer $k$, there exists a graph with vertex cover of size $k$, $O(k^2)$
vertices, and $\Omega(4^k)$ potential maximal cliques. Our results extend the
results of Fomin, Liedloff, Montealegre, and Todinca [Algorithmica,
80(4):1146--1169, 2018], who proved an upper bound of $poly(n) 4^k$, but left
the lower bound as an open problem.
