\documentclass[11pt]{article}
\usepackage{jeffe,handout,multicol,tikz,kgm}
\usepackage{graphicx}

\newcommand{\kgmcomment}[1]{}
\renewcommand{\gcd}{\mathrm{gcd}}

\begin{document}
\headers{Math378}{Homework 7}{Due Fri. Mar. 6, 2026}

%\makeatletter
%\def\@oddfoot{\hfill \tikz \node[draw] {over} ; }
%\makeatother

%\newcommand{\seq}[1]{\left\langle #1\right\rangle}

\newcommand{\RR}{\mathbb{R}}
\newcommand{\ZZ}{\mathbb{Z}}

\makeatletter
\def\@oddfoot{}
\makeatother

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

\begin{enumerate}


\item {} [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)$?

\item {} Find $r(C_3, C_4)$. 

\item {} Here, we show that $r(P_4, K_n) = 3(n-1) + 1$.  
\begin{enumerate}
	\item 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$.
	\item Prove that if $G$ is a graph in which every vertex has degree at least $3$, then $G$ contains $P_4$ as a subgraph.
	\item 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$?)
\end{enumerate}
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)$? 




\end{enumerate}
\end{document}
