X_k}$, and because there are $k$ sets $Y_l$ altogether, this means that there are two sets $Y_i$ and $Y_j$ that intersect, say in the triple $(u,v,w)$. But if we write $P_i = (p_1,\dotsc,p_t)$ and $P_j=(p_1',\dotsc,p_{t-1}',p_t)$, then either $c(p_1,w)\neq c(u,p_t)$ or $c(p_1',w)\neq c(u,p_t)$, contradicting the result above stating that for any maximum rainbow path $P=(p_1,\dotsc,p_t)$, every vertex $p_i\in A(P)\cap B(P)$ satisfies $c(p_1,p_{i+1}) = c(p_{i-1},p_t)$.

Now we are ready to prove the following.

There exists at least one nice maximum rainbow path.

We may assume that there are no nice maximum rainbow paths.

Then, by Proposition \[cons:a-b\], there is a maximum rainbow path $P$ with $\abs{A(P)\cap B(P)}\leq \epsilon n$. Writing $A$ and $B$ for $A(P)$ and $B(P)$ respectively, this means that $$\abs{A \cup B} = \abs{A} + \abs{B} - \abs{A\cap B} \geq 2n-2t - \epsilon n\text.$$ Observe that every vertex in $A\cup B$ can have at most one new neighbor in $V(P)^c$, as otherwise we would get a rainbow path of length $t$.

Now suppose that $r$ is a vertex in $V(P)^c$ such that $$\abs{{\Gamma_{\mathrm{new}}(r,P)}\cap V(P)} \geq {\Gamma_{\mathrm{new}}(r,P)}-a\geq n-t-a\text.$$ For brevity, let us write $X = {\Gamma_{\mathrm{new}}(r,P)}\cap V(P)$. Then, using $\abs{A \cup B \cup X}\leq t$, $$\begin{aligned}
    \abs{(A \cup B) \cap X}& 