Rephrasing, given $G$ and $n$ you're looking for the smallest subset $V' \subseteq V$ of the vertices of $G$ such that the subgraph $G'$ induced by $V'$ has a vertex colouring $\phi$ on $n$ colours for which every pair of colours $c \neq d$ has an edge between those colours and there is no edge between two vertices of the same colour.

For your particular case of interest, when $n$ is odd we can colour a subchain of $\mathbb{Z}_G$ in the sequence of colours of an Eulerian path on $K_n$ to find that $\varepsilon_n(\mathbb{Z}_G) = \binom{n}{2} + 1$. When $n$ is even, $0 \le \varepsilon_n(\mathbb{Z}_G) - \binom{n}{2} - 1 \le n - 2$ by a similar argument (a near-Eulerian path fails to cover $\frac{n-2}{2}$ edges), with equality on the lower bound only for $n=2$. I think it probably works to argue that the upper bound is tight because initially each vertex has an odd number of edges unvisited and each path can only reduce the number of vertices with an odd number of edges unvisited by two, so that $\frac{n}{2}$ separate paths are required.

Rephrasing, given $G$ and $n$ you're looking for the smallest subset $V' \subseteq V$ of the vertices of $G$ such that the subgraph $G'$ induced by $V'$ has a vertex colouring $\phi$ on $n$ colours for which every pair of colours $c \neq d$ has an edge between those colours and there is no edge between two vertices of the same colour.

For your particular case of interest, when $n$ is odd we can colour a subchain of $\mathbb{Z}_G$ in the sequence of colours of an Eulerian path on $K_n$ to find that $\varepsilon_n(\mathbb{Z}_G) = \binom{n}{2} + 1$. When $n$ is even, $\varepsilon_n(\mathbb{Z}_G) = \binom{n}{2} + \frac{n-2}{2} + 1$ by a similar argument, as bof correctly pointed out in a comment improving the earlier claim of this answer: the addition of $\frac{n-2}{2}$ edges is necessary and sufficient for an Eulerian trace to exist.