more than $a$ new neighbors in $V(P)^c$.

\[cons:no-cycles\] Suppose that there are no nice maximum rainbow paths. Then there are no rainbow cycles of length $t$.

Suppose that $C$ is such a cycle. Then removing any edge $e\in E(C)$ from $C$, we get a maximum rainbow path $P=C-e$, with $V(P)=V(C)$.

By assumption, this maximum rainbow path cannot be not nice, so there is a vertex $v \in V(C)^c$ such that at least $\abs{{\Gamma_{\mathrm{new}}(v,P)}} - a\geq n-t-a$ new neighbors of $v$ are in $V(C)$. Since, for large enough $n$, we have $n-t-a\geq 2$, at least one of those neighbors, call it $u$, is such that $c(u,v)\neq c(e)$. So $c(u,v){\not\in}c(P+e) = c(C)$.

Let $u'$ be a vertex adjacent to $u$ on $C$. Then $(C-\{u,u'\}) \cup (u,v)$ is a rainbow path of length $t$. This contradicts the definition of $t$.

Suppose that there are no nice maximum rainbow paths, and let $P = (p_1,\dotsc,p_t)$ be a maximum rainbow path. Then for every vertex $p_i\in A(P)\cap B(P)$ we have $c(p_1,p_{i+1}) = c(p_{i-1},p_t)$.

Assume by way of contradiction that there is a vertex $p_i \in A(P)\cap B(P)$ such that $c(p_1,p_{i+1}) \neq c(p_{i-1},p_t)$. By definition, $c(p_1,p_{i+1}){\not\in}c(P)$ and $c(p_t,p_{i-1}){\not\in}c(P)$, so the cycle $$C = (p_1,\dotsc,p_{i-1},p_t,p_{t-1},\dotsc,p_{i+1},p_1)$$ shown in 