Degree comparison of $P(Q(x))$ and $R(S(x))$ implies that $q = \deg Q$ divides $\deg S = s$. We will show that $S(x) = T(Q(x))$ for some polynomial $T$. Then $P(Q(x)) = R(S(x)) = R(T(Q(x)))$, so the polynomial $P(t) - R(T(t))$ vanishes upon substitution $t = S(x)$; it therefore vanishes identically, as desired.

Choose the polynomials $T(x)$ and $M(x)$ such that
$$S(x) = T(Q(x)) + M(x), \qquad (*)$$
where $\deg M$ is minimised; if $M = 0$, then we get the desired result. For the sake of contradiction, suppose $M \ne 0$. Then $q \nmid m = \deg M$; otherwise, $M(x) = \beta Q(x)^{m/q} + M_1(x)$, where $\beta$ is some number and $\deg M_1 < \deg M$, contradicting the choice of $M$. In particular, $0 < m < s$ and hence $\deg T(Q(x)) = s$.

Substitute now (*) into $R(S(x)) - P(Q(x)) = 0$; let $\alpha$ be the leading coefficient of $R(x)$ and let $r = \deg R(x)$. Expand the brackets to get a sum of powers of $Q(x)$ and other terms including powers of $M(x)$ as well. Amongst the latter, the unique term of highest degree is $\alpha r M(x) T(Q(x))^{r-1}$. So, for some polynomial $N(x)$,
$$N(Q(x)) = \alpha r M(x) T(Q(x))^{r-1} + \text{a polynomial of lower degree.}$$
This is impossible, since $q$ divides the degree of the left-hand member, but not that of the right-hand member.

Alternative solution:

All polynomials in the solution have real coefficients. As usual, the degree of a polynomial $f(x)$ is denoted $\deg f(x)$.

Of all pairs of polynomials $P(x), R(x)$, satisfying the conditions in the statement, choose one, say, $P_0(x), R_0(x)$, so that $P_0(Q(x)) = R_0(S(x))$ has a minimal (positive) degree. We will show that $\deg R_0(x) = 1$, say, $R_0(x) = \alpha x + \beta$ for some real numbers $\alpha \neq 0$ and $\beta$, so $P_0(Q(x)) = \alpha S(x) + \beta$. Hence $S(x) = T(Q(x))$ for some polynomial $T(x)$.

Now, if $P(x)$ and $R(x)$ are polynomials satisfying $P(Q(x)) = R(S(x))$, then $P(Q(x)) = R(T(Q(x)))$. Since $Q(x)$ is not constant, it takes infinitely many values, so $P(x)$ and $R(T(x))$ agree at infinitely many points, implying that $P(x) = R(T(x))$, as required.

It is therefore sufficient to solve the problem in the particular case where $F(x) = P(Q(x)) = R(S(x))$ has a minimal degree. Let $d = \gcd(\deg Q(x), \deg S(x))$ to write $\deg Q(x) = ad$ and $\deg S(x) = bd$, where $\gcd(a, b) = 1$. Then $\deg P(x) = bc$, $\deg R(x) = ac$ and $\deg F(x) = abcd$ for some positive integer $c$. We will show that minimality of $\deg F(x)$ forces $c = 1$, so $\deg P(x) = b$, $\deg R(x) = a$ and $\deg F(x) = abd$. The conditions $a = \deg R(x)$ divides $\deg P(x) = b$ and $\gcd(a, b) = 1$ then force $a = 1$, as stated above.

We are now in a position to prove that $c = 1$. Suppose, if possible, that $c > 1$. By the lemma, there exist monic polynomials $U(x)$ and $V(x)$ of degree $b$ and $a$, respectively, such that
$$\deg (P(x) - U(x)^c) < (c-1)b \quad \text{and} \quad \deg (R(x) - V(x)^c) < (c-1)a.$$
Then
$$\deg (F(x) - U(Q(x))^c) = \deg (P(Q(x)) - U(Q(x))^c) < (c-1)abd,$$
$$\deg (F(x) - V(S(x))^c) = \deg (R(S(x)) - V(S(x))^c) < (c-1)abd,$$
$$\text{so } \deg (U(Q(x))^c - V(S(x))^c) = \deg \left( (F(x) - V(S(x))^c) - (F(x) - U(Q(x))^c) \right) < (c-1)abd.$$
On the other hand,
$$U(Q(x))^c - V(S(x))^c = (U(Q(x)) - V(S(x))) (U(Q(x))^{c-1} + \dots + V(S(x))^{c-1}).$$
By the preceding, the degree of the left-hand member is (strictly) less than $(c-1)abd$ which is precisely the degree of the second factor in the right-hand member. This forces $U(Q(x)) = V(S(x))$, so $U(Q(x)) = V(S(x))$ has degree $abd < abcd = \deg F(x)$ — a contradiction. Consequently, $c = 1$. This completes the argument and concludes the proof.