because $p_i\in A(P_{l-1})$, the path $P_l$ is a maximum rainbow path starting in $p_i$ and ending in $p_t$.

By this construction, all paths $P_i$ end in the same vertex $p_t$, but no two different paths start in the same vertex. We now show that at least one of the paths $P_l$ must satisfy $\abs{A(P_l)\cap B(P_l)}\leq \epsilon n$. By way of contradiction, assume that for every $l\in \{0,\dotsc,k\}$, we have $$\abs{A(P_l)\cap B(P_l)} > \epsilon n\text.$$ For every path $P_l = (p_1,\dotsc,p_t)$, we define two sets $X_l$ and $Y_l$.

Let $X_l$ be the smallest set that, for every vertex $p_i\in {\Gamma_{\mathrm{new}}(p_t,P_l)}$, contains the triples $(p_i,p_{i+1},p_{i+2})$ and $(p_i,p_{i-1},p_{i-2})$, if those vertices are defined. Observe that $\abs{X_l\setminus X_{l-1}} \leq 4$, because the path $P_l$ is built from $P_{l-1}$ by a single rotation. Then, since $\abs{X_0} \leq 2t$, we get $$\abs{X_0\cup \dotsb\cup X_k} \leq 2t + 4k\text.$$ Now let $Y_l$ be the smallest set that, for every vertex $p_i \in A(P_l)\cap B(P_l)$, contains the triple $(p_{i-1},p_i,p_{i+1})$. If $p_i\in B(P_l)$, then $p_{i-1}\in {\Gamma_{\mathrm{new}}(p_t,P_l)}$, so we have $Y_l\subseteq X_l$.

Assuming that $n$ is large enough, we get $$\frac{\abs{X_0\cup \dotsb\cup X_k}}{\abs{Y_l}} < \frac{2t+4k}{\epsilon n} < 1+2/\epsilon\leq k\text.$$ Thus $k\abs{Y_l}> \abs{X_0\cup \dotsb \cup X_k}$. Since $Y_l\subseteq \abs{X_0\cup \dotsb \cup 