A good example is testing if a graph is connected. This is easily seen to be $\mathsf{MSO}_2$ expressible, since a graph $G$ is connected if and only if for all partitions $A \cup B$ of $V(G)$, there is an edge between $A$ and $B$. On the other hand, it is not possible to test if a graph is connected in $\mathsf{MSO}_1$ (or even in existential $\mathsf{MSO}_2$). See this paper of Fagin, Stockmeyer and Vardi for a short proof via Enrenfeucht–Fraïssé games, which is easier than an earlier proof due to Fagin.
Tony Huynh
- 32.1k
- 11
- 112
- 187