Class of graphs that contain a cycle is not axiomatizable

Question

Let $S_G=\{E\}$ be the language of graphs theory and $\Phi = \{ \forall x \neg E(x,x); \forall x \forall y [E(x,y) \rightarrow E(y,x)]\}$ be the axioms of graphs theory. Let $\mathcal G$ be a graph. The sequence $(a_0, ... , a_{n+2})$ in $G$ is a cycle if $\mathcal G \models E(a_0,a_1) \wedge ... \wedge E(a_{n+1},a_{n+2}) \wedge E(a_{n+2},a_0) $. How can I show that the class of all graphs that contain a cycle is not axiomatizable?

Answer 1

Assume for a contradiction that there is a set $\Sigma$ of sentences such that, for any graph $\mathcal G$, $$\mathcal G\models\Sigma\iff\mathcal G\text{ has a cycle.}$$ Let $\alpha_n$ be a sentence such that $$\mathcal G\models\alpha_n\iff\mathcal G\text{ has no cycle of length }\le n.$$ So $\Sigma\cup\{\alpha_n:n\in\mathbb N\}$ is unsatisfiable. It follows by the compactness theorem that there is some $n\in\mathbb N$ such that $\Sigma\cup\{\alpha_n\}$ is unsatisfiable. But this is wrong; there is a graph whose shortest cycle has length $n+1$.