that they have some nice properties.

\[prop:long-paths\] If $P$ is nice maximum rainbow path, then for any vertex $r\in R(P)$ and any set $F$ of colors, there is a rainbow path $Q$ starting in $r$ in the subgraph induced by $R(P)$ such that $\abs{V(Q)} = \floor{(a-\abs{F}-1/\epsilon)/2}$ and $c(Q)\cap (F \cup c(P)) = \emptyset$.

Let $k=\floor{(a-\abs{F}-1/\epsilon)/2}$. We construct a series of rainbow paths $Q_1,\dotsc,Q_{k}$ starting in $r$ and using only vertices in $R(P)$, such that for every $i \in [k]$, we have $\abs{V(Q_i)} = i$. Furthermore, we shall make sure that no $Q_i$ uses colors in $F\cup c(P)$. Clearly, the path $Q_k$ will have the desired properties.

Let $Q_1 = (r)$ and define $Q_{i+1}$ in terms of $Q_i$ as follows. By construction, $Q_i$ starts in $r$ and ends in some vertex $v\in R(P)$. If there is a vertex $u\in {\Gamma_{\mathrm{new}}(v,P)} \cap R(P)\setminus V(Q_i)$ such that $$c(u,v){\not\in}c(Q_i)\cup F\text,$$ then we can simply define $Q_{i+1}$ to be $Q_i\cup(v,u)$. Hence it is enough to prove that $\abs{{\Gamma_{\mathrm{new}}(v,P)} \cap R(P) \setminus V(Q_i)} > \abs{c(Q_i)\cup F}$.

Because $i< k$, we have $$\abs{c(Q_i)\cup F} \leq \abs{c(Q_i)} + \abs{F} < k + \abs{F}\text.$$ Since $P$ is nice, we have $\abs{V(P)^c\setminus R(P)} < 1/\epsilon$, and as $v\in R(P)$, we 