Return to Answer

Nice question. I am also keen to learn of more examples.

Here are some more details on the Hamiltonian cycle example. This is expressible in $\mathsf{MSO_2}$ since testing if a graph is connected is expressible in $\mathsf{MSO}_2$ and testing if a set of edges induces a $2$-regular subgraph is clearly expressible in $\mathsf{MSO}_2$. Indeed, connectivity is actually expressible in $\mathsf{MSO_1}$ 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$. However, $\mathsf{MSO}_1$ does not know the difference between balanced complete bipartite graphs (which do have Hamiltonian cycles) and unbalanced complete bipartite graphs (which do not have Hamiltonian cycles).

Another example I think that works is the existence of an odd (or even) length path between two fixed vertices $u$ and $v$. This is expressible in $\mathsf{MSO}_2$ since a path between $u$ and $v$ is a set of edges $P$ such that $G[P]$ is connected, $u$ and $v$ have degree $1$ in $G[P]$ and all other vertices in $G[P]$ have degree $2$. We can say that $P$ has odd length in $\mathsf{MSO}_2$ since $P$ has odd length (length is the number of edges) if and only if there exists a partition $A \cup B$ of $V(P)$ such that $u \in A$, $v \in B$, and for each $e \in P$, $e$ has one end in $A$ and one end in $B$. However, although it is possible to say that there exists a path between $u$ and $v$ in $\mathsf{MSO}_1$, I do not see how to specify the parity of such a path in $\mathsf{MSO}_1$.

Nice question. I am also keen to learn of more examples.

Here are some more details on the Hamiltonian cycle example. This is expressible in $\mathsf{MSO_2}$ since testing if a graph is connected is expressible in $\mathsf{MSO}_2$ and testing if a set of edges induces a $2$-regular subgraph is clearly expressible in $\mathsf{MSO}_2$. Indeed, connectivity is actually expressible in $\mathsf{MSO_1}$ 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$. However, $\mathsf{MSO}_1$ does not know the difference between balanced complete bipartite graphs (which do have Hamiltonian cycles) and unbalanced complete bipartite graphs (which do not have Hamiltonian cycles).

Edit. Another example I thought that works is the existence of an odd (or even) length path between two fixed vertices $u$ and $v$. However, this turns out to be expressible in both $\mathsf{MSO}_2$ and $\mathsf{MSO}_1$. Thanks to Emil Jeřábek for the comments below.

Odd length paths are expressible in $\mathsf{MSO}_2$ since a path between $u$ and $v$ is a set of edges $P$ such that $G[P]$ is connected, $u$ and $v$ have degree $1$ in $G[P]$ and all other vertices in $G[P]$ have degree $2$. We can say that $P$ has odd length in $\mathsf{MSO}_2$ since $P$ has odd length (length is the number of edges) if and only if there exists a partition $A \cup B$ of $V(P)$ such that $u \in A$, $v \in B$, and for each $e \in P$, $e$ has one end in $A$ and one end in $B$.

For $\mathsf{MSO}_1$, we can say that $u$ and $v$ are connected by an odd length path in $G$ if there exist disjoint subsets $A$ and $B$ of $V(G)$ such that $u \in A$, $v \in B$, and the subgraph consisting of all edges between $A$ and $B$ is connected.

Nice question. I am also keen to learn of more examples.

Here are some more details on the Hamiltonian cycle example. This is expressible in $\mathsf{MSO_2}$ since testing if a graph is connected is expressible in $\mathsf{MSO}_2$ and testing if a set of edges induces a $2$-regular subgraph is clearly expressible in $\mathsf{MSO}_2$. Indeed, connectivity is actually expressible in $\mathsf{MSO_1}$ 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$. However, $\mathsf{MSO}_1$ does not know the difference between balanced complete bipartite graphs (which do have Hamiltonian cycles) and unbalanced complete bipartite graphs (which do not have Hamiltonian cycles).

