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

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

\begin{document}
\headers{Math378}{Quiz 6}{Wed. Mar 4, 2026}
\setlength{\columnseprule}{0.4pt}

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

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

\newcommand{\compicon}%
{%
	\begin{tikzpicture}[scale=0.15]%
		\draw[double] (0,0) rectangle (1,1) ;
		\begin{scope}[yshift=-5pt]
			\draw (-0.5, -0.5) rectangle (1.5, 0) ;
		\end{scope}
	\end{tikzpicture}
}

\makeatletter
\def\@oddfoot{}
\makeatother

\noindent
\hfill Name: \underline{\hspace{3.5in}} 

\noindent
\textbf{Directions:} Show all work.  

\begin{enumerate}

\item\ppoints{3}{2} Let $G$ be the Petersen graph.  Recall that $V(G)$ is the set of $2$-element subsets of $\{1,2,3,4,5\}$ with $uv\in E(G)$ if and only if $u$ and $v$ are disjoint.
\begin{center}
\tikzstyle{vertex}=[circle,inner sep=1pt,fill=black!30]
\begin{tikzpicture}[rotate=90,scale=0.5]
	\foreach \n in {0,...,4}
	{{
		\pgfmathsetmacro{\ang}{int(72*\n)}
		\node[vertex] (U\n) at (\ang:2cm) {} ;
		\node[vertex] (V\n) at (\ang:1cm) {} ;
	}}
	
	\foreach \n in {0,...,4}
	{{
		\pgfmathsetmacro{\outersucc}{int(mod(\n + 1, 5))}
		\pgfmathsetmacro{\innersucc}{int(mod(\n + 2, 5))}
		
		\draw (U\n) -- (U\outersucc) (V\n) -- (V\innersucc) (U\n) -- (V\n) ;
	}}
\end{tikzpicture}
\end{center}

\begin{enumerate}
	\item Is $G$ bipartite?  Prove your answer is correct.
	\vfill
	
	\item Recall that $P_n$ is the path with $n$ vertices.  Let $k$ be the maximum integer such that $P_k$ is a subgraph of $G$.  Determine $k$ and find a copy of $P_k$ as a subgraph of $G$.  No proof required.
\begin{center}
\tikzstyle{vertex}=[circle,inner sep=1pt,fill=black!30]
\begin{tikzpicture}[rotate=90,scale=0.5]
	\foreach \n in {0,...,4}
	{{
		\pgfmathsetmacro{\ang}{int(72*\n)}
		\node[vertex] (U\n) at (\ang:2cm) {} ;
		\node[vertex] (V\n) at (\ang:1cm) {} ;
	}}
	
	\foreach \n in {0,...,4}
	{{
		\pgfmathsetmacro{\outersucc}{int(mod(\n + 1, 5))}
		\pgfmathsetmacro{\innersucc}{int(mod(\n + 2, 5))}
		
		\draw (U\n) -- (U\outersucc) (V\n) -- (V\innersucc) (U\n) -- (V\n) ;
	}}
\end{tikzpicture}
\end{center}
	\vspace{3cm}
	
	\item Let $t$ be the maximum integer such that $P_t$ is an \emph{induced} subgraph of $G$.  Determine $t$ and find a copy of $P_t$ as an \emph{induced} subgraph of $G$.  No proof required.
\begin{center}
\tikzstyle{vertex}=[circle,inner sep=1pt,fill=black!30]
\begin{tikzpicture}[rotate=90,scale=0.5]
	\foreach \n in {0,...,4}
	{{
		\pgfmathsetmacro{\ang}{int(72*\n)}
		\node[vertex] (U\n) at (\ang:2cm) {} ;
		\node[vertex] (V\n) at (\ang:1cm) {} ;
	}}
	
	\foreach \n in {0,...,4}
	{{
		\pgfmathsetmacro{\outersucc}{int(mod(\n + 1, 5))}
		\pgfmathsetmacro{\innersucc}{int(mod(\n + 2, 5))}
		
		\draw (U\n) -- (U\outersucc) (V\n) -- (V\innersucc) (U\n) -- (V\n) ;
	}}
\end{tikzpicture}
	\vspace{3cm}

\end{center}
\end{enumerate}

\newpage

\item\ppoints{2}{2} Graph Ramsey Problems.
\begin{enumerate}
	\item Prove that $K_5 \not\to (P_5, P_5)$.
	\vfill
	
	\item Recall that $C_n$ is the $n$-vertex cycle.  Use the fact that $K_6 \to (C_4, C_4)$ to prove that $K_6 \to (P_5, P_5)$.
	\vfill
\end{enumerate}
\end{enumerate}
\end{document}
