# Showing via Ehrenfeucht-Fraïssé games that acyclicity is not definable in FO for finite graphs

I've been working through Elements of Finite Model Theory (Leonid Libkin) and am stuck on exercise 3.4.

As in the title, the question asks "Using Ehrenfeucht-Fraïssé games, show that acyclicity of finite graphs is not FO-definable."

We know that a property over finite structures is inexpressible in FO iff for every $k$ there are two finite structures $\mathfrak{A, B}$ such that $\mathfrak{A}$ has said property but $\mathfrak{B}$ doesn't and the duplicator always has a winning strategy in $k$-round Ehrenfeucht-Fraïssé games.

My initial approach was to take $\mathfrak{A}$ to be a large enough cycle so that the spoiler cannot demonstrate its cyclicity. The issue is that, if $\mathfrak{B}$ is acyclic, then there is some vertex with in-degree equal to 0 (?) So for $k \geq 2$ the spoiler seems to have a winning strategy by choosing such a vertex in $\mathfrak{B}$ for the first round. Then when the duplicator responds with some $a \in \mathfrak{A}$ the spoiler can play the vertex in $\mathfrak{A}$ who has an edge pointing to $a$ which the duplicator is unable to replicate in $\mathfrak{B}$

Adding more structure to $\mathfrak{A}$ to try and work around this, I continue to run into similar problems.

This question seems to be asking the same thing (but without the restriction to finite graphs) but the answer seems to use two graphs which are both cyclic so I'm assuming I'm missing some critical understanding about the question/concept or they're working with a non-standard definition of cyclicity.

Consider the two following graphs: Choose the number of rays, their lengths and the number of nodes on the circles to be very large w.r.t. $n$. Then you will not be able to distinguish between them in a game of length $n$. Of course this requires a proof...
• Do you really need such a large number of rays? It seems to me that $n$ would be sufficient. – Ibrahim Jun 26 at 14:02
• Yes, I think $n$ rays is sufficient. Though I don't think taking everything to be 'very large' relative to $n$ makes the construction any more complicated and it slightly reduces the cognitive load required to verify the proof works. – Dylan Jun 27 at 13:51