Another example I think that works is the existence of an odd (or even) length path between two fixed vertices $u$ and $v$. This is expressible in $\mathsf{MSO}_2$ since a path between $u$ and $v$ is a set of edges $P$ such that $u$ and $v$ have degree $1$ in $P$ and all other vertices in $V(P)$ have degree $2$. We can say that $P$ has odd length in $\mathsf{MSO}_2$ since $P$ has odd length (length is the number of edges) if and only if there exists a partition $A \cup B$ of $V(P)$ such that $u \in A$, $v \in B$, and for each $e \in P$, $e$ has one end in $A$ and one end in $B$. However, although it is possible to say that there exists a path between $u$ and $v$ in $\mathsf{MSO}_1$, I do not see how to specify the parity of such a path in $\mathsf{MSO}_1$.

Nice question. I am also keen to learn of more examples.

Here are some more details on the Hamiltonian cycle example. This is expressible in $\mathsf{MSO_2}$ since testing if a graph is connected is expressible in $\mathsf{MSO}_2$ and testing if a set of edges induces a $2$-regular subgraph is clearly expressible in $\mathsf{MSO}_2$. Indeed, connectivity is actually expressible in $\mathsf{MSO_1}$ 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$. However, $\mathsf{MSO}_1$ does not know the difference between balanced complete bipartite graphs (which do have Hamiltonian cycles) and unbalanced complete bipartite graphs (which do not have Hamiltonian cycles).

Another example I think that works is the existence of an odd (or even) length path between two fixed vertices $u$ and $v$. This is expressible in $\mathsf{MSO}_2$ since a path between $u$ and $v$ is a set of edges $P$ such that $G[P]$ is connected, $u$ and $v$ have degree $1$ in $G[P]$ and all other vertices in $G[P]$ have degree $2$. We can say that $P$ has odd length in $\mathsf{MSO}_2$ since $P$ has odd length (length is the number of edges) if and only if there exists a partition $A \cup B$ of $V(P)$ such that $u \in A$, $v \in B$, and for each $e \in P$, $e$ has one end in $A$ and one end in $B$. However, although it is possible to say that there exists a path between $u$ and $v$ in $\mathsf{MSO}_1$, I do not see how to specify the parity of such a path in $\mathsf{MSO}_1$.

Nice question. I am also keen to learn of more examples.

Here are some more details on the Hamiltonian cycle example. This is expressible in $\mathsf{MSO_2}$ since testing if a graph is connected is expressible in $\mathsf{MSO}_2$ and testing if a set of edges induces a $2$-regular subgraph is clearly expressible in $\mathsf{MSO}_2$. Indeed, connectivity is actually expressible in $\mathsf{MSO_1}$ 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$. However, $\mathsf{MSO}_1$ does not know the difference between balanced complete bipartite graphs (which do have Hamiltonian cycles) and unbalanced complete bipartite graphs (which do not have Hamiltonian cycles).

Nice question. I am also keen to learn of more examples.

Here are some more details on the Hamiltonian cycle example. This is expressible in $\mathsf{MSO_2}$ since testing if a graph is connected is expressible in $\mathsf{MSO}_2$ and testing if a set of edges induces a $2$-regular subgraph is clearly expressible in $\mathsf{MSO}_2$. Indeed, connectivity is actually expressible in $\mathsf{MSO_1}$ 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$. However, $\mathsf{MSO}_1$ does not know the difference between balanced complete bipartite graphs (which do have Hamiltonian cycles) and unbalanced complete bipartite graphs (which do not have Hamiltonian cycles).

Another example I think that works is the existence of an odd (or even) length path between two fixed vertices $u$ and $v$. This is expressible in $\mathsf{MSO}_2$ since a path between $u$ and $v$ is a set of edges $P$ such that $u$ and $v$ have degree $1$ in $P$ and all other vertices in $V(P)$ have degree $2$. We can say that $P$ has odd length in $\mathsf{MSO}_2$ since $P$ has odd length (length is the number of edges) if and only if there exists a partition $A \cup B$ of $V(P)$ such that $u \in A$, $v \in B$, and for each $e \in P$, $e$ has one end in $A$ and one end in $B$. However, although it is possible to say that there exists a path between $u$ and $v$ in $\mathsf{MSO}_1$, I do not see how to specify the parity of such a path in $\mathsf{MSO}_1$.