% 
% 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.
%

% Updated for Fall 2018 by Michael Zhu

\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}
\hypersetup{
    colorlinks=true,
    linkcolor=blue,
    filecolor=magenta,      
    urlcolor=blue,
}
\usepackage{mathrsfs}
\usepackage{makecell}
\usepackage{tabularx}



\title{CS 103: Mathematical Foundations of Computing\\Problem Set \#4}
\author{Your Name(s) Here}
\date{\today}

\lhead{Your Name(s) Here}
\chead{Problem Set \#4}
\rhead{\today}
\lfoot{}
\cfoot{CS 103: Mathematical Foundations of Computing --- Spring 2019}
\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}}

% start MZ
\usetikzlibrary{automata,positioning}
\let\oldemptyset\emptyset
\renewcommand{\emptyset}{\text{\O}}
\renewcommand\qedsymbol{$\blacksquare$}
\newenvironment{prf}{{\bfseries Proof.}}{\qedsymbol}
\renewcommand{\emph}[1]{\textit{\textbf{#1}}}
\newcommand{\annotate}[1]{\textit{\textcolor{blue}{#1}}}
\usepackage{stmaryrd}
\usepackage{minted}
\usepackage{mathtools}
% end MZ

\begin{document}

\maketitle

\section{Cartesian Products and Set Cardinalities}

If $A$ and $B$ are sets, the \textbf{\textit{Cartesian product}} of $A$ and $B$, denoted $\mathbf{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 $\{\textcolor{red}{1}, \textcolor{red}{2}\} \times \{\textcolor{blue}{u}, \textcolor{blue}{v}, \textcolor{blue}{w}\}$ is

\begin{equation*}
\{\ (\textcolor{red}{1}, \textcolor{blue}{u}), (\textcolor{red}{1}, \textcolor{blue}{v}), (\textcolor{red}{1}, \textcolor{blue}{w}), (\textcolor{red}{2}, \textcolor{blue}{u}), (\textcolor{red}{2}, \textcolor{blue}{v}), (\textcolor{red}{2}, \textcolor{blue}{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|$. 

\annotate{For your own benefit, we strongly encourage you to pause and 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. You do not need to turn it in. You might want to draw some pictures of the set $\N \times \{\bigstar, \smiley{}\}$ so that you can get a better visual intuition.}

\begin{enumerate}[label*=\roman*.,ref=\roman*]
    \item Based on the picture you came up with,
    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{shaded}
    \begin{center}
    $f(n, x) = $  \underline{\hspace{35ex}} % Write you definition here
    \end{center}
    \end{shaded}
    where $n \in \N$ and $x \in \{\bigstar, \smiley{}\}$. 
    
    \annotate{In defining this function, you cannot assume $\bigstar$ or $\smiley{}$ are numbers, since they're arbitrary values out of your control. See if you can find a way to define this function that doesn't treat $\bigstar$ or $\smiley{}$ algebraically.}
    
    \item Prove that the function you came up with in part (i) 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?

\pagebreak

\section{Understanding Diagonalization}

Proofs by diagonalization are tricky and rely on nuanced arguments. In this problem, we'll ask you to review formal proof of 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$. 
    
    \annotate{This is of course a terrible proposal for f, if the point is to come up with a bijection between $\N$ and $\wp(\N)$ It's not even close to injective (every single value of $n$ from the domain $\N$ gives the same $f(n)$), and it’s not even close to surjective either (only one element of the co-domain $\wp(\N)$ is used). But we can't really blame the person who came up with it—we know that there is no such bijection, so the only surprising thing about this not being one is just how spectacularly it fails.}
    
    Despite how poor this $f$ is, tracing through our formal proof of Cantor's theorem with this choice of $f$ in mind will help us see with a concrete example $f$ how the set $D$ is made. So go ahead and trace through our formal Cantor proof, to the part where the proof defines some set $D$ in terms of $f$. Given that $f(n) = \varnothing$, what is that set $D$ and how do we know that $f(n) \neq D$ for any $n \in \N$? Write $D$ without using set builder notation (there is an extremely concise solution), and you just need one brief sentence to explain how we know that  $f(n) \neq D$ for any $n \in \N$.
    
    \annotate{Make sure you can determine what the set D is both by using the visual intuition behind Cantor's theorem
    and by symbolically manipulating the formal definition of D given in the proof.}
    
    \begin{shaded}
    Write your answer here.
    \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 \textit{every} set with this property.
    
    \begin{shaded}
    Write your answer here and 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}
    Write your answer here.
    \end{shaded}
    
    \item Repeat part (ii) of this problem using the function $f$ from part (iii).
    
    \begin{shaded}
    Write your answer and justification here.
    \end{shaded}
    
    \item Give a function $f : \N \rightarrow \wp(\N)$ such that the set $D$ obtained from the proof of Cantor's theorem is the set $\{ n \in \N \mid n$ is even\}. Briefly justify your answer.
    
    \begin{shaded}
    Write your answer and justification here.
    \end{shaded}

\end{enumerate}

\pagebreak

\section{Simplifying Cantor's Theorem?}

Below is a purported proof that $|S| \neq |\wp(S)|$ that doesn't use a diagonal argument:

\vspace{-2em}
\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 by pointing to a specific claim that's made here that's incorrect and explaining why it's incorrect.

\begin{shaded}
Write your answer and justification here.
\end{shaded}

\pagebreak

\section{Independent and Dominating Sets}

An \emph{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.
$$
Let's begin with a quick warm-up about independent sets.

\begin{enumerate}[label=\roman*.,ref=\roman*,topsep=0pt]
  \item Consider the graph shown below. Give two different independent sets of
    this graph, each of which has cardinality three or greater. No
    justification is necessary.

    \begin{center}
    \begin{minipage}{0.5\textwidth}
    \tikzset{every state/.style={inner sep=6pt,minimum size=0pt}}
    \begin{tikzpicture}[node distance=1.5cm,on grid,auto,
        baseline={(current bounding box.north)}]
      \node[state] (a) {a};
      \node[state] (b) [right=of a] {b};
      \node[state] (c) [right=of b] {c};
      \node[state] (d) [right=of c] {d};
      \node[state] (e) [below=of a] {e};
      \node[state] (f) [below=of b] {f};
      \node[state] (g) [below=of c] {g};
      \node[state] (h) [below=of d] {h};
      \path[-]
        (a) edge node {} (b)
        (a) edge node {} (e)
        (b) edge node {} (c)
        (b) edge node {} (e)
        (b) edge node {} (f)
        (c) edge node {} (d)
        (c) edge node {} (g)
        (f) edge node {} (g)
        (g) edge node {} (h);
    \end{tikzpicture}
    \end{minipage}
    \end{center}

    \begin{shaded}
      Write your answer here.
    \end{shaded}
\end{enumerate}

Now, a new definition. A \emph{dominating set} in $G$ is a set $D \subseteq V$
with the following property:
$$
  \forall v \in V.\ (v \not\in D \rightarrow \exists u \in D.\ \{u, v\} \in E).
$$
As above, it's good to play around with this definition a bit before moving on.

\begin{enumerate}[resume*]
  \item Give two different examples of dominating sets of the above graph, each
    of which has cardinality four or less. No justification is necessary.
    \begin{shaded}
      Write your answer here.
    \end{shaded}

  \item Let $G = (V, E)$ be a graph with the following property: every node in
    G is adjacent to at least one other node in $G$. Prove that if $I$ is an
    independent set in $G$, then $V - I$ is a dominating set in $G$.

    \annotate{Notice that we're asking you to show that $V - I$ is a dominating
      set, not that $I$ is a dominating set. Also, we recommend drawing some
      pictures here to get a sense of how this works. After all, you have a
      couple of examples of independent sets from part (i) of this problem!}

    \annotate{Use the formal definitions to guide your proofs. If you proceed
      via a direct proof or via contrapositive, what, exactly, will you be
      assuming, and what will you be proving? If you write this as a proof by
      contradiction, what specifically is it that you're assuming for the sake
      of contradiction?}

    \begin{shaded}
      Provide a proof here.
    \end{shaded}
\end{enumerate}

An independent set $I$ in a graph $G$ is a \emph{maximal independent set} in
$G$ if there is no independent set $I'$ in $G$ where $I \subsetneq I'$. (Here,
$I \subsetneq I'$ denotes that $I$ is a strict subset of $I'$).

\begin{enumerate}[resume*]
  \item Find independent sets $I$ and $J$ of the graph from part (i) of this
    problem such that $I$ is maximal but $\abs{I} < \abs{J}$. No justification
    is necessary.

    \annotate{Yes, this is possible. The definition of a maximal independent
      set is meant to be taken literally.}

    \begin{shaded}
      Write your answer here.
    \end{shaded}

  \item Prove that if $I$ is a maximal independent set in $G = (V, E)$, then
    $I$ is a dominating set of $G$.

    \annotate{You can build a great intuition for this result by drawing some
      pictures and thinking about what has to happen for a set of nodes to be
      an independent set and for a set of nodes to be a dominating set. When it
      comes time to write out your proof, however, you'll need to use the
      formal first-order definitions of independent sets, maximal independent
      sets, and dominating sets.}

    \begin{shaded}
      Provide a proof here.
    \end{shaded}
\end{enumerate}

\pagebreak


\section{Highly Irregular Graphs}

As a refresher, the \emph{degree} of a node in a graph G, denoted
$\boldsymbol{deg(v)}$, is the number of nodes that $v$ is adjacent to.
Equivalently, it's the number of edges touching $v$.

Now, a new definition. A graph $G = (V, E)$ is called \emph{highly irregular}
if this first-order formula is true:
$$
  \forall v \in V.\ \forall x \in V.\ \forall y \in V.\ (x \ne y \land \{v, x\} \in E \land \{v,
  y\} \in E \rightarrow deg(x) \ne deg(y)).
$$
That definition might look like a mouthful, but it's actually not that bad once
you get the hang of it.

\begin{enumerate}[label=\roman*.,ref=\roman*,topsep=0pt]
  \item Below is a collection of graphs. Which ones are highly irregular? No
    justification is necessary.

    \bgroup
    \def\arraystretch{1.5}
    \begin{tabularx}{\linewidth}{|X|X|X|}
      \hline
      \makecell[c]{\emph{Graph 1}} &
      \makecell[c]{\emph{Graph 2}} &
      \makecell[c]{\emph{Graph 3}} \\
      \makecell[c]{
        \tikzset{every state/.style={inner sep=4pt,minimum size=0pt,
            fill=black!8}}
        \begin{tikzpicture}[node distance=1cm,on grid,auto,
            baseline={(current bounding box.north)}]
          \node[state] (a) {};
          \node[state] (b) [right=of a] {};
          \node[state] (c) [right=of b] {};
          \node[state] (d) [below=of a] {};
          \node[state] (e) [below=of b] {};
          \node[state] (f) [below=of c] {};
          \path[-]
            (a) edge node {} (b)
            (b) edge node {} (c)
            (c) edge node {} (f)
            (f) edge node {} (e)
            (e) edge node {} (d)
            (d) edge node {} (a)
            (b) edge node {} (e);
        \end{tikzpicture}\\[6pt]~} &
      \makecell[c]{
        \tikzset{every state/.style={inner sep=4pt,minimum size=0pt,
            fill=black!8}}
        \begin{tikzpicture}[node distance=0.7cm,on grid,auto,
            baseline={(current bounding box.north)}]
          \node[state] (a) {};
          \node[state] (b) [right=of a] {};
          \path[-]
            (a) edge node {} (b);
        \end{tikzpicture}\\[6pt]~} &
      \makecell[c]{
        \tikzset{every state/.style={inner sep=4pt,minimum size=0pt,
            fill=black!8}}
        \begin{tikzpicture}[node distance=1cm,on grid,auto,
            baseline={(current bounding box.north)}]
          \node[state] (a) {};
          \node[state] (b) [right=of a] {};
          \node[state] (c) [below=of a] {};
          \node[state] (d) [below=of b] {};
          \path[-]
            (a) edge node {} (b)
            (b) edge node {} (d)
            (d) edge node {} (c)
            (c) edge node {} (a)
            (b) edge node {} (c);
        \end{tikzpicture}\\[6pt]~} \\\hline
      \makecell[c]{\emph{Graph 4}} &
      \makecell[c]{\emph{Graph 5}} &
      \makecell[c]{\emph{Graph 6}} \\
      \makecell[c]{
        \tikzset{every state/.style={inner sep=4pt,minimum size=0pt,
            fill=black!8}}
        \begin{tikzpicture}[node distance=0.7cm,on grid,auto,
            baseline={(current bounding box.north)}]
          \node[state] (a) {};
          \node[state] (b) [right=of a] {};
          \node[state] (c) [above=of a] {};
          \node[state] (d) [left=of a] {};
          \node[state] (e) [below=of a] {};
          \path[-]
            (a) edge node {} (b)
            (a) edge node {} (c)
            (a) edge node {} (d)
            (a) edge node {} (e);
        \end{tikzpicture}\\[6pt]~} &
      \makecell[c]{
        \tikzset{every state/.style={inner sep=4pt,minimum size=0pt,
            fill=black!8}}
        \begin{tikzpicture}[node distance=0.7cm,on grid,auto,
            baseline={(current bounding box.north)}]
          \node[state] (a) {};
          \node[state] (c) [below=of a] {};
          \node[state] (b) [left=of c] {};
          \node[state] (d) [right=of c] {};
          \node[state] (f) [below=of b] {};
          \node[state] (e) [left=of f] {};
          \node[state] (g) [below=of c] {};
          \node[state] (h) [below=of e] {};
          \path[-]
            (a) edge node {} (b)
            (a) edge node {} (c)
            (a) edge node {} (d)
            (b) edge node {} (e)
            (b) edge node {} (f)
            (c) edge node {} (g)
            (e) edge node {} (h);
        \end{tikzpicture}\\[6pt]~} &
      \makecell[c]{
        \tikzset{every state/.style={inner sep=4pt,minimum size=0pt,
            fill=black!8}}
        \begin{tikzpicture}[node distance=0.7cm,on grid,auto,
            baseline={(current bounding box.north)}]
          \node[state] (a) {};
          \node[state] (b) [right=of a] {};
          \node[state] (c) [above right=of b] {};
          \node[state] (d) [right=of c] {};
          \node[state] (e) [below right=of d] {};
          \node[state] (f) [right=of e] {};
          \node[state] (g) [below right=of b] {};
          \node[state] (h) [right=of g] {};
          \path[-]
            (a) edge node {} (b)
            (b) edge node {} (c)
            (c) edge node {} (d)
            (d) edge node {} (e)
            (e) edge node {} (f)
            (g) edge node {} (b)
            (g) edge node {} (h)
            (h) edge node {} (e)
            (b) edge node {} (e);
        \end{tikzpicture}\\[6pt]~} \\\hline
    \end{tabularx}
    \egroup

    \annotate{Since the definition of highly irregular graphs depends on the
      degrees of the nodes, it's probably not a bad idea to annotate each node
      with its degree.}

    \begin{shaded}
      Write your answer here.
    \end{shaded}
\end{enumerate}

Highly irregular graphs have some interesting properties. First, a new
definition. If $G$ is a graph with at least one node, then we'll have
$\boldsymbol{\Delta(G)}$ denote the maximum degree of any of the nodes in $G$.

\begin{enumerate}[resume*]
  \item Draw the simplest possible graph $G$ that has at least two nodes but
    only one node of degree $\Delta(G)$. By ``simplest,'' we mean having as few
    nodes as possible, then as few edges as possible among all graphs with the
    smallest number of nodes. No justification is necessary.

    \begin{shaded}
      Provide a drawing here.
    \end{shaded}
\end{enumerate}

Although graphs in general can have exactly one degree of node $\Delta(G)$,
highly irregular graphs cannot.

\begin{enumerate}[resume*]
  \item Prove that if $G$ is a highly irregular graph and $\Delta(G) \ge 2$,
    then $G$ has at least two nodes of degree $\Delta(G)$. (This theorem is
    also true in the case where $\Delta(G) = 0$ or $\Delta(G) = 1$, but these
    are somewhat degenerate cases and aren't as interesting.)

    \annotate{As a hint, proceed by contradiction. Look back at the pictures
      above that you identified as highly irregular graphs -- do you notice
      anything about where the nodes of degree $\Delta(G)$ are? See if you can
      use that to build out your proof.}

    \begin{shaded}
      Provide a proof here.
    \end{shaded}
\end{enumerate}

As a refresher, a \emph{triangle} in a graph is a group of three different
nodes $x$, $y$, and $z$ where $\{x, y\}$, $\{y, z\}$, and $\{x, z\}$ are all
edges in the graph.

\begin{enumerate}[resume*]
  \item Draw a highly irregular graph that contains a triangle. To make things
    easier for the TAs to grade, please annotate each node with its degree and
    highlight three nodes that form a triangle. For full credit, your solution
    should have ten nodes or fewer. No justification is necessary.

  \annotate{Something to think about: if $G$ is highly irregular and $G$
    contains a triangle, what is the smallest possible value for $\Delta(G)$?
    Based on that and your observations from part (iii) of this problem, what
    does that tell you about the shape of the graph? Use that to guide your
    search.}

  \begin{shaded}
    Provide a drawing here.
  \end{shaded}
\end{enumerate}

\pagebreak

\section{Bipartite Graphs}

There are a few famous families of graphs that come up over and over again. One of the most important types of graphs in computer science is the \textit{bipartite graph}, which is the focus of this problem. \\

Let's begin with a formal definition of bipartite graphs. An undirected graph $G = (V, E)$ is called \emph{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 \textit{\textbf{bipartite classes}} of $G$. To help you get a better sense for why bipartite graphs are important and where they show up, let's work through a couple of examples. 

\begin{enumerate}[label=\roman*]
    \item Consider a graph where each node represents a square on a chessboard and where there's an edge between any pair of squares that are immediately adjacent in one of the four cardinal directions (up, down, left, and right). Explain why this is a bipartite graph by telling us what the bipartite classes are and briefly explaining why all the edges have one endpoint in each bipartite class.

    \annotate{Draw lots of pictures!}
    
    \begin{shaded}
    Write your answer here.
    \end{shaded}

\end{enumerate}

Bipartite graphs have many interesting properties. One of the most fundamental is this one:
\begin{center}
\emph{Theorem:} An undirected graph is bipartite if and only if it contains no cycles of odd length.
\end{center}

The forward direction of this implication has a nice intuition.

\annotate{ Pause to see if you can convince yourself, intuitively, why if $G$ is bipartite, then it has no cycles of odd length. Specifically, why every cycle in $G$ has to have even length.}

The reverse direction of this implication -- that if $G$ has no cycles of odd length, then $G$ is bipartite -- requires a different sort of argument. \\

Let's pick some arbitrary graph $G = (V, E)$ that has no cycles of odd length. For simplicity's sake, we'll assume that $G$ has just one connected component. If $G$ has two or more connected components, we can essentially treat each one of them as independent graphs. \textit{(Do you see why?)} \\

Now, choose any node $v \in V$. Using node $v$ as an ``anchor point,'' we can define two sets $V_1$ and $V_2$ that we'll need for the remainder of this argument:
\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*}
This turns out to be a really useful way to group the nodes of $G$.

\begin{enumerate}[resume*]
\item Given the choices of $G$ and $v$ from above, prove that $V_1$ and $V_2$ have no nodes in common.

\annotate{Remember that there might be multiple different paths of 
different lengths from v to some other node x, so
be careful not to talk about ``the'' path between v and x. Also note that these \emph{do not} have to be \emph{simple} paths.}

\begin{shaded}
Provide a proof here.
\end{shaded}

\item Using your result from part (ii), prove that $G$ is bipartite.

\annotate{The most common mistake on this problem is to not address all the parts of the definition of a bipartite graph. So start off by writing down a list of what you need to prove, then address each part in turn.}

\begin{shaded}
Provide a proof here.
\end{shaded}

\end{enumerate}

\pagebreak

On this problem set, we've included four optional fun problems you can play around with. You're welcome to play around with any number of them, but \emph{please submit answers to at most one of these problems} with your problem set. We, unfortunately, don't have TA bandwidth to grade all of them. If you submit solutions to more than one of them, we'll choose one to grade arbitrarily.

\section*{Optional Fun Problem 1: Hugs All Around! (Extra Credit)}

There's a party with 137 attendees. Each person is either \emph{honest}, meaning that they \textit{always} tell the truth,
or \emph{mischievous}, meaning that they \textit{never} tell the truth. After everything winds down, everyone is asked how many \underline{\emph{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}
Write your answer and proof here.
\end{shaded}

\section*{Optional Fun Problem 2: How Many Functions Are There? (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*}
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}

\section*{Optional Fun Problem Three: Chemical Automorphisms}

Below is a graph of the molecular structure of octomethylcyclotetrasiloxane. How many automorphisms does this graph have? Justify your answer, but no formal proof is required.

% This image takes a very long time to compile, so we've commented it out. Feel free to uncomment
% it if you like.

% \begin{center}
% \begin{minipage}
% \begin{tikzpicture}[every node/.style={circle,draw=black,minimum size=7pt,fill=white}]
% \draw (0:3) node (root1) {} -- (45:3) node (1) {} -- (90:3) node (root2) {} -- (135:3) node (2) {} -- (180:3) node (root3) {} -- (225:3) node (3) {} -- (270:3) node (root4) {} -- (315:3) node (4) {} -- (root1)
% \draw (root1) -- ++ (330:1) node (subtree11) {}
% \draw (subtree11) -- ++ (290:0.8) node (leaf111) {}
% \draw (subtree11) -- ++ (330:0.8) node (leaf112) {}
% \draw (subtree11) -- ++ (40:0.8) node (leaf113) {}
% \draw (root1) -- ++ (30:1) node (subtree12) {}
% \draw (subtree12) -- ++ (350:0.8) node (leaf121) {}
% \draw (subtree12) -- ++ (30:0.8) node (leaf122) {}
% \draw (subtree12) -- ++ (70:0.8) node (leaf123) {}
% \draw (root2) -- ++ (60:1) node (subtree21) {}
% \draw (subtree21) -- ++ (20:0.8) node (leaf211) {}
% \draw (subtree21) -- ++ (60:0.8) node (leaf212) {}
% \draw (subtree21) -- ++ (100:0.8) node (leaf213) {}
% \draw (root2) -- ++ (120:1) node (subtree22) {}
% \draw (subtree22) -- ++ (80:0.8) node (leaf221) {}
% \draw (subtree22) -- ++ (120:0.8) node (leaf222) {}
% \draw (subtree22) -- ++ (160:0.8) node (leaf223) {}
% \draw (root3) -- ++ (150:1) node (subtree31) {}
% \draw (subtree31) -- ++ (110:0.8) node (leaf311) {}
% \draw (subtree31) -- ++ (150:0.8) node (leaf312) {}
% \draw (subtree31) -- ++ (190:0.8) node (leaf313) {}
% \draw (root3) -- ++ (210:1) node (subtree32) {}
% \draw (subtree32) -- ++ (170:0.8) node (leaf321) {}
% \draw (subtree32) -- ++ (210:0.8) node (leaf322) {}
% \draw (subtree32) -- ++ (250:0.8) node (leaf323) {}
% \draw (root4) -- ++ (240:1) node (subtree41) {}
% \draw (subtree41) -- ++ (200:0.8) node (leaf411) {}
% \draw (subtree41) -- ++ (240:0.8) node (leaf412) {}
% \draw (subtree41) -- ++ (280:0.8) node (leaf413) {}
% \draw (root4) -- ++ (300:1) node (subtree42) {}
% \draw (subtree42) -- ++ (260:0.8) node (leaf421) {}
% \draw (subtree42) -- ++ (300:0.8) node (leaf422) {}
% \draw (subtree42) -- ++ (340:0.8) node (leaf423) {};
% \end{tikzpicture}
% \end{minipage}
% \end{center}

\begin{shaded}
Write your answer and justification here.
\end{shaded}


\section*{Optional Fun Problem 4: Chromatic and Independence Numbers}
Recall that if $G$ is a graph, then $\chi(G)$ represents the \emph{chromatic number} of $G$, the minimum number of colors needed to paint each node of $G$ so no two adjacent nodes of $G$ are the same color. The \emph{independence number} of a graph, denoted $\alpha(G)$, is the size of the largest independent set in $G$. \\

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). \\

\annotate{You should definitely check out what the Guide to Proofs on Discrete Structures' advice for proving $P \lor Q$.}

\begin{shaded}
Provide a proof here.
\end{shaded}


\end{document}