FOL sentence which is true in a graph G exactly when G has no cycles of length $n $

Question

Consider only directed graphs. Show that for each $ n \ge 1$ there is an $L_{\text{graph} } $-sentence $ \phi_n$ which is true in a graph $G $ exactly when $G $ has no cycles of length $n $.

I'm not really familiar with graph theory, so I have no idea how to define such sentences. This question is the first of three in an exercise, and I need this one to proceed.

Thanks.

Answer 1

Hint: Saying "there is no cycle of length $n$" is saying you can't find vertices $x_1, \ldots, x_n$ so that

$$x_1 E x_2 E x_3 \ldots E x_{n-1} E x_n E x_1$$

where $x E y$ means that $x$ and $y$ are adjacent in the graph.

Do you see how to write this formally in FOL?

---

I hope this helps ^_^