Sentences in first order logic for graphs

Question

I am trying to write first-order sentences about graphs. We can use relation $E(x,y)$ which means that there exist directed edge $x\to y$. Moreover, we can use only $3$ variables, but we can arbitraly requantify each of them.

I show my trial, but I am not sure about corectness of them. Moreover, I can't write formula for particular cases.

(1) Graph is finite directed cycle.
$\left(\forall_x\forall_y E(x,y)\to\neg E(y,x)\right)\wedge (\forall_x\forall_y\forall_z E(x,y) \wedge E(x,z)\to y=z)\wedge (\forall_x\exists_y E(x,y)) $. Of course it should be ok only for cycles with at least $3$ edges.
(2) Graph is directed cycle with exactly $3n$ edges.
I think that length of this formula depends on $n$. So, first of all as above - conditions for directed cycle. However, I don't know how to force exactly $3n$ edges.

Can you check my answers and help me with my wrong/empty reasoning ?

Answer 1

Given the negative answer to the question, as explained in my other answer, it is natural to ask some related questions, namely whether there is a set $S$ of axioms (in the same language of graphs) that are satisfied by:

Only graphs that are either a cycle or an infinite chain.

Intuitively there is a global constraint that there is only one cycle/chain. Thus it is no surprise that the same kind of compactness argument works, by adding two new constants $v,w$ and adding for each natural $k$ an axiom stating that "$v,w$ are not reachable in either direction within $k$ edges". Each finite subset of the (modified) set of axioms is satisfied by an infinite chain together with an appropriate interpretation of $v,w$. Thus by compactness the axioms still have a model. But neither a cycle nor an infinite chain satisfies all the added axioms; contradiction.

Only graphs that are a disjoint union of semi-infinite chains.

Again, intuitively the global constraint is that each chain is infinite (rather than being cyclic). The compactness argument is slightly harder to see here. Let $c_i$ be a new constant for each natural $i$, and then add an axiom for each $k$ stating that "$c_k \to c_{k-1} \to \cdots \to c_1 \to c_0$" (where the arrows indicate directed edges). Check that the same argument goes through.

Only graphs that are a disjoint union of infinitely many (doubly-)infinite chains.

I'll leave this as an exercise. Note that the language only has the edge relation $E$, so if you think it can be axiomatized you must do so without adding any predicate-symbols or function-symbols (or constants). If you think it can't, prove it.

Answer 2

Finite directed cycle

Your attempt is wrong. In short, your attempt is "$\forall x,y\ ( E(x,y) \to \neg E(y,x) ) \land \forall x\ \exists! y\ ( E(x,y) )$", which asserts "for every (directed) edge there is no backward edge, and for every vertex there is a unique outgoing edge". The second part does force the graph to have an infinite chain, because it ensures that you can keep stepping to the (unique) next vertex. But nothing forces that chain to loop back on itself.

Have you considered that it is impossible? If not, you may want to think about it before looking below.

Finite X

In general, even if one uses infinitely many sentences, one cannot force the structure to be finite if one must accept arbitrarily large instances and there is no global constraint, roughly speaking. In the case of graphs, all you can express are local constraints, namely the edges. So if there is a set $S$ of axioms that are satisfied by only cycles of all finite sizes, then you can construct a separate set $T$ of sentences, one for each natural $k$ that asserts "there is a chain with at least $k$ distinct vertices". Then there is a structure that satisfies any finite subset of $S \cup T$ (prove it yourself), and hence by compactness there is a structure that satisfies $S \cup T$. But any such structure must be a finite cycle (by definition of $S$) and hence cannot satisfy $T$; contradiction. Therefore such $S$ does not exist.