Directions: Solve the following problems. All written work must be your own. See the course syllabus for detailed rules.

1. [2.3.14] In class, we showed that $r(3,3,3)\le 17$. What upper bound do our techniques give on $r(3,3,3,3)$?
2. Find $r(C_3,C_4)$.

3. Here, we show that $r(P_4,K_n)=3(n-1)+1$.

   1. With $s=3(n-1)$, find a blue/red coloring of the edges of $K_s$ that avoids a blue copy of $P_4$ and a red copy of $K_n$.
   2. Prove that if $G$ is a graph in which every vertex has degree at least $3$, then $G$ contains $P_4$ as a subgraph.
   3. With $s=3(n-1)+1$, prove that every blue/red coloring of the edges of $K_s$ contains a blue copy of $P_4$ or a red copy of $K_n$. (Hint: if every vertex in $G$ has at least $3$ blue neighbors, then apply part (b) to the blue subgraph. Otherwise, $G$ has a vertex $u$ with blue degree at most $2$. How large is the red neighborhood of $u$?)

   Comment: the argument above can be generalizes to longer paths (and even to other graphs called trees). Do you see how it generalizes to give $r(P_5,K_n)$?