I'm stuck with a question:
Proof that you can't express if a graph is cyclic in first-order logic.
The definition of cyclic is that for every node there is a path back to the node wich never uses an edge twice.
This question appears in my book in the topic: Ehrenfeucht-Fraïssé games. For every $n \geq 0$ we need to find two graphs $G_1$ and $G_2$ so $G_1 \sim_n G_2$ such that $G_1$ is cyclic and $G_2$ isn't.
I can't find any two such finite graphs. However if I allow $G_2$ (right graph) to have an infinit amount of nodes the following two graphs work:
Provided $G_1$ (left) has enough, but a finite amount of, nodes. But this doesn't seem verry elegant. I would like to see finite graphs wich also works.
Notice that the following strategy explains why a finite $G_2$ doesn't work:
round 1: spoiler choses an $a_1$ endpoint in $G_2$. Duplicator choses a point $b_1$.
round 2: spoiler choses the other endpoint $a_2$ in $G_2$. Duplicator choses a point $b_2$.
round 3: spoiler: neighbour point of $b_2$. Duplicator: neighbour point of $a_2$.
round 4: spoiler: other neighbour point of $b_2$. Duplicator is lost because there is no ohter neighbour point of $a_2$ because it's an endpoint in $G_2$
Thanks in advance.