Logical complexity of induced subgraph isomorphism for certain graph families

E. D. Kudryavtsev, M. V. Makarov, A. S. Shlychkova +1

We prove that, for every $\ell \ge 4$, there exists an $\ell$-vertex graph and a first order sentence having a quantifier depth at most $\ell -1$ defining the property of having an…