Return to Revisions

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 $K_{n,n}$ (which has a Hamiltonian cycle) and $K_{n-1,n+1}$ (which does not have a Hamiltonian cycle).