Find $R(P_4, K_4)$

Question

Find $R(P_4,K_4)$. I know that the answer is 10, but am confused as how to get to this answer. Does anyone have a good solution for this? I am really stuck on trying to find ramsey numbers and have just as much trouble with $K_4$ and $P_4$. I think I could use the fact that the connected components of a maximal $P_4$-free graph are all either a triangle ($C_3=K_3$) or stars (including the one-vertex and one-edge graphs).

Answer 1

Right, the fact which you mentioned, is useful to prove that $R(P_4,K_4)\le 10$. Indeed, consider any coloring of the edges of $K_{10}$ into red and blue colors. The red graph is partitioned into its connected components. Since it is $P_4$-free, each of these components is either a triangle (then the number of its edges equals the number of its vertices) or a star (then the number of its edges equals the number of its vertices minus one). Since all components cannot be triangles, at least one of them is a star. This observation implies that then the number of edges of the red graph is not bigger than the number of its vertices minus one, that is $0$. Therefore the blue graph has at least $|e(K_{10})|-9=38$ edges. On the other hand, Turán's theorem implies that any $K_4$-free subgraph on $10$ vertices has at most the number of edges in a complete tripartite graph $K_{4,3,3}$, which equals $33<38$.

To see that $R(P_4,K_4)>9$ consider the read and blue coloring of $K_9$ in which three disjoint triangles are colored red and the other edges are colored blue. Clearly, there are no red pats of length $P_4$. On the other hand, among any four distinct vertices of $K_9$ there are two belonging to a common red triangle, so the coloring contains no blue $K_4$.