I have found an "algorithm" that seems to work every time but to me it seems more of a "how to make every subgraph from this particular graph" rather than a rigorous proof.
I.e. to go from complement of $C_v$ to complement of $C_{v-1}$ you take a vertex, let's say $x$ and erase it along with all edges adjacent to it. Finally erase the edge joining vertices $x-1$ and $x+1$ (if labelled with the standard labelling).
Indeed you are right.
If in a graph $\bar{C}_n$ remove, for example, vertex $v_n$ and edge $v_{n-1}v_1$, then we get a graph $G\cong \bar{C}_{n-1}$. (We denote the complement to a graph $\Gamma$ by the symbol $\bar{\Gamma}$)
In order to prove this we reason as follows. We have $V(G)=\{v_1,\ldots,v_{n-1}\}$.
The graph $G$ has no edges $v_1v_2,\ldots,v_{n-2}v_{n-1}$ and $v_1v_{n-1}$ but it has all edges $v_iv_j$, $j\neq i+1$ and if $i=1$ then $j\neq n-1$. This means that $G\cong \bar{C}_{n-1}$.