I am looking for a proof for the non-definability, in first order logic, of the exisence of a Hamiltonian cycle (or path) on a graph. It seems it can be proved using Ehrefeucht-Fraïssé games, but I can't manage to do it. Here are some things I tried that didn't work:
- Deriving the problem from Eulerian cycles. Tried making the edges into vertices and connecting them in some smart way. Didn't work.
- Deriving from parity. Tried finding a way to build a graph related to a number $n$ such that if $n$ is even, the graph would be Hamiltonian, but if $n$ was odd, it wouldn't.
I suppose deriving the problem from another one (especially those above) may be hard or downright impossible because it would mean translating a $NP$-complete problem to a much simpler one using first-order sentences, which seems wrong.
If someone needs such definitions, an Eulerian path is a path that goes through all edges only once and a Hamiltonian path is one that goes through all vertices once. A cycle is a closed path.
Also, I'm working with finite graphs only.