with $c(S')\cap c(Q)=\emptyset$.

Because (P1) is violated, we have $V(Q)\cap R(P) = \emptyset$, and thus $$V(Q)\cap V(S') = \{q\}\text.$$ so $Q\cup S'$ is a rainbow path. As (P4) is violated, we have $$\begin{aligned}
    \abs{V(Q\cup S')} &=\abs{V(Q)}+\abs{V(S')}-1\\
    &= k + l-1\\
    &\geq t-\frac{a}{3} + \floor{(a-3-1/\epsilon)/2}-1\\
    &> t-\frac{a}{3} + \frac{a}{2} -\frac{1}{2\epsilon}- 3\\
    &> t\text.
  \end{aligned}$$ But by definition of $t$, there are no rainbow paths this long.

Thus Lemma \[lemma:no-paths\] suggests that we can prove Theorem \[thm:awesome\] in two steps. Under the assumption that $t\leq(3/4-\epsilon)n$:

-   Show that there is at least one nice maximum rainbow path $P$.

-   Then show that for this $P$, there is a rainbow path $Q$ violating Lemma \[lemma:no-paths\].

### Existence of nice maximum rainbow paths

In this section, we will prove that there are nice maximum rainbow paths. First, let us reiterate what it means for a rainbow path not to be nice. If $P$ is a rainbow path that is not nice, then we have $$\abs{R(P)}\leq n-t-1/\epsilon\text,$$ or, equivalently, $$\abs{R(P)^c} \geq n-(n-t-1/\epsilon) = t+1/\epsilon\text.$$ For any rainbow path, we have $\abs{V(P)}\leq t$, so we get $$\abs{R(P)^c\cap V(P)^c} = \abs{R(P)^c\setminus V(P)}\geq 1/\epsilon\text.$$ This means that there are at least $1/\epsilon$ vertices in $V(P)^c$ that have no 