\documentclass{article}
\usepackage{amssymb,multicol, graphicx, color, amsthm, hyperref, amsmath, verbatim, caption, subcaption}
\setlength{\parskip}{8pt}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\renewcommand{\today}{}
\newcommand{\abs}[1]{\left| #1\right|}
\addtolength{\topmargin}{-.875in}
\addtolength{\textheight}{1.75in}
\newcommand{\solution}[1]{
\begin{quote}\color{red}Solution:\quad
\color{black} #1
\end{quote}
}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\C}{\mathbb{C}}
\begin{document}
\title{Math 101 Homework}
\author{Mary Radcliffe}
\date{due 27 Jan 2015}
\maketitle
Complete the following problems. Fully justify each response.
\begin{enumerate}
\item Suppose $M$ is a graph\footnote{Here you can assume that $M$ has at most countably many vertices, so that we can list the partition sets in $\mathcal{S}$. In general, this statement is still true when $M$ has more than countably many vertices, but in that case you may not get countably many independence sets in the partition.}, that has the following condition:
\[\hbox{if } a\not\sim b\hbox{ and }b\not\sim c, \hbox{ then } a\not\sim c\]
(where $\not\sim$ indicates vertices are not adjacent and $\sim$ indicates vertices are adjacent).
Prove that the vertex set of $M$ can be divided into subsets $\mathcal{S}=\{S_1, S_2, S_3,\dots\}$ (this list could be finite in length) in such a way that if $u, v \in S_i$ (the same $i$), then $u\not\sim v$, but if $u\in S_i$ and $v\in S_j$ (with $i\neq j$), then $u\sim v$.
\item Mess around with triangle-free, 3-chromatic unit graphs. Try to build some that don't contain any 5- or 7-cycles (without just being larger odd cycles).
\item Suppose that we lived in a different universe, and Erd\H{o}s' 1975 conjecture that every triangle-free unit graph is 3-chromatic was proven true instead of false. How do you think that could help mathematicians solve the Hadwiger-Nelson problem? What kind of approaches do you think would made sense if Erd\H{o}s' conjecture were true?
\end{enumerate}
\end{document}