First-Order Complexity of Subgraph Isomorphism via Kneser Graphs

The problem of finding the least number of variables of a first-order formula expressing the statement that an input-graph contains a subgraph isomorphic to a given pattern-graph is studied. Input-graphs of sufficiently high connectivity are considered. This problem has previously been solved for all pattern-graphs on four vertices except the simple cycle and the diamond graph. In the paper, this number is found for the two remaining graphs.