$c \geq min(k,q) \quad \textrm{and} \quad q < k$

Here the paths look like:

$$P'_{3} = y_{1}, \ldots y_{q},y_{q+1} \ldots y_{k},b,y_{k+1} \ldots y_{m}$$

$$P_{2} = x_{1}, \ldots x_{q}, b, x_{q+1}, \ldots x_{m}$$

From the conditions on P₂, b < x_q+1. But x_q+1=y_q+1 from the condition on c, so b < y_q+1, giving that P'₃ > P₂.