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

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

\begin{document}
\headers{Math378}{Homework 6}{Due Fri. Feb 27, 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}}
\renewcommand{\emptyset}{\varnothing}

\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 {} Graphs, Subgraphs, and Isomorphism.
\begin{enumerate}
	\item Let $G$ be a graph.  The \emph{neighborhood} of a vertex $v\in V(G)$, denoted $N(v)$, is the set of all vertices adjacent to $v$.  Show that the $4$-cycle $C_4$ is not a subgraph of $G$ if and only if for all distinct $u,v\in V(G)$, we have $|N(u) \cap N(v)| \le 1$.  Note: a vertex $w$ in $N(u) \cap N(v)$ is a \emph{common neighbor} of $u$ and $v$.
	
	\item Recall that the Petersen graph is the graph whose vertices are the $2$-element subsets of $\{1,2,3,4,5\}$ where $u$ and $v$ are adjacent if and only if $u\cap v = \emptyset$.  Use part (a) to show that the Petersen graph does not contain a $4$-cycle.
	
	\item Use part (b) to give a short proof that the graph $H$ below is \emph{not} isomorphic to the Petersen graph.
	\begin{center}
	\begin{tikzpicture}[vertex/.style={inner sep=2pt,fill=black!50,circle,minimum size=0.5ex},baseline=0pt,scale=0.75]
		\foreach \n in {0,...,4}
		{{
			\pgfmathsetmacro{\ang}{90 + 72*\n}
			\node[vertex] at (\ang:2cm) (U\n) {} ;
			\node[vertex] at (\ang:1cm) (V\n) {} ;
		}}
		
		\foreach \n in {0,...,4}
		{{
			\pgfmathsetmacro{\succ}{int(mod(\n + 1, 5))}
			\draw (U\n) -- (U\succ) ;
			\draw (V\n) -- (V\succ) ;
			\draw (U\n) -- (V\n) ;
		}}
	\end{tikzpicture}
	\end{center}
\end{enumerate}

\item {} [2.3.2] Suppose that $r(4,5) = 25$.  Let $G$ be a copy of $K_{25}$ in which each edge is colored red or blue.  Prove that $G$ either contains a monochromatic copy of $K_5$ (red or blue), or $G$ contains both a red copy and a blue copy of $K_4$.

\item {} [2.3.8] Prove that $r(3,4) > 8$. 




\end{enumerate}
\end{document}
