= Solution
We first derive the <Erdős-Gallai path edge bound> from part b. If an $n$-vertex graph has no path of length $t$, then
$$
e(G)\leq\frac{(t-1)n}{2}.
$$
Induct on $n$, component by component. A component with at most $t$ vertices satisfies the bound trivially. A larger connected component cannot have minimum degree at least $t/2$ by part b, so delete a vertex of degree less than $t/2$ and apply induction; the integer degree removed is at most $(t-1)/2$, which preserves the bound.
Now set
$$
n=(s-1)t+1
$$
and consider a red-blue colouring of $K_n$. If there is no red $K_s$, part a with $r=s-1$ gives
$$
e_R\leq\left(1-\frac1{s-1}\right)\frac{n^2}{2}.
$$
Consequently
$$
\begin{aligned}
e_B
&=\binom n2-e_R\\
&\geq\frac12\left(\frac{n^2}{s-1}-n\right)\\
&=\frac n2\left(t-1+\frac1{s-1}\right)
>\frac{(t-1)n}{2}.
\end{aligned}
$$
The path edge bound forces a blue $P_t$. Together with part c this proves the <clique-path Ramsey number>
$$
\boxed{r(K_s,P_t)=(s-1)t+1.}
$$
Back to article page
