On winning Ehrenfeucht games and monadic NP

AbstractInexpressibility results in Finite Model Theory are often proved by showing that Duplicator, one of the two players of an Ehrenfeucht game, has a winning strategy on certain structures.In this article a new method is introduced that allows, under certain conditions, the extension of a winning strategy of Duplicator on some small parts of two finite structures to a global winning strategy.As applications of this technique it is shown that •— Graph Connectivity is not expressible in existential monadic second-order logic (MonNP), even in the presence of a built-in linear order,•— Graph Connectivity is not expressible in MonNP even in the presence of arbitrary built-in relations of degree n0(1), and•— the presence of a built-in linear order gives MonNP more expressive power than the presence of a built-in successor relation