First, you mention "infinite cycles". Let's agree that a cycle in a graph is a path which starts and ends at a vertex $v$ and otherwise does not visit any vertex more than once. By this definition, every cycle is finite, since an infinite path fails to have a starting point or fails to have an ending point or both.
Your sentence $\phi(n)$ almost expresses "there exists a cycle of length $n+2$". I say almost because you've forgotten to require that $v_1$ and $v_2$ are distinct from the $p_i$ as well. So for example the graph $$a\sim b\sim c$$ satisfies $\varphi(2)$, setting $v_1 = a$, $v_2 = b$, $p_1 = b$, $p_2 = c$. But this graph does not have a cycle (of any length).
Ok, let's say we've fixed this problem, and now we have a family of sentences $\phi(n)$ where $\phi(n)$ expresses "there exists a cycle of length $n+2$". Now we want to axiomatize the acyclic graphs. Your theory $$T = \{\varphi(n)\mid n>0\}\cup \text{Graph Axioms}$$
axiomatizes the class of graphs which do contain a cycle of every possible length. Do you see what you need to do to fix this axiomatization?
Once you've fixed that problem, you'll be convinced it's possible to axiomatize the class of acyclic graphs. But you've asked about finite acyclic graphs.
The class of finite ayclic graphs is not elementary. Usually, if you want to show that some class is not elementary, you use the compactness theorem. Let $\psi_n$ be the sentence asserting "there are at least $n$ distinct elements". Suppose for contradiction that there was some theory $T$ axiomatizing the finite acyclic graphs. Consider $T' = T \cup \{\psi_n\mid n\in \mathbb{N}\}$. By compactness, $T'$ is consistent: if $\Delta \subseteq T'$ is a finite subset, let $N$ be maximum such that $\psi_n\in \Delta$. Then any finite acyclic graph of size greater than $N$ is a model of $\Delta$ (for example, take a large graph with no edges). So $T'$ has a model $M$. But then $M\models T$ is a finite acyclic graph, but $M\models \psi_n$ for all $n$, so $M$ is infinite. Contradiction.
The exact same argument shows that if $K$ is any class of finite structures containing arbitrarily large finite structures, $K$ is not elementary. So usually, you cannot axiomatize the class of "finite X".
The exercise in Marker you refer to asks you to show that the class of trees is elementary. Unfortunately, there are many definitions of "tree" in mathematics. I think the definition that Marker has in mind is the one from order theory: a tree is a partially ordered set $T$ with a minimal element such that for each element $v\in T$, the set of predecessors of $v$, ${\downarrow}v = \{u\in T\mid u\leq v\}$, is linearly ordered.
Here are some other common definitions of "tree" which are not elementary (and it's a good exercise to try to prove this in each case by compactness):
- A tree is a connected acyclic graph.
- A tree is a partially ordered set with a minimal element, such that for each element, the set of predecessors of that element is well-ordered.
- A tree is a directed graph with a specified vertex (the root), such that each vertex other than the root has exactly one outgoing edge, and the path formed by following these outgoing edges from each vertex eventually leads to the root.
You can find lots of relevant questions on this site by searching for "not elementary" or "not axiomatizable".
Best Answer
A set of formulas $\Sigma$ with free variables from $x = (x_1,\dots,x_n)$ is satisfiable if there is a structure $M$ and a tuple $a = (a_1,\dots,a_n)$ from $M$ such that $M\models \varphi(a)$ for every formula $\varphi(x)\in \Sigma$.
You're right that this is the same as replacing each of the variables $x_i$ with a new constant symbol $c_i$ and asking for the resulting theory to be satisfiable. Of course if you allow variables to occur both free and bound in a formula, you only replace the free instances! This is not hard to formalize.