Winning strategy for graphs (Ehrenfeucht-Fraïssé games)

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$

• I guess a line with $2^{n+1}$ nodes would suffice. – Primo Petri Aug 23 '15 at 9:53
• Might be good to mention which book this is from. (Title, author(s), etc.) – user642796 Aug 23 '15 at 10:03
• I have added to the question why a finite $G_2$ doesn't work. The book is a private book at our university wich isn't published. – abcdef Aug 23 '15 at 10:06
• The proof with the infinite graph seems most elegant to me. – bof Aug 23 '15 at 10:57

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: