\Question{Optimal Partners}
In the notes, we proved that the SMA always outputs the male-optimal pairing. However, we never explicitly showed why it is guaranteed that putting every man with his best choice results in a pairing at all. Prove by contradiction that no two men can have the same optimal partner. (Note: your proof should not rely on the fact that the SMA outputs the male-optimal pairing.)
\Question{Relaxed Timing}
Suppose that when running the SMA, we relax the rules for the men, so that each unpaired man proposes to the next woman on his list at a time of his choice (some men might procrastinate for several days, while others might propose and get rejected several times in a single day). Can the order of the proposals change the resulting pairing? Give an example of such a change or prove that the pairing that results is the same.
\Question{Connectivity}
Prove the following claims regarding connectivity:
\begin{Parts}
\Part If $G$ is a graph with $n$ vertices such that for any two non-adjacent vertices $u$, $v$, it holds that $\deg u + \deg v \ge n - 1$, then $G$ is connected.
\Part Give an example to show that if the condition $\deg u + \deg v \ge n - 1$ is replaced with $\deg u + \deg v \ge n - 2$, then $G$ is not necessarily connected.
% \Part If $G = (V, E)$ is not connected, then $G^c = (V, \{\{u, v\} | \{u, v\} \not\in E\})$, the complement of $G$, is connected.
\Part For a graph $G$ with $n$ vertices, if the minimum degree of each vertex is at least $n/2$, then $G$ is connected.
\Part If there are exactly two vertices with odd degrees in a graph, then they must be connected to each other (meaning, there is a path connecting these two vertices).
\end{Parts}
\Question{Edge Complement}
\begin{figure}[H]
\centering
\includegraphics[width=0.8\textwidth]{src/problems/graphtheory/resources/S2.png}
\end{figure}
The \textbf{edge complement} graph of a graph $G = (V,E)$ is a graph $G' = (V',E')$, such that $V' = E$, and $(i,j) \in E'$ if and only if $i$ and $j$ had a common vertex in $G$. In the above picture, the graph on the right is the edge complement of the graph on the left: for every edge $e_{\{i,j\}}$ in the graph on the left there is a vertex in the graph on the right. If two edges $e_{\{i,j\}}$ and $e_{\{j,k\}}$ share a vertex $j$ on the left, then the corresponding vertices on the right have an edge $j$ connecting them.
\begin{Parts}
\Part Prove or disprove: if a graph $G$ has an Eulerian tour, then its \textbf{edge complement} graph has an Eulerian tour.
\Part Prove or disprove: if a graph's \textbf{edge complement} graph $G'$ has an Eulerian tour, then graph $G$ has an Eulerian tour.
\end{Parts}
\Question{Always, Sometimes, or Never}
In each part below, you are given some information about a graph $G$. Using only the information in the current part, say whether $G$ will always be planar, always be non-planar, or could be either. If you think it is always planar or always non-planar, prove it. If you think it could be either, give a planar example and a non-planar example.
\begin{Parts}
\Part $G$ can be vertex-colored with $4$ colors.
\Part $G$ requires 7 colors to be vertex-colored.
\Part $e \leq 3v - 6$, where $e$ is the number of edges of $G$ and $v$ is the number of vertices of $G$.
\Part $G$ is connected, and each vertex in $G$ has degree at most 2.
\Part Each vertex in $G$ has degree at most 2.
\end{Parts}
\Question{Bipartite Graphs}
An undirected graph is bipartite if its vertices can be partitioned into two disjoint sets $L$, $R$ such that each edge connects a vertex in $L$ to a vertex in $R$ (so there does not exist an edge that connects two vertices in $L$ or two vertices in $R$).
\begin{Parts}
\Part
Suppose that a graph $G$ is bipartite, with $L$ and $R$ being a bipartite partition of the vertices. Prove that $\sum\limits_{v \in L} \deg(v) = \sum\limits_{v \in R} \deg(v)$.
\Part
Suppose that a graph $G$ is bipartite, with $L$ and $R$ being a bipartite partition of the vertices. Let $s$ and $t$ denote the average degree of vertices in $L$ and $R$ respectively. Prove that $s/t = |R|/|L|$.
\Part
A double of a graph $G$ consists of two copies of $G$ with edges joining
the corresponding ``mirror'' points. Now suppose that $G_1$ is a bipartite
graph, $G_2$ is a double of $G_1$, $G_3$ is a double of $G_2$, and so on.
Show that $\forall n \geq 1$, $G_n$ is bipartite.
\Part
Prove that a graph is bipartite if and only if it can be $2$-colored.
\end{Parts}
\Question{Countability Practice}
\begin{Parts}
% \Part
% Are the following sets finite, countably infinite, or uncountably infinite?
% \begin{Parts}
% \Part The set of subsets of $A$, where $A$ is a countably infinite set.
% \Part The set of all words of length $n$ over a finite alphabet.
% \Part The set of all words (of finite length) over a finite alphabet.
% \Part The set of all languages over a given alphabet. (A language can be considered as the set of all words over an alphabet.)
% \end{Parts}
\Part
Prove or disprove: The set of increasing functions $f : \N \rightarrow \N$ (i.e., if $x \geq y $, then $f(x) \geq f(y)$) is countable.
\Part
Prove or disprove: The set of decreasing functions $f : \N \rightarrow \N$ (i.e., if $x \geq y$, then $f(x) \leq f(y))$ is countable.
\Part Is a set of disks in $\R^2$ such that no two disks overlap necessarily countable or possibly uncountable? [A disk is a region in the plane of the form $\{(x, y) \in \R^2 : (x - x_0)^2 + (y - y_0)^2 \le r^2\}$, for some $x_0, y_0, r \in \R$, $r > 0$.]
\Part Is a set of circles in $\R^2$ such that no two circles overlap necessarily countable or possibly uncountable? [\textit{Hint}: A circle is a subset of the plane of the form $\{(x, y) \in \R^2 : (x - x_0)^2 + (y - y_0)^2 = r^2\}$ for some $x_0, y_0, r \in \R$, $r > 0$. The difference between a circle and a disk is that a disk contains all of the points in its interior, whereas a circle does not.]
\end{Parts}
\Question{Impossible Programs}
Show that none of the following programs can exist.
\begin{Parts}
\Part
Consider a program $P$ that takes in any program $F$, input $x$ and output $y$ and returns true if
$F(x)$ outputs $y$ and returns false otherwise.
\nosolspace{0.5in}
\Part
Consider a program $P$ that takes in any program $F$ and returns true if $F(F)$ halts and returns
false if it doesn't halt.
\nosolspace{0.5in}
\Part
Consider a program $P$ that takes in any programs $F$ and $G$ and returns true if $F$ and $G$ halt
on all the same inputs and returns false otherwise.
\nosolspace{0.5in}
\end{Parts}