\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{multicol}
\usepackage{latexsym}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\def\zero{\multicolumn{1}{>{\columncolor{white}}c}{0}}
\def\colCell#1#2{\multicolumn{1}{>{\columncolor{#1}}c}{#2}}

\input{preamble.tex}

\begin{document}
\homework{5: Graphs}{Due Friday, Week 4}

Pick \textbf{three} of \textbf{five} problems to solve.  Prove all of your claims, and have fun!

\begin{enumerate}
\item Define the \textbf{unit distance graph}, denoted in the literature as $\mathbb{R}^2$, as follows:
\begin{itemize}
\item Vertex set: the collection of all points in $\mathbb{R}^2$.
\item Edge set: connect two vertices if their corresponding points in $\mathbb{R}^2$ are distance 1 apart in the plane.
\end{itemize}
This problem asks you to bound the chromatic number of $\mathbb{R}^2$.  
\begin{enumerate}
\item One easy lower bound is that you'll need at least three colors.  This is because there is an equilateral triangle with side length 1 in $\mathbb{R}^2$, and therefore if we're coloring all of $\mathbb{R}^2$ we'll need to give those three points different colors, or we'll have an edge with monochromatic endpoints.  

Improve this bound by 1: i.e. prove that $\chi(\mathbb{R}^2) \geq 4$.
\item Find any finite upper bound on the chromatic number of $\mathbb{R}^2$: i.e. find some $n \in \mathbb{N}$ such that $\chi(\mathbb{R}^2) \leq n$.
\end{enumerate}

\item Prove that all ``map-graphs'' are planar.

\item A sequence $d_1 \geq d_2 \geq \ldots d_n$ of nonnegative integers is called \textbf{graphic} if and only if there is a graph $G$ on $n$ vertices such that $\deg(v_i) = d_i$, for every $v_i \in V(G)$.

Determine whether any of the following sequences are graphic:
\begin{itemize}
\item $5,3,3,2,2,2$.
\item $6,2,2,2$.
\item $3,2,2,2,1,1,1$
\item $3,3,3,3,3,3,3,3,3,3$
\item $\underbrace{n, n, n \ldots n}_{n+1 \textrm{ times}}$.
\end{itemize}

\item A graph $G$ is called \textbf{Eulerian} if it contains a path $P$ that satisfies the following two properties:
\begin{itemize}
\item $P$ starts and ends on the same vertex.
\item $P$ uses every edge in $G$ exactly once.
\end{itemize}
Show that a graph $G$ is Eulerian if and only if the degree of every vertex in $G$ is even.

\item For a graph $G$, let $\Delta(G)$ denote the maximum degree of all of the vertices in $G$.   Prove that if $G$ is a graph, then $\chi(G) \leq \Delta(G)+1.$
\end{enumerate}



\end{document}