\documentclass[12pt]{amsart} 


% Call packages that allow you to invoke certain mathematical symbols.
\usepackage{amssymb,amsmath,amsthm}
\usepackage[margin=0.9in]{geometry}
\usepackage{cases}
\usepackage{url}
\usepackage{hyperref}
\usepackage{tikz}

% Set the title, author, and date information.


% Formally begin the document and make the title.

\begin{document}
\noindent \textbf{Math 451 - Spring 2018 \\
 Homework 9} \\
Due May 16th, 2018 \vspace{-4mm}\\


\vspace{-5mm}
\normalsize
\noindent \hrulefill
\vspace{3mm}\\
\noindent \textbf{Turn in:} 

\vspace{5mm}

\vspace{5mm}
\begin{enumerate}


\item   Find a 4-regular planar graph. (Note that $K_5$ is such a graph but it’s not planar.) and a planar bipartite graph such that every vertex has degree 3. (Note that $K_{3,3}$ is such a graph but it’s not planar.)

\item Prove Theorem 8.8 in the book. (Hint: Look at the proof of theorem 8.7!)

\item Exercise 9.1

\item Show that the Gr\"otzsch graph (Figure 10.11) is not planar.  

\item Determine the chromatic number of each of the following:
\begin{enumerate}
\item[a.] The petersen graph.
\item[b.] The $n$-dimensional hypercube $Q_n$.
\item[c.] The graph with $V=\{v_i\mid 1\leq i \leq 10\}$, $E=\{v_iv_j \text{ if $i$ divides $j$}\}$. 

\end{enumerate}  
\end{enumerate}


\end{document}
