%
% LaTeX Problem Set Template by Sachin Padmanabhan
% I created this when I was a freshman in CS 103,
% and I continue to use it to this day.
%
% Hope you enjoy!
%
% There may be problems with this template.
% If so, feel free to contact me.
%
\documentclass{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{mathdots}
\usepackage[pdftex]{graphicx}
\usepackage{fancyhdr}
\usepackage[margin=1in]{geometry}
\usepackage{multicol}
\usepackage{bm}
\usepackage{listings}
\PassOptionsToPackage{usenames,dvipsnames}{color} %% Allow color names
\usepackage{pdfpages}
\usepackage{algpseudocode}
\usepackage{tikz}
\usepackage{enumitem}
\usepackage[T1]{fontenc}
\usepackage{inconsolata}
\usepackage{framed}
\usepackage{wasysym}
\usepackage[thinlines]{easytable}
\usepackage{wrapfig}
\usepackage{hyperref}
\usepackage{mathrsfs}
\title{CS 103: Mathematical Foundations of Computing\\Problem Set \#4}
\author{Sachin Padmanabhan}
\date{\today}
\lhead{Sachin Padmanabhan}
\chead{Problem Set \#4}
\rhead{\today}
\lfoot{}
\cfoot{CS 103: Mathematical Foundations of Computing --- Fall 2017}
\rfoot{\thepage}
\newcommand{\abs}[1]{\lvert #1 \rvert}
\newcommand{\absfit}[1]{\left\lvert #1 \right\rvert}
\newcommand{\norm}[1]{\left\lVert #1 \right\rVert}
\newcommand{\eval}[3]{\left[#1\right]_{#2}^{#3}}
\renewcommand{\(}{\left(}
\renewcommand{\)}{\right)}
\newcommand{\floor}[1]{\left\lfloor#1\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil#1\right\rceil}
\newcommand{\pd}[1]{\frac{\partial}{\partial #1}}
\newcommand{\inner}[1]{\langle#1\rangle}
\newcommand{\cond}{\bigg|}
\newcommand{\rank}[1]{\mathbf{rank}(#1)}
\newcommand{\range}[1]{\mathbf{range}(#1)}
\newcommand{\nullsp}[1]{\mathbf{null}(#1)}
\newcommand{\repr}[1]{\left\langle#1\right\rangle}
\DeclareMathOperator{\Var}{Var}
\DeclareMathOperator{\tr}{tr}
\DeclareMathOperator{\Tr}{\mathbf{Tr}}
\DeclareMathOperator{\diag}{\mathbf{diag}}
\DeclareMathOperator{\dist}{\mathbf{dist}}
\DeclareMathOperator{\prob}{\mathbf{prob}}
\DeclareMathOperator{\dom}{\mathbf{dom}}
\DeclareMathOperator{\E}{\mathbf{E}}
\DeclareMathOperator{\Q}{\mathbb{Q}}
\DeclareMathOperator{\R}{\mathbb{R}}
\DeclareMathOperator{\var}{\mathbf{var}}
\DeclareMathOperator{\quartile}{\mathbf{quartile}}
\DeclareMathOperator{\conv}{\mathbf{conv}}
\DeclareMathOperator{\VC}{VC}
\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\argmin}{arg\,min}
\DeclareMathOperator{\Ber}{Bernoulli}
\DeclareMathOperator{\NP}{\mathbf{NP}}
\DeclareMathOperator{\coNP}{\mathbf{coNP}}
\DeclareMathOperator{\TIME}{\mathsf{TIME}}
\DeclareMathOperator{\polytime}{\mathbf{P}}
\DeclareMathOperator{\PH}{\mathbf{PH}}
\DeclareMathOperator{\SIZE}{\mathbf{SIZE}}
\DeclareMathOperator{\ATIME}{\mathbf{ATIME}}
\DeclareMathOperator{\SPACE}{\mathbf{SPACE}}
\DeclareMathOperator{\ASPACE}{\mathbf{ASPACE}}
\DeclareMathOperator{\NSPACE}{\mathbf{NSPACE}}
\DeclareMathOperator{\Z}{\mathbb{Z}}
\DeclareMathOperator{\N}{\mathbb{N}}
\DeclareMathOperator{\EXP}{\mathbf{EXP}}
\DeclareMathOperator{\NEXP}{\mathbf{NEXP}}
\DeclareMathOperator{\NTIME}{\mathbf{NTIME}}
\DeclareMathOperator{\DTIME}{\mathbf{DTIME}}
\DeclareMathOperator{\poly}{poly}
\DeclareMathOperator{\BPP}{\mathbf{BPP}}
\DeclareMathOperator{\ZPP}{\mathbf{ZPP}}
\DeclareMathOperator{\RP}{\mathbf{RP}}
\DeclareMathOperator{\coRP}{\mathbf{coRP}}
\DeclareMathOperator{\BPL}{\mathbf{BPL}}
\DeclareMathOperator{\IP}{\mathbf{IP}}
\DeclareMathOperator{\PSPACE}{\mathbf{PSPACE}}
\DeclareMathOperator{\NPSPACE}{\mathbf{NPSPACE}}
\DeclareMathOperator{\SAT}{\mathsf{SAT}}
\DeclareMathOperator{\NL}{\mathbf{NL}}
\DeclareMathOperator{\PCP}{\mathbf{PCP}}
\DeclareMathOperator{\PP}{\mathbf{PP}}
\DeclareMathOperator{\cost}{cost}
\let\Pr\relax
\DeclareMathOperator*{\Pr}{\mathbf{Pr}}
\definecolor{shadecolor}{gray}{0.9}
\theoremstyle{plain}
\newtheorem*{lem}{Lemma}
\theoremstyle{plain}
\newtheorem*{claim}{Claim}
\theoremstyle{definition}
\newtheorem*{answer}{Answer}
\newtheorem{theorem}{Theorem}[section]
\newtheorem*{thm}{Theorem}
\newtheorem{corollary}{Corollary}[theorem]
\newtheorem{lemma}[theorem]{Lemma}
\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}
\setlength{\parindent}{0pt}
\pagestyle{fancy}
\renewcommand{\thefootnote}{\fnsymbol{footnote}}
\begin{document}
\maketitle
\section{Set Cardinalities}
Let's begin with a new definition. If $A$ and $B$ are sets, the \textbf{\textit{Cartesian product}} of $A$ and $B$, denoted $A \times B$,
is the set
\begin{equation*}
\{ (x, y)\ |\ x \in A \land y \in B \}
\end{equation*}
Intuitively, $A \times B$ is the set of all ordered pairs you can make by taking one element from $A$ and one element
from $B$, in that order. For example, the set $\{1, 2\} \times \{u, v, w\}$ is
\begin{equation*}
\{\ (1, u), (1, v), (1, w), (2, u), (2, v), (2, w)\ \}
\end{equation*}
For the purposes of this problem, let's let $\bigstar$ and $\smiley{}$ denote two arbitrary objects where $\bigstar \ne \smiley{}$. Over the
course of this problem, we're going to ask you to prove that $|\N \times \{\bigstar, \smiley{}\}| = |\N|$. \\
Before starting this problem, you might want to play around with the set $\N \times \{\bigstar, \smiley{}\}$ so that you can get a
better feel for what it looks like.
\begin{enumerate}[label*=\roman*.,ref=\roman*]
\item Draw a picture showing a way to pair of the elements of $\N \times \{\bigstar, \smiley{}\}$ with the elements of $\N$ so
that no elements of either set are uncovered or paired with multiple elements.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item Based on the picture you came up with in part (i),
define a bijection $f : \N \times \{\bigstar, \smiley{}\} \to \N$. The inputs
to this function will be elements of $\N \times \{\bigstar, \smiley{}\}$, so you can define your function by writing
\begin{center}
$f(n, x) = $ \underline{\hspace{35ex}}
\end{center}
where $n \in \N$ and $x \in \{\bigstar, \smiley{}\}$. (You cannot assume $\bigstar$ or $\smiley{}$ are numbers. They?re arbitrary values
out of your control.)
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item Prove that the function you came up with in part (ii) is a bijection.
\begin{shaded}
Provide a proof here.
\end{shaded}
\end{enumerate}
The result you've proved here essentially shows that $2\aleph_0 = \aleph_0$. Isn't infinity weird?
\section{Understanding Diagonalization}
Proofs by diagonalization are tricky and rely on nuanced arguments.
In this problem, we'll ask you to review
the diagonalization proof we covered in the Guide to Cantor's Theorem
to help you better understand how it works.
(Please read the Guide to Cantor's Theorem before attempting this problem.)
\begin{enumerate}[label*=\roman*.,ref=\roman*]
\item Consider the function $f : \N \to \wp(\N)$ defined as
$f(n) = \varnothing$.
Trace through our proof of Cantor's theorem
with this choice of $f$ in mind.
In the middle of the argument,
the proof defines some set $D$ in terms of $f$.
Given that $f(n) = \varnothing$,
what is that set $D$? Provide your answer without using
set-builder notation.
Is it clear why $f(n) \neq D$ for any $n \in \N$?
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item Let $f$ be the function from part (i).
Find a set $S \subseteq \N$ such that $S \neq D$,
but $f(n) \neq S$ for any $n \in \N$.
Justify your answer.
This shows that while the diagonalization proof will always find
\textit{some} set $D$ that isn't covered by $f$,
it won't find every set with this property.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
Provide justification here.
\end{shaded}
\item Repeat part (i) of this problem using the function
$f : \N \to \wp(\N)$ defined as
$$f(n) = \{ m \in \N \mid m \geq n \}$$
Now what do you get for the set $D$?
Is it clear why $f(n) \neq D$ for any $n \in \N$?
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item Repeat part (ii) of this problem using the function $f$ from part (iii).
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
Provide justification here.
\end{shaded}
\end{enumerate}
\section{Simplifying Cantor's Theorem?}
In our proof of Cantor's theorem,
we proved that $|S| \neq |\wp(S)|$ by using a diagonal argument.
Below is a purported proof that $|S| \neq |\wp(S)|$
that doesn't use a diagonal argument:
\vspace{-1em}
\begin{quote}
\begin{thm}
If $S$ is a set, then $|S| \neq |\wp(S)|$.
\end{thm}
\begin{proof}
Let $S$ be any set and consider the function
$f : S \to \wp(S)$ defined as $f(x) = \{x\}$.
To see that this is a valid function from $S$ to $\wp(S)$,
note that for any $x \in S$,
we have $\{x\} \subseteq S$.
Therefore, $\{x\} \in \wp(S)$ for any $x \in S$,
so $f$ is a legal function from $S$ to $\wp(S)$. \\
Let's now prove that $f$ is injective.
Consider any $x_1, x_2 \in S$ where $f(x_1) = f(x_2)$.
We'll prove that $x_1 = x_2$.
Because $f(x_1) = f(x_2)$,
we have $\{x_1\} = \{x_2\}$.
Since two sets are equal if and only
if their elements are the same,
this means that $x_1 = x_2$, as required. \\
However, $f$ is not surjective.
Notice that $\varnothing \in \wp(S)$,
since $\varnothing \subseteq S$ for any set $S$,
but that there
is no $x$ such that $f(x) = \varnothing$;
this is because $\varnothing$ contains no elements and
$f(x)$ always contains one element.
Since $f$ is not surjective, it is not a bijection.
Thus $|S| \neq |\wp(S)|$.
\end{proof}
\end{quote}
Unfortunately, this proof is incorrect.
What's wrong with this proof?
Justify your answer, and be as
specific as possible.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
Provide justification here.
\end{shaded}
\section{Paradoxical Sets}
What happens if we take \textit{absolutely everything} and throw it into a set?
If we do, we would get a set called the \textbf{\textit{universal set}},
which we denote $\mathscr{U}$:
$$\mathscr{U} = \{ x \mid \text{$x$ exists} \}$$
Absolutely everything would belong to this set:
\begin{center}
$1 \in \mathscr{U}$ \quad $\N \in \mathscr{U}$ \quad $\text{CS103} \in \mathscr{U}$ \quad $\text{whimsy} \in \mathscr{U}$
\end{center}
In fact,
we'd even have $\mathscr{U} \in \mathscr{U}$,
which is strange but not immediately a problem. \\
Unfortunately,
the set $\mathscr{U}$ doesn't actually exist,
as its existence would break mathematics.
\begin{enumerate}[label*=\roman*.,ref=\roman*]
\item Prove that if $A$ and $B$ are arbitrary sets where
$A \subseteq B$, then $|A| \leq |B|$.
\textit{(Hint: Look at the Guide to
Cantor's Theorem.
Formally speaking, if you want to prove that $|A| \leq |B|$,
what do you need to prove?
Your answer should involve defining some sort of function
between $A$ and $B$ and proving
that function has some specific property or properties.)}
\begin{shaded}
Provide a proof here.
\end{shaded}
\item Using your result from (i),
prove that if $\mathscr{U}$ exists, then
$|\wp(\mathscr{U})| \leq |\mathscr{U}|$.
\begin{shaded}
Provide a proof here.
\end{shaded}
\item Using your result from (ii) and Cantor's Theorem,
prove that $\mathscr{U}$ does not exist.
Feel free to the following
fact:
for any sets $A$ and $B$, if $|A| \leq |B|$ and $|B| \leq |A|$,
then $|A| = |B|$.
\begin{shaded}
Provide a proof here.
\end{shaded}
\end{enumerate}
The result you've proven shows that there is a collection of objects
(namely, the collection of everything that exists)
that cannot be put into a set.
When this was discovered at the start of the twentieth century,
it caused quite a lot of chaos in the math world
and led to a reexamination of logical reasoning itself
and a more formal definition of what objects can and cannot
be gathered into a set.
If you're curious to learn
more about what came out of that,
take Math 161 (Set Theory) or Phil 159 (Non-Classical Logic).
\section{Independent Sets}
An \textbf{\textit{independent set}} in a graph $G = (V, E)$
is a set $I \subseteq V$ with the following property:
$$\forall u \in I.\ \forall v \in I.\ \{u, v\} \not\in E.$$
This question explores independent sets and their properties.
\begin{enumerate}[label*=\roman*.,ref=\roman*]
\item Translate the definition of an independent set into plain English.
No justification is necessary.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item Download the starter files for Problem Set Four from the website, then open the file $\mathsf{GraphTheory.cpp}$
and implement a function
\begin{center}
$\mathsf{bool\ isIndependentSet(Graph\ G,\ std::set I)}$
\end{center}
that takes as input a graph $G$ and a set $I$, then returns whether $I$ is an independent set in $G$. The
definition of the $\mathsf{Graph}$ type is provided in $\mathsf{GraphTheory.h}$. \\
Our provided starter code contains logic that, given a graph $G$, finds the largest independent set in
$G$ by making a lot of repeated calls to $\mathsf{isIndependentSet}$. You might want to look over some of
the sample graphs to get a feel for what large independent sets look like.
\begin{shaded}
Submit your edited $\mathsf{GraphTheory.cpp}$ file through Gradescope.
\end{shaded}
\item You want to conduct a poll for an election and would like to survey people where no two people in
the group know each other so that you can get a good representative sample of the population.
Ideally, you'd find a large group of mutual strangers so that your poll has good statistical power.
Explain how you might model this problem in terms of building some sort of graph, then finding a
large independent set in it. Briefly justify your answer; no formal proof is necessary. \textit{(We don't
want you to design an algorithm for finding large independent sets; instead, imagine you have a
program that finds large independent sets and explain how you'd use it to choose who to survey.)}
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
Provide justification here.
\end{shaded}
\end{enumerate}
The size of an independent set is the number of nodes in it.
Formally speaking, if $I$ is an independent set,
then the size of $I$ is given by $|I|$. The \textit{\textbf{independence number}} of a graph $G$, denoted \textbf{$\alpha(G)$}, is the size of the largest independent set in $G$.
\begin{enumerate}[resume*]
\item Edit the file $\mathsf{PartA.graph}$ in the $\mathsf{res/}$ directory to define a graph $G$ where $G$ has exactly five
nodes and $\alpha(G) = 5$.
\begin{shaded}
Submit your edited $\mathsf{PartA.graph}$ file through Gradescope.
\end{shaded}
\item Edit the file $\mathsf{PartB.graph}$ in the $\mathsf{res/}$ directory to define a graph $G$ where $G$ has exactly five
nodes and $\alpha(G) = 1$.
\begin{shaded}
Submit your edited $\mathsf{PartB.graph}$ file through Gradescope.
\end{shaded}
\end{enumerate}
\section{Vertex Covers}
A \textbf{\textit{vertex cover}} in a graph $G = (V, E)$ is a set
$C \subseteq V$ with the following property:
$$\forall u \in V.\ \forall v \in V.\ (\{u, v\} \in E
\rightarrow u \in C \lor v \in C).$$
This question explores vertex covers and their properties.
\begin{enumerate}[label*=\roman*.,ref=\roman*]
\item Translate the definition of a vertex cover into plain English.
No justification is necessary.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item Implement a function
\begin{center}
$\mathsf{bool\ isVertexCover(Graph\ G,\ std::set C)}$
\end{center}
that takes as input a graph $G$ and a set $C$, then returns whether $C$ is a vertex cover of $G$. \\
Our provided starter code contains logic that, given a graph $G$, finds the smallest vertex cover in
$G$ by making a lot of repeated calls to $\mathsf{isVertexCover}$. You might want to look over some of
the sample graphs to get a feel for what large independent sets look like.
\begin{shaded}
Submit your edited $\mathsf{GraphTheory.cpp}$ file through Gradescope.
\end{shaded}
\item Suppose that you have a map of a city's roads and streets (assume that the roads are set up so that
it's possible to walk between any two points in the city). You want to set up information kiosks so
that no matter where you are, you never need to walk more than a block to get to a kiosk. You
also want to use as few information kiosks as possible to accomplish this. Explain how you might
model this problem by building some sort of graph and looking for a small vertex cover in that
graph. Briefly justify your answer; no formal proof is necessary. \textit{(Along the lines of part (iii) of
the previous problem, assume you have a black box for finding small vertex covers and don?t try to
come up with an algorithm on your own.)}
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
Provide justification here.
\end{shaded}
\end{enumerate}
The size of a vertex cover is the number of nodes in it.
Formally speaking, if $C$ is a vertex cover,
then the size of $C$ is given by $|C|$. The \textbf{\textit{vertex cover number}} of a graph $G$, denoted $\tau(G)$, is the size of the smallest
vertex cover of $G$.
\begin{enumerate}[resume*]
\item Edit the file $\mathsf{PartC.graph}$ in the $\mathsf{res/}$ directory to define a graph $G$ where $G$ has exactly five
nodes and $\tau(G) = 0$.
\begin{shaded}
Submit your edited $\mathsf{PartC.graph}$ file through Gradescope.
\end{shaded}
\item Edit the file $\mathsf{PartD.graph}$ in the $\mathsf{res/}$ directory to define a graph $G$ where $G$ has exactly five
nodes and $\tau(G) = 4$.
\begin{shaded}
Submit your edited $\mathsf{PartD.graph}$ file through Gradescope.
\end{shaded}
\end{enumerate}
\section{Independent Sets and Vertex Covers}
\textit{(This problem builds on Problem Five and Problem Six, so you may want to complete those problems before
starting this one.)} \\
There's a close connection between independent sets and vertex covers.
\begin{enumerate}[label*=\roman*.,ref=\roman*]
\item Prove that if $G = (V, E)$ is a graph and $I$ is a an
independent set in $G$, then $V - I$ is a vertex cover of $G$.
\begin{shaded}
Provide a proof here.
\end{shaded}
\item Prove that if $G = (V, E)$ is an arbitrary graph and
$C$ is a vertex cover of $G$, then $V - C$ is an independent
set in $G$.
\begin{shaded}
Provide a proof here.
\end{shaded}
\end{enumerate}
The connection you explored here shows that the problem of finding a maximum independent set
in a graph is essentially the same as finding a minimum vertex cover in that graph. It's suspected that both of
these problems are computationally infeasible for large graphs. We'll talk about this more when we discuss
$\NP$-completeness later in the quarter. \\
This result also shows, for any graph $G$, that $\alpha(G) + \tau(G) = n$.
\section{Chromatic and Clique Numbers}
Recall from lecture that a \textit{\textbf{k-vertex coloring}} of a graph is a way of coloring each node in the graph one of
\underline{up to} $k$ different colors such that no two adjacent nodes are the same color. The \textit{\textit{chromatic number}} of a
graph, denoted $\chi(G)$, is the minimum value of $k$ for which a $k$-vertex coloring exists.
\begin{enumerate}[label*=\roman*.,ref=\roman*]
\item Implement a function
\begin{center}
$\mathsf{bool\ isKVertexColoring(Graph\ G,
std::map\ colors,
std::size\_t\ k);}$
\end{center}
that takes as input a graph, a mapping from nodes in the graph to colors, and a number $k$, then returns
whether the indicated coloring is a $k$-vertex coloring. You can assume that the map has one
key for each node in the graph and that the only keys in the map are nodes in $G$. (The type
$\mathsf{std::size\_t}$ represents a natural number.) \\
Our provided starter code contains some logic that, given a graph $G$, finds a minimum $k$-vertex coloring
of $G$ by making a lot of calls to your $\mathsf{isKVertexColoring}$ function. We recommend taking
some time to look at a few sample graphs and their minimum colorings - they're quite pretty!
\begin{shaded}
Submit your edited $\mathsf{GraphTheory.cpp}$ file through Gradescope.
\end{shaded}
\end{enumerate}
Here's a new definition. A \textit{\textbf{clique}} in a graph $G = (V, E)$ is a set $K \subseteq V$ with the following property:
\begin{equation*}
\forall u \in K.\ \forall v \in K.\ (u \ne v \rightarrow \{u, v\} \in E)
\end{equation*}
This question explores the connection between cliques and chromatic numbers.
\begin{enumerate}[resume*]
\item Translate the definition of a clique into plain English. No justification is necessary.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item Implement a function
\begin{center}
$\mathsf{bool\ isClique(Graph\ G, std::set\ K)}$
\end{center}
that takes as input a graph $G$ and a set $K$, then returns whether $K$ is a clique in $G$.\\
Our provided starter code contains some logic that, given a graph $G$, finds the largest clique
in $G$ by making a lot of calls to your $\mathsf{isClique}$ function. You may want to take a look at some of the
provided sample graphs to see what large cliques look like.
\begin{shaded}
Submit your edited $\mathsf{GraphTheory.cpp}$ file through Gradescope.
\end{shaded}
\end{enumerate}
The size of a clique $K$, denoted $|K|$, is the number of nodes in $K$. The \textbf{\textit{clique number}} of a graph, denoted
$\omega(G)$, is the size of the largest clique in $G$.
\begin{enumerate}[resume*]
\item Prove that if $G$ is a graph, then $\chi(G) \ge \omega(G)$.
\begin{shaded}
Provide a proof here.
\end{shaded}
\item Edit the file $\mathsf{PartE.graph}$ in the $\mathsf{res/}$ directory to contain a graph $G$ where $\chi(G) \ne \omega(G)$. This
shows that, in general, the chromatic and clique numbers of a graph don't have to equal one another.
\begin{shaded}
Submit your edited $\mathsf{PartE.graph}$ file through Gradescope.
\end{shaded}
\end{enumerate}
\section{Bipartite Graphs}
The \textbf{\textit{bipartite graphs}}
are a special class of graphs with applications
throughout computer science.
An undirected graph $G = (V, E)$ is called \textbf{\textit{bipartite}}
if there exists two sets $V_1$ and $V_2$ such that
\begin{itemize}
\item every node $v \in V$ belongs to exactly one of $V_1$ and $V_2$,
and
\item every edge $e \in E$ has one endpoint in $V_1$ and the other in $V_2$.
\end{itemize}
The sets $V_1$ and $V_2$ here are called the bipartite classes of G. \\
To help you get a better intuition for bipartite graphs,
let's consider an example.
Suppose that you have a
group of people and a list of restaurants.
You can illustrate which people like which restaurants by constructing
a bipartite graph where $V_1$ is the set of people,
$V_2$ is the set of restaurants,
and there's an edge
from a person $p$ to a restaurant $r$ if person $p$ likes restaurant $r$. \\
Bipartite graphs have many interesting properties.
One of the most fundamental is this one:
\begin{center}
\textit{An undirected graph is bipartite if and only if it contains no cycles
of odd length.}
\end{center}
Intuitively, a bipartite graph contains no odd-length cycles
because cycles alternate between the two
groups $V_1$ and $V_2$,
so any cycle has to have even length. \\
The trickier step is proving that if $G$ is a graph that contains no cycles of odd length,
then $G$ has to be bipartite.
For now,
assume that G has just one connected component;
if G has multiple connected components,
we can treat
each one as a separate graph for the purposes of determining whether $G$
is bipartite.
(You don't need to
prove this,
but I'd recommend taking a minute to check why this is the case.) \\
Suppose $G$ is a connected,
undirected graph with no cycles of odd length.
Choose any node $v \in V$.
Let $V_1$
be the set of all nodes that are connected to $v$
by a path of odd length and $V_2$
be the set of all nodes connected
to $v$ by a path of even length.
(Note that these paths do not have to be simple paths).
Formally:
\begin{gather*}
V_1 = \{ x \in V \mid \text{there is an odd-length path from $v$ to $x$} \} \\
V_2 = \{ x \in V \mid \text{there is an even-length path from $v$ to $x$} \}
\end{gather*}
\begin{enumerate}[label*=\roman*.,ref=\roman*]
\item Prove that $V_1$ and $V_2$ have no nodes in common.
\begin{shaded}
Provide a proof here.
\end{shaded}
\item Using your result from part (i),
prove that if $G$ is connected and has no cycles of odd length,
then $G$ is bipartite.
\textit{(Hint: look back at the definition of a bipartite graph.
What exactly do you need to
prove to show that a graph is bipartite?)}
\begin{shaded}
Provide a proof here.
\end{shaded}
\end{enumerate}
\section{Chromatic and Independence Numbers}
\textit{(This problem builds on Problem Five, so you may want to complete that problem before starting this one.)} \\
In Problem Eight, you explored the connection between clique numbers and chromatic numbers. This
problem explores the connection between independence numbers and chromatic numbers. \\
Let $n$ be an arbitrary positive natural number.
Prove that if $G$ is an undirected graph with exactly $n^2+1$ nodes,
then $\chi(G) \geq n+1$ or $\alpha(G) \geq n+1$ (or both).
As a hint, look at Handout 17's
advice about how to prove a statement of the form $P \lor Q$.
\begin{shaded}
Provide a proof here.
\end{shaded}
\section*{Optional Fun Problem 1:
Hugs All Around! (1 Point Extra Credit)}
There's a party with $137$ attendees.
Each person is either \textbf{\textit{honest}},
meaning that they \textit{always} tell the truth,
or \textbf{\textit{mischievous}},
meaning that they \textit{never} tell the truth. \\
After everything winds down,
everyone is asked how many \underline{\textbf{\textit{honest}}} people they hugged at the party.
Surprisingly,
each of the numbers
0, 1, 2, 3, \dots, and 136 was given as an answer exactly once. \\
How many honest people were at the party?
Prove that your answer is correct and that no other answer
could be correct.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
Provide a proof here.
\end{shaded}
\section*{Optional Fun Problem 2:
How Many Functions Are There? (1 Point Extra Credit)}
If $A$ and $B$ are sets, we can define the set $B^A$
to be the set of all functions from $A$ to $B$. Formally speaking:
\begin{equation*}
B^A = \{ f\ |\ f : A \rightarrow B \}
\end{equation*}
Using the formal definition of the less-than relation over cardinalities, prove that $|\N| < |\N^{\N}|$. This shows
that $\aleph_0 < \aleph_0^{\aleph_0}$. Isn't infinity weird?
\begin{shaded}
Provide a proof here.
\end{shaded}
\end{document}