$\S 1$. The class of connected graphs is not axiomatizable in first-order logic
As stated in the question, it is well known that the class of graphs is not first-order axiomatizable in the language of graphs. But what if we add more to the language? In other words, suppose $L$ is a first-order language containing a binary relation $R$ (for graphs), but possibly more. Can we construct an $L$-theory $T$ so that the models of $T$ are precisely connected graphs? Since $L$ contains other symbols, we have to say precisely what is meant by "a model of $T$ is a connected graph". The most natural meaning is: "if we take a model of $T$ and forget about all of the first-order structure except the interpretation of $R$, then we get a connected graph". Let's denote this process like this: If $A$ is an $L$-structure then $A{\upharpoonright}R$ is the $\{R\}$-structure obtained by only looking at the interpretation of $R$ (this is sometimes called a reduct). So the most natural way to understand the question is:
Is there an $L$-theory $T$ such that $\{A{\upharpoonright}R:A\models T\}$ is precisely the class of connected graphs?
So now that we have a precise question, I'll show that that there is no such theory $T$. The proof is basically the same. Suppose such a theory $T$ exists. Add two new constants $a,b$ to $L$, which produces a bigger languge $L'$. For any $n\geq 1$, let $\varphi_n$ be the $L'$-sentence saying there is no path from $a$ to $b$ of length at most $n$. Let $T'=T\cup\{\varphi_n:n\geq 1\}$. By our assumption, any finite subset of $T'$ has a model. To see this, fix $n\geq 1$. Consider the graph $G$ which is a path of length $n$. Then by our assumption there is $A\models T$ such that $A{\upharpoonright}R=G_n$. Make $A$ into an $L'$-structure $A'$ by interpreting $a$ and $b$ as the endpoints. Then $A'\models T\cup\{\varphi_k:k<n\}$.
Now, by the Compactness Theorem for First-Order Logic, $T'$ has a model $B$. So $B{\upharpoonright}R$ is not a connected graph, as witnessed by the interpretations of $a$ and $b$. But $B{\upharpoonright}L\models T$, which contradicts our assumptions.
$\S 2$. A failed attempt
Next I will make an attempt to formalize your tutor's idea, and see why it fails. As motivation, let's first observe a more obvious failed attempt at axiomatizing connected graphs:
$$
\forall x\forall y\bigg(x\neq y\rightarrow \exists n\geq 1\,\exists z_1\ldots z_n\big(x=z_1\wedge y=z_n\wedge \bigwedge_{k<n}R(y_k,y_{k+1})\big)\bigg)
$$
Although this sentence describes connectivity, it is not a first-order sentence because we have quantified over the number of variables used in the sentence, which is a no-no. What your tutor has done is try to disguise this quantification by viewing natural numbers as elements themselves and lists of variables as images of functions from natural numbers. But we have to make this rigorous, and the most natural way to do it is with sorts.
Let $L$ be a language with three sorts $V$, $N$, and $F$. I think of $V$ as the sort for vertices of graphs, $N$ as a sort for the natural numbers, and $F$ as a sort for functions from $N$ to $V$. In $L$ I have a binary relation $R$ on the $V$ sort (which I think of as the graph relation), a constant symbol $0$ in the $N$ sort (which I think of as the number $0$), a binary relation $<$ on the $N$ sort (which I think of as the ordering), and a unary function $s$ on the $N$ sort (which I think of as the successor function).
Side remark: The three sorts are motivated by the objects your tutor has attempted to quantify over: vertices, natural numbers, and functions from vertices to natural numbers. Part of the rules of first-order logic require that quantifiers only quantify over elements of structures, not higher order things like subsets and functions, or meta-things like natural numbers. So anything we want to quantify over has to be given a sort.
Let us continue. I will now write down a variation of the proposed axiom that looks like it will describe connected graphs. It's basically the same as what your tutor wrote, but I omit the confusing and/or superfluous parts. In the following sentence, $x,y$ are variables in the $V$ sort, $f$ is in the $F$ sort, and $k,n$ in the $N$ sort (I'm omitting the specification of this in the sentence itself to make things easier to read).
$$
\forall x \forall y \bigg(x\neq y\rightarrow \exists f \exists n \big(f(0)=x\wedge f(n)=y\wedge \forall k(0\leq k<n\rightarrow R(f(k),f(s(k)))\big)\bigg)
$$
So does it work? We might be optimistic since certainly I can take any connected graph and turn it into an $L$-structure satisfying this sentence. Specifically, let $G$ be a connected graph and consider the $L$-structure $A$ where $(V,R)$ is interpreted as $G$, $(N,<,0)$ is interpreted as $(\omega,<,0)$, and $F$ as all functions from $\omega$ to the vertex set of $G$. For any distinct $x$, $y$ in $G$, there is a path from $x$ to $y$, and so there is a function as in the sentence above.
The problem is the other direction, and the main point is that $(N,<,0)$ doesn't have to be interpreted as $(\omega,<,0)$. This is what I mean by saying "you can't quantify over natural numbers". You can quantify over elements that you might think are natural numbers in some structure, but not necessarily in others. For example, consider the graph $G$ that looks like two disjoint copies of $\mathbb{N}$ and edges between any element and its successor. This graph is disconnected but I can make it into an $L$-structure satisfying the sentence above. Interpret $(V,R)$ as $G$, and $(N,<,0)$ as the order $\omega+\omega^*$ (i.e., $\omega$ followed by $\omega$ in reverse order) with $0$ interpreted as the least element. $F$ is the set of functions from $\omega+\omega^*$ to the vertices in $G$. For any distinct vertices $x$ and $y$, I can find a function as above. If $x$ and $y$ are in the same copy of $\mathbb{N}$ then it's easy. On the other hand, if they are in different copies then send $\omega$ to the interval $[x,\infty)$ and send $\omega^*$ to $[y,\infty)$.
Side Remark. There are dumber ways to show that the sentence above won't work because it doesn't specify anything about $R$ being a graph relation, or $<$ being a linear order, etc, etc, etc. So you can add all of this in, and the same counterexample goes through. You might try to add more axioms or more symbols to try to "force" the interpretation of $(N,<)$ to be $\omega$. But it won't work and $\S 1$ proves it.
Transfinite induction is not necessary, because all paths in graphs are finite.
Suppose that our graph has no cycles. Let $(u,v)$ be an arbitrary edge. Then color each vertex $w$:
- blue, if there is a $v-w$ walk in the graph (equivalently, if there is a $v-w$ path);
- red, otherwise.
For any edge $(x,y)$, if $x$ is blue, then appending $y$ to the $v-x$ walk gives a $v-y$ walk, so $y$ is also blue. Therefore there are no blue-red edges.
If $u$ is blue, then the implied $v-u$ path can be turned into a cycle by adding a final step along edge $(u,v)$. We assumed there were no cycles, so $u$ must instead be red, and therefore $(u,v)$ is a red-blue edge.
This proves that every $(1)$-acyclic graph is $(2)$-acyclic.
The inductive argument in the question is not too different - it is more complicated to say "color $w$ blue if there is a $v-w$ walk and red if there is a $w-v$ walk" but it achieves the same purpose and that's what every step of the induction is doing: after step $k$, we will have done this for all walks of length less than $k$.
In fact, after we have done all the finite steps, we have colored every vertex we are going to color recursively (and so nothing happens in steps $\omega+1$, $\omega+2$, and so forth). This is why transfinite induction is not necessary. If there are still any doubts, here is a quick proof sketch: suppose that vertex $y$ gets colored blue in step $\omega+1$, due to an edge $(x,y)$ where $x$ was blue after the limit step $\omega$. Then $x$ was actually colored blue in some finite step $k$, because the coloring in step $\omega$ is just the union of colorings done in the finite steps. However, that means we would have already colored $y$ blue in step $k+1$: we do not need to wait infinitely long to color $y$. (The case for red vertices is symmetric.)
The vertices that need to be colored by a separate rule are those with no incoming edge from any blue vertex and no outgoing edge to any red vertex. I color them all red, but it's fine to also color them all blue: all we want is that there is no blue-red edge between two of them.
Note, however, that these are not precisely "vertices outside $E$'s connected component". I assume this means "weakly connected component" because the strongly connected components are all isolated vertices. But there can be vertices in the same weakly connected component which the induction would not color: for example, a vertex with no incoming edges, and an outgoing edge to $v$.
Best Answer
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):
You can find lots of relevant questions on this site by searching for "not elementary" or "not axiomatizable".