“Hamiltonian graphs cannot be expressed in existential monadic second order logic because palindromes are not a regular language.”
Apparently, Keith Ellul immediately realized that
without MONADIC the statement is false, because it is “trivial” to see
that hamiltonian graphs can be expressed in existential second order
I can't wait to tell the guys at the pub.