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.
Sorry, my previous answer was wrong because I misunderstood your definition of "cyclic". In this variant the answer is still yes, but you need another example:
For given $n$, choose the number of "lollipops" to be very large and the distance between any two nodes of degree $>2$ to be very large as well. Then you cannot distinguish between the above graphs.
edit: a simpler example is possible as well, note that lines in this drawing correspond to paths of nodes. For given $n$ just make sure that distances between nodes of degree $3$ are very large: