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.