Thread: graph 6

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

cheers!

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

(b) Firstly note that $\displaystyle r(P_4,P_4)>4$

Spoiler:

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

Then consider $\displaystyle 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 $\displaystyle a$ and suppose, without loss of generality, that two of its incident edges, $\displaystyle ab$ and $\displaystyle ac$, are red. Denote $\displaystyle d,e$ two remaining vertices. If any one of the edges $\displaystyle db$, $\displaystyle dc$, $\displaystyle eb$, $\displaystyle ec$ is red, then this edge together with $\displaystyle cab$ forms a red $\displaystyle P_4$. If they are all blue, then $\displaystyle dbec$ is a blue $\displaystyle P_4$. Thus, $\displaystyle r(P_4,P_4) = 5$