The Ehrenfeucht-Fraissé Game for Paths and Cycles

Abstract

Let \(L\) and \(R\) be two graphs. For any positive integer \(n\), the Ehrenfeucht-Fraissé game \(G_n(L, R)\) is played as follows: on the \(i\)-th move, with \(1 \leq i \leq n\), the first player chooses a vertex on either \(L\) or \(R\), and the second player responds by choosing a vertex on the other graph. Let \(l_i\) be the vertex of \(L\) chosen on the \(i^{th}\) move, and let \(r_i\) be the vertex of \(R\) chosen on the \(i^{th}\) move. The second player wins the game iff the induced subgraphs \(L\{l_1,l_2,…,l_n\}\) and \(R\{r_1,r_2,…,r_n\}\) are isomorphic under the mapping sending \(l_i\) to \(r_i\). It is known that the second player has a winning strategy if and only if the two graphs, viewed as first-order logical structures (with a binary predicate E), are indistinguishable (in the corresponding first-order theory) by sentences of quantifier depth at most \(n\). In this paper we will give the first complete description of when the second player has a winning strategy for \(L\) and \(R\) being both paths or both cycles. The results significantly improve previous partial results.