Skip to main content
4 of 6
added 776 characters in body
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

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$.

Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187