(Previous answer was completely wrong.)

Denote by $p_k$ the probability that at least $k$ vertices remain. Then the expectation is of course $\sum p_i$. I claim that $p_k=\frac{(n-k+1)! (n-k)!}{(n-2k+1)! n!}$, it is about $e^{-k^2/n}$ and thus the asymptotics is the same as for $\sum e^{-k^2/n}\sim \int_0^\infty e^{-x^2/n}dx=\frac12 \sqrt{\pi n}$.

Now the claim. We need to prove that the probability that exactly $k$ vertices remain equals $p_k-p_{k+1}$. It is convenient to replace the graph to the cycle with $n+1$ vertices (it becomes a path after the first move). Fix the last removed vertex $v_0$, and the remained set $A$, $|A|=k$, $A$ should be independent and contain at least one neighbor of $v_0$. The probability of this event (fixed $v_0$, $A$) equals $\frac1{\binom{n+1}{k+1}(k+1)}$. It has to be multiplied by the number of ways to choose $v_0$ and $A$. There are $n+1$ ways for $v_0$ and $\binom{n-k+1}{k}-\binom{n-k-1}{k}$ ways to choose $A$ after that. Remained calculations are straightforward.

[Previous answer was completely wrong.]

Denote by $p_k$ the probability that at least $k$ vertices remain. Then the expectation is of course $\sum p_i$. I claim that $p_k=\frac{(n-k+1)! (n-k)!}{(n-2k+1)! n!}$, it is about $e^{-k^2/n}$ and thus the asymptotics is the same as for $\sum e^{-k^2/n}\sim \int_0^\infty e^{-x^2/n}dx=\frac12 \sqrt{\pi n}$. I do not know whether the sum $\sum p_k$ may be simplified.

Now the claim. We need to prove that the probability that exactly $k$ vertices remain equals $p_k-p_{k+1}$. It is convenient to replace the graph to the cycle with $n+1$ vertices (it becomes a path after the first move). Fix the last removed vertex $v_0$, and the remained set $A$, $|A|=k$, $A$ should be independent and contain at least one neighbor of $v_0$. The probability of this event (fixed $v_0$, $A$) equals $\frac1{\binom{n+1}{k+1}(k+1)}$. It has to be multiplied by the number of ways to choose $v_0$ and $A$. There are $n+1$ ways for $v_0$ and $\binom{n-k+1}{k}-\binom{n-k-1}{k}$ ways to choose $A$ after that. It remains to note that $$\frac{\binom{n-k+1}{k}}{\binom{n+1}{k+1}(k+1)}=p_k,\,\, \frac{\binom{n-k-1}{k}}{\binom{n+1}{k+1}(k+1)}=p_{k+1}. $$

Denote the answer by $f(n)$. We have $f(0)=0,f(1)=f(2)=1$, $f(n)=\frac1n\sum_{k=1}^n (f(k-1)+f(n-k))$ (by considering the first removed vertex). That is, $\frac n2f(n)=f(0)+\dots+f(n-1)=f(n-1)+\frac{n-1}2f(n-1)=\frac{n+1}2f(n-1)$, $f(n)=\frac{n+1}n f(n-1)$ for $n\geqslant 3$. Hence $f(n)=(n+1)/3$ by induction.

(Previous answer was completely wrong.)

Denote by $p_k$ the probability that at least $k$ vertices remain. Then the expectation is of course $\sum p_i$. I claim that $p_k=\frac{(n-k+1)! (n-k)!}{(n-2k+1)! n!}$, it is about $e^{-k^2/n}$ and thus the asymptotics is the same as for $\sum e^{-k^2/n}\sim \int_0^\infty e^{-x^2/n}dx=\frac12 \sqrt{\pi n}$.

Now the claim. We need to prove that the probability that exactly $k$ vertices remain equals $p_k-p_{k+1}$. It is convenient to replace the graph to the cycle with $n+1$ vertices (it becomes a path after the first move). Fix the last removed vertex $v_0$, and the remained set $A$, $|A|=k$, $A$ should be independent and contain at least one neighbor of $v_0$. The probability of this event (fixed $v_0$, $A$) equals $\frac1{\binom{n+1}{k+1}(k+1)}$. It has to be multiplied by the number of ways to choose $v_0$ and $A$. There are $n+1$ ways for $v_0$ and $\binom{n-k+1}{k}-\binom{n-k-1}{k}$ ways to choose $A$ after that. Remained calculations are straightforward.