  Given a graph $F$, let $I(F)$ be the class of graphs containing $F$ as an
induced subgraph. Let $W[F]$ denote the minimum $k$ such that $I(F)$ is
definable in $k$-variable first-order logic. The recognition problem of $I(F)$,
known as Induced Subgraph Isomorphism (for the pattern graph $F$), is solvable
in time $O(n^{W[F]})$. Motivated by this fact, we are interested in determining
or estimating the value of $W[F]$. Using Olariu's characterization of paw-free
graphs, we show that $I(K_3+e)$ is definable by a first-order sentence of
quantifier depth 3, where $K_3+e$ denotes the paw graph. This provides an
example of a graph $F$ with $W[F]$ strictly less than the number of vertices in
$F$. On the other hand, we prove that $W[F]=4$ for all $F$ on 4 vertices except
the paw graph and its complement. If $F$ is a graph on $t$ vertices, we prove a
general lower bound $W[F]>(1/2-o(1))t$, where the function in the little-o
notation approaches 0 as $t$ inreases. This bound holds true even for a related
parameter $W^*[F]\le W[F]$, which is defined as the minimum $k$ such that
$I(F)$ is definable in the infinitary logic $L^k_{\infty\omega}$. We show that
$W^*[F]$ can be strictly less than $W[F]$. Specifically, $W^*[P_4]=3$ for $P_4$
being the path graph on 4 vertices.
  Using the lower bound for $W[F]$, we also obtain a succintness result for
existential monadic second-order logic: A usage of just one monadic quantifier
sometimes reduces the first-order quantifier depth at a super-recursive rate.
