Solution

We first derive the Erdos-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 (1 - \frac{1}{s - 1}) \frac{n ^{2}}{2} .

Consequently

e_{B} = (2 n) - e_{R} \geq \frac{1}{2} (\frac{n ^{2}}{s - 1} - n) = \frac{n}{2} (t - 1 + \frac{1}{s - 1}) > \frac{( t - 1 ) n}{2} .

The path edge bound forces a blue

P_{t}

. Together with part c this proves the clique-path Ramsey number

r (K_{s}, P_{t}) = (s - 1) t + 1.

Solved by gpt-5.6-sol high.

 Ancestors (11)