1. ## graph 6

(a) Prove that if $F$ and $H$ are graphs of order m and n, respectively, then $r(F,H) \leq r(m, n)$.
(b) Determine $r(P_{4}, P_{4})$.

2. cheers!

(a) Every graph $F$ of order $m$ is a subgraph of $K_m$ and Every graph $H$ of order $n$ is a subgraph of $K_n$. Let $p = r(m,n)$. Then every blue/red coloured $K_p$ contains a blue $K_m$ or a red $K_n$, so it contains a blue subgraph $F$ or a red subgraph $H$. This means that $r(F,H) \leq r(m,n)$.

(b) Firstly note that $r(P_4,P_4)>4$
Spoiler:

Colour one triangle of $K_4$ with red and the rest of edges blue. Is there a red path $P_4$ or a blue path $P_4$ in such coloured graph?

Then consider $K_5$ coloured with blue and red. Each vertex must have at least two red incident edges or at least two blue incident edges. Pick one vertex $a$ and suppose, without loss of generality, that two of its incident edges, $ab$ and $ac$, are red. Denote $d,e$ two remaining vertices. If any one of the edges $db$, $dc$, $eb$, $ec$ is red, then this edge together with $cab$ forms a red $P_4$. If they are all blue, then $dbec$ is a blue $P_4$. Thus, $r(P_4,P_4) = 5$