  Let $\mathscr C$ be a class of finite and infinite graphs that is closed
under induced subgraphs. The well-known {\L}o\'s-Tarski Theorem from classical
model theory implies that $\mathscr C$ is definable in first-order logic (FO)
by a sentence $\varphi$ if and only if $\mathscr C$ has a finite set of
forbidden induced finite subgraphs. It provides a powerful tool to show
nontrivial characterizations of graphs of small vertex cover, of bounded
tree-depth, of bounded shrub-depth, etc. in terms of forbidden induced finite
subgraphs. Furthermore, by the Completeness Theorem, we can compute from
$\varphi$ the corresponding forbidden induced subgraphs. We show that this
machinery fails on finite graphs.
  - There is a class $\mathscr C$ of finite graphs which is definable in FO and
closed under induced subgraphs but has no finite set of forbidden induced
subgraphs.
  - Even if we only consider classes $\mathscr C$ of finite graphs which can be
characterized by a finite set of forbidden induced subgraphs, such a
characterization cannot be computed from an FO-sentence $\varphi$, which
defines $\mathscr C$, and the size of the characterization cannot be bounded by
$f(|\varphi|)$ for any computable function $f$.
  Besides their importance in graph theory, the above results also
significantly strengthen similar known results for arbitrary structures.
