First order logic to describe a finite tree I am reading the paper Describing Graphs: a First Order Approach to Graph Canonization.
In Corollary 1.8.2, the paper says

Let $TREES$ be the set of finite trees. Then $vc(TREES)=2$.

where $vc(TREES)=\max_n vc(TREES, n)$ and define $vc(TREES, n)$ to be the minimum $k$ such that $\mathcal{C}_k$ ($k$-variable first order logic with counting) characterizes the graphs in $TREES$ with at most $n$ vertices.
Assume there is a path (belong to the set $TREES$) of length $r$ starting from $x$ and ending with $y$. Does this corollary mean such a path of length $r$ can be written in $\mathcal{C}_2$? However, I don't think a path of length $r>1$ can be written in $\mathcal{C}_2$ and Proposition 1.5.2 in this paper says such a path can be written in $\mathcal{L}_3$. I am really confused by this inconsistency.
 A: As an illustration, here is how we can characterize the graph $P_n$ in $\mathcal C_2$.
First, we can express the degree sequence of a graph. The statement $$D(i,j) \equiv (\exists!i\, x_1)((\exists!j\, x_2) E(x_1, x_2))$$ says that there are exactly $i$ vertices of degree $j$. We don't fully characterize $P_n$ by saying that it has $n$ vertices: $2$ vertices of degree $1$ and $n-2$ vertices of degree $2$. However, it will help for the next step.
Second, we can recursively define the statement $L_k(x_i)$ meaning that the closest leaf to $x_i$ is at distance $k$. We have:

*

*$L_0(x_1) \equiv (\exists!\, x_2)(E(x_1, x_2))$ (this just says $x_1$ is a leaf).

*Recursively, $L_k(x_1) \equiv \neg L_{k-1}(x_1) \land (\exists x_2)(E(x_1, x_2) \land L_{k-1}(x_2))$.

The exact characterization of $P_n$ depends on whether $n$ is even or odd. $P_{2k}$ is characterized by giving its degree sequence, together with $$(\exists!2\,x_1)(\exists!\,x_2)(L_{k-1}(x_1) \land L_{k-1}(x_2) \land E(x_1, x_2))$$
That is, there are two adjacent vertices at distance $k-1$ from a leaf. For $P_{2k+1}$, we could instead say
$$
   (\exists!\,x_1)(\exists!2\,x_2)(L_{k-1}(x_2) \land E(x_1, x_2))
$$
That is, there is a vertex with two neighbors at distance $k-1$ from a leaf.
(In both cases, knowing the vertex degrees tells us that the two paths to a leaf we find can't possibly merge, which gives us a path of length $n-1$ total. Then, knowing the total number of edges from the vertex degrees, we know that there are no other edges we haven't identified.)

What we do for trees in general is a bit harder to do explicitly, which is why Theorem 1.8.1 is proven using pebble games instead. But the idea above is very closely related to the idea of "vertex refinement" used in that proof. We start by identifying the vertices of $P_n$ just by their degrees: there's two vertices of degree $1$ and $n-2$ vertices of degree $2$. Then, we can distinguish the $n-2$ vertices of degree $2$ further: two of them have neighbors of degree $1$, and the rest don't. Among the $n-4$ unclassified vertices, two have neighbors which have neighbors of degree $1$, and so on. Eventually, we can distinguish all the vertices, up to the automorphism of $P_n$ which swaps the two ends.
