\include{preamble}
\setcounter{try}{40}
\renewcommand{\thefootnote}{\fnsymbol{footnote}}
\title{}
\author{Zajj Daugherty}
\date{\today}
\usepackage{multicol}
\begin{document}
\begin{flushright}
SOLUTIONS\\
Homework 9\\
Due 4/17/19
\end{flushright}
%-----------------% HANDOUT 15 %-----------------%
\begin{try}Use inclusion/exclusion to answer the following questions.
\begin{enumerate}[(a)]
\item How many elements are in $A_1 \cup A_2$ if there are 12 elements in $A_1$, 18 elements in $A_2$, and
\begin{enumerate}[(i)]
\item $|A_1 \cap A_2| = 6$?
\begin{ans}
We have
$$|A_1 \cup A_2| = |A_1| + |A_2| - |A_1 \cap A_2| = 12 + 18 - 6 = \fbox{$24$}.$$
\end{ans}
\item $A_1 \cap A_2 = \emptyset$?
\begin{ans}
We have $|A_1 \cap A_2|= |\emptyset| = 0$, so that
$$|A_1 \cup A_2| = |A_1| + |A_2| - |A_1 \cap A_2| = 12 + 18 - 0 = \fbox{$30$}.$$
\end{ans}
\item $A_1 \subseteq A_2$?
\begin{ans}
Since $A_1 \subseteq A_2$ have $A_1 \cap A_2 = A_2$. So $|A_1 \cap A_2|= |A_2| = 18$, so that
$$|A_1 \cup A_2| = |A_1| + |A_2| - |A_1 \cap A_2| = 12 + 18 - 18 = \fbox{$12$}.$$
Note that $A_1 \cup A_2 = A_1$, so $|A_1 \cup A_2| = |A_1| = 12$, which matches.
\end{ans}
\end{enumerate}
\medskip
\item A survey of households in the United States reveals that 96\% have at least one television set, 42\% have a land-line telephone service, and 39\% have land-line telephone service and at least one television set. What percentage of households in the United States have neither telephone service nor a television set?\\
{\small [Start by naming your sets, as in ``Let $A$ be the set of households that have at least one TV set," and so on.]}
\begin{ans}
Let $A$ be the set of households that have at least one TV set, let $B$ be the set of households that have a land-line, and let $U$ be the total set of surveyed households. Then $|A| = 0.96*|U|$, $|B| = 0.42*|U|$, and $|A \cap B| = 0.39*|U|$. Thus
\begin{align*}
\text{\% households with neither TV nor landline}
&= \frac{|U| - |A \cup B|}{|U|}\\
&= 1 - \frac{|A| + |B| - |A \cap B|}{|U|}\\
&= 1 - \left(0.96 + 0.42 - 0.39\right)\\
&= 1-0.99 = \fbox{$1\%$}.
\end{align*}
\end{ans}
\pagebreak
\item How many students are enrolled in a course either in
\centerline{(1) \emph{calculus 1}, \qquad (2) \emph{discrete math},}
\centerline{(3) \emph{data structures}, \quad or \quad (4) \emph{intro to computer science}}
\noindent at a school if there are 507, 292, 312, and 344 students in these courses, respectively; 14 in both calculus and data structures; 213 in both calculus and intro to CS; 211 in both discrete mathematics and data structures; 43 in both discrete mathematics and intro to CS; and no student may take calculus and discrete mathematics at the same time, nor intro to CS and data structures at the same time?\\
{\small [Again, start by naming your sets, as in ``Let $A$ be the set of students enrolled in calculus 1," and so on.]}
\begin{ans}
Let
\begin{align*}
A & = \{ \text{ students enrolled in calculus 1 } \},\\
B & = \{ \text{ students enrolled in discrete math } \},\\
C & = \{ \text{ students enrolled in data structures } \},\\
D & = \{ \text{ students enrolled in intro to computer science } \}.
\end{align*}
Then
$$|A| = 507, \quad |B| = 292, \quad |C| = 312, \quad |D| = 344,$$
$$|A \cap C| = 14, \quad |A \cap D| = 213, \quad |B \cap C| = 211,$$
$$|B \cap D| = 43, \quad |A\cap B| = 0, \quad \text{and} \quad |C \cap D| = 0.$$
Moreover, since $A \cap B = C \cap D = \emptyset$, the intersection of any three sets is also empty, as is the intersection of all four sets. Thus
$$|A \cup B \cup C \cup D| = 507 + 292 + 312 + 344 - (14 + 213 + 211 + 43) = \fbox{$974$}.$$
\end{ans}
\item Find the number of integers $1 \le n \le 100$ that are odd and/or the square of an integer.
\begin{ans}
In that range, there are $50$ odd integers $9$ squares of integers. Of those squares, there are 5 that are odd:
$$1^2,\ 3^2,\ 5^2,\ 7^2, \quad \text{and}\quad 9^2.$$
Thus there are
$$50 + 9 - 5 = \fbox{$54$}$$
integers in that range that are odd and/or the square of an integer.
\end{ans}
\item Find the number of integers $1 \le n \le 500$ that are \emph{not} a multiple of $3$, $5$, or $7$.
\begin{ans}
In that range, there are
\begin{enumerate}[\quad]
\item $\lfloor 500/3 \rfloor = 166$ multiples of $3$,
\item $\lfloor 500/5 \rfloor=100$ multiples of $5$,
\item $\lfloor 500/7 \rfloor=71$ multiples of $7$,
\item $\lfloor 500/(3 \cdot 5) \rfloor = 33$ multiples of $3$ and $5$,
\item $\lfloor 500/ (3 \cdot 7)\rfloor = 23$ multiples of $3$ and $7$,
\item $\lfloor 500/ (5 \cdot 7)\rfloor = 14$ multiples of $5$ and $7$, and
\item $\lfloor 500/ (3 \cdot 5 \cdot 7)\rfloor = 4$ multiples of $3$, $5$, and $7$.
\end{enumerate}
Thus, there are
$$166 + 100 + 71 - (33 + 23 + 14) + 4 = 271$$
integers in that range that are multiples of $3$, $5$, and/or $7$.
Therefore, there are $500 - 271 = \fbox{$229$}$ integers in that range that \emph{aren't} multiples of $3$, $5$, or $7$.
\end{ans}
\end{enumerate}
\end{try}
\vfill
\begin{try} Recall that the \emph{Stirling numbers (of the second kind)} count arrangements of distinguishable objects into indistinguishable boxes, namely
$$S(n,k) = \left|\left\{ \begin{matrix}\text{Ways to place $n$ distinguishable objects}\\
\text{into $k$ indistinguishable boxes}\\
\text{so that no box is left empty}
\end{matrix}\right\}\right|.$$
We stated in section 6.5 that
$$S(n,k) = \frac{1}{k!} \sum_{\ell=0}^{k-1} (-1)^\ell \binom{n}{\ell} (k - \ell)^n.$$
We can now check this using inclusion/exclusion!
\medskip
But first, we count the number of surjective functions from $X = \{1, 2, \dots, n\}$ to $Y = \{1, \dots, k\}$ (where $k \le n$). To that end, let $U$ be the set of \emph{all} functions from $X$ to $Y$, and for $i = 1, \dots, k$, let
$$A_i = \{ \text{functions } f: X \to Y ~|~ i \notin f(X)\}.$$
\begin{enumerate}[(a)]
\item What is $|U|$, i.e.\ how many functions are there from $X$ to $Y$? \\
{[Don't put any restrictions on the functions here---this is a simple product rule question.]}
\begin{ans}
Using the product rule, there are \fbox{$k^n$} functions from $X$ to $Y$ ($k$ choices for the image of $1$, $k$ choices for the image of $2$, and so on).
\end{ans}
\item For $X = \{1,2,3\}$ and $Y = \{1,2, 3\}$, we have
$$A_1 = \{ f_1, f_2, f_3, f_4, f_5, f_6, f_7, f_8\}$$
where
$$
f_1 \text{ sends } \begin{matrix}1 \mapsto 2,\\2 \mapsto 2,\\3 \mapsto 2;\end{matrix}
\qquad
f_2 \text{ sends } \begin{matrix}1 \mapsto 3,\\2 \mapsto 2,\\3 \mapsto 2;\end{matrix}
\qquad
f_3 \text{ sends } \begin{matrix}1 \mapsto 2,\\2 \mapsto 3,\\3 \mapsto 2;\end{matrix}
\qquad
f_4 \text{ sends } \begin{matrix}1 \mapsto 2,\\2 \mapsto 2,\\3 \mapsto 3;\end{matrix}
$$
\smallskip
$$
f_5 \text{ sends } \begin{matrix}1 \mapsto 3,\\2 \mapsto 3,\\3 \mapsto 2;\end{matrix}
\qquad
f_6 \text{ sends } \begin{matrix}1 \mapsto 3,\\2 \mapsto 2,\\3 \mapsto 3;\end{matrix}
\qquad
f_7 \text{ sends } \begin{matrix}1 \mapsto 2,\\2 \mapsto 3,\\3 \mapsto 3;\end{matrix}
\quad \text{and}\quad
f_8 \text{ sends } \begin{matrix}1 \mapsto 3,\\2 \mapsto 3,\\3 \mapsto 3.\end{matrix}
$$
\begin{enumerate}[(i)]
\item What is $A_2$?\hfill
{[Describe the \emph{set}, not its size.]}
\begin{ans}
We have
$$A_2 = \{ g_1, g_2, g_3, g_4, g_5, g_6, g_7, g_8\}$$
where
$$
g_1 \text{ sends } \begin{matrix}1 \mapsto 1,\\2 \mapsto 1,\\3 \mapsto 1;\end{matrix}
\qquad
g_2 \text{ sends } \begin{matrix}1 \mapsto 3,\\2 \mapsto 1,\\3 \mapsto 1;\end{matrix}
\qquad
g_3 \text{ sends } \begin{matrix}1 \mapsto 1,\\2 \mapsto 3,\\3 \mapsto 1;\end{matrix}
\qquad
g_4 \text{ sends } \begin{matrix}1 \mapsto 1,\\2 \mapsto 1,\\3 \mapsto 3;\end{matrix}
$$
\smallskip
$$
g_5 \text{ sends } \begin{matrix}1 \mapsto 3,\\2 \mapsto 3,\\3 \mapsto 1;\end{matrix}
\qquad
g_6 \text{ sends } \begin{matrix}1 \mapsto 3,\\2 \mapsto 1,\\3 \mapsto 3;\end{matrix}
\qquad
g_7 \text{ sends } \begin{matrix}1 \mapsto 1,\\2 \mapsto 3,\\3 \mapsto 3;\end{matrix}
\quad \text{and}\quad
g_8 \text{ sends } \begin{matrix}1 \mapsto 3,\\2 \mapsto 3,\\3 \mapsto 3.\end{matrix}
$$
\end{ans}
\pagebreak
\item What is $A_1 \cap A_2$?
\begin{ans}
This is the set of functions from $X = \{1,2,3\}$ to $Y = \{1,2,3\}$ whose image doesn't contain 1 or 2, i.e.\ the set of functions from $\{1,2,3\}$ to $\{3\}$. Thus
$$A_1 \cap A_2 = \{h\}, \quad \text{where} \quad h: 1,2,3 \mapsto 3.$$
\end{ans}
\item What is $A_1 \cap A_2 \cap A_3$? \\
{[You should be able to do this without computing $A_3$.]}
\begin{ans}
This is the set of functions from $X = \{1,2,3\}$ to $Y = \{1,2,3\}$ whose image doesn't contain 1, 2, or 3, i.e.\ the set of functions from $\{1,2,3\}$ to $\emptyset$. No such function exists, so $A_1 \cap A_2 \cap A_3 = \emptyset$.
\end{ans}
\end{enumerate}
\item Explain why, for general $n$ and $k$, we have the following:
\begin{enumerate}[(i)]
\item $|A_1| = (k-1)^n$;
\begin{ans}
This is the set of functions from $X = \{1, \dots, n\}$ to $Y = \{1, \dots, k\}$ whose image doesn't contain 1, i.e.\ the set of functions from $ \{1, \dots, n\}$ to $\{2, 3, \dots, k\}$. Using the product rule as in part (a), this gives
$$|A_1| = |\{2, 3, \dots, k\}|^{|X|} = (k-1)^n,$$
as desired.
\end{ans}
\item $|A_ 1 \cap A_2| = (k-2)^n$;
\begin{ans}
This is the set of functions from $X = \{1, \dots, n\}$ to $Y = \{1, \dots, k\}$ whose image doesn't contain 1 or 2, i.e.\ the set of functions from $ \{1, \dots, n\}$ to $\{3, 4, \dots, k\}$. Using the product rule as in part (a), this gives
$$|A_1 \cap A_2| = |\{3, 4, \dots, k\}|^{|X|} = (k-2)^n,$$
as desired.
\end{ans}
\item $|A_1 \cap A_2 \cap \cdots \cap A_{\ell}| = (k-\ell)^n$ (for any $\ell \leq k$);
\begin{ans}
Similarly to the previous two parts, this is the set of functions from from $X = \{1, \dots, n\}$ to $Y - \{1, \dots, \ell\} = \{\ell+1, \ell+2, \dots, k\}$. Using the product rule as in part (a), this gives
$$|A_1 \cap A_2| = |\{\ell+1, \ell+2, \dots, k\}|^{|X|} = (k-\ell)^n,$$
as desired.
\end{ans}
\pagebreak
\item $|A_1 \cap A_2 \cap \cdots \cap A_k| = 0$.
\begin{ans}
Similarly to part (b)(iii), this is the set of functions from from $X$ to $\emptyset$, of which there are none.
\end{ans}
\end{enumerate}
\item Explain why for any subset $S \subseteq \{A_1, A_2, \dots, A_k\}$ of size $\ell$, we have
$$\left| \bigcap_{A_i \in S} A_i \right| = |A_1 \cap \cdots \cap A_\ell|.$$
{[For example $|A_1 \cap A_3 \cap A_7| = |A_1 \cap A_2 \cap A_3|$.]}
\begin{ans}
Note that for any finite sets $C$ and $D$, then number of functions from $C$ to $D$ depends entirely on the sizes of the domain and codomain, i.e.\ $|D|^{|C|}$. Since the domain is always $X$, and though the codomain corresponding to $A_1 \cap \cdots \cap A_\ell$ (which is $\{\ell+1, \ell+2, \dots, k\}$) and to $\bigcap_{A_i \in S} A_i $ (which is $Y - \{i ~|~ A_i \in S\}$) are different, they are both of size $k - \ell$. So
$$\left| \bigcap_{A_i \in S} A_i \right| = (k - \ell)^n = |A_1 \cap \cdots \cap A_\ell|.$$
For example,
$$|A_1 \cap A_3 \cap A_7| = (k-3)^n = |A_1 \cap A_2 \cap A_3|.$$
\end{ans}
\item Use inclusion/exclusion to give a formula for $|A_1 \cup A_2 \cup \cdots \cup A_k|$.
\begin{ans}
We have
\begin{align*}
|A_1 \cup A_2 \cup \cdots \cup A_k| &= \sum_{S \subseteq \{A_1, A_2, \dots, A_k\} \atop S \neq \emptyset} (-1)^{|S| +1} \left| \bigcap_{A_i \in S} A_i \right|, & \quad \text{by inclusion/exclusion},\\
&= \sum_{\ell=1}^k (-1)^{\ell+1} \sum_{S \subseteq \{A_1, A_2, \dots, A_k\} \atop |S|=\ell}
\left|\bigcap_{A_i \in S} A_i \right|, & \begin{matrix}\text{grouping by number of}\\\text{sets in the intersection}\end{matrix}\\
&= \sum_{\ell=1}^k (-1)^{\ell+1} \sum_{S \subseteq \{A_1, A_2, \dots, A_k\} \atop |S|=\ell}
\left| A_1 \cap \cdots \cap A_\ell \right|, & \text{by part (d),}\\
&= \sum_{\ell=1}^k (-1)^{\ell+1} \binom{n}{\ell}
\left| A_1 \cap \cdots \cap A_\ell \right|, \\
&= \sum_{\ell=1}^k (-1)^{\ell+1} \binom{n}{\ell} (k - \ell)^n, & \text{by part (c)(iii).}\\
\end{align*}
\end{ans}
\pagebreak
\item Explain why the set of surjective functions $f: X \to Y$ is
$$\overline{A_1 \cup A_2 \cup \cdots \cup A_k}, \quad \text{i.e.} \quad U - A_1 \cup A_2 \cup \cdots \cup A_k.$$
\item Use the last two parts, together with part (a), to give the number of surjective functions from $X$ to $Y$.\hfill
{[Your answer should line up Theorem 1 in Section 8.6.]}
\begin{ans}
Note that $A_1 \cup A_2 \cup \cdots \cup A_k$ is the set of functions whose image is missing at least one of $1$, $2$, \dots, $k-1$, or $k$. Thus $\overline{A_1 \cup A_2 \cup \cdots \cup A_k}$ is the set of functions that \emph{isn't} missing any of $1$, $2$, \dots, $k-1$, or $k$, i.e.\ the set of function that are surjective.
\end{ans}
\item Use division rule to explain why $S(n,k)$ is $\frac{1}{k!}$ times your answer to (g). Check that this agrees with the formula we gave above.
\begin{ans}
Supposing we knew $S(n,k)$, we could compute the number of surjective functions in another way. Namely, we can build a surjective function from $X$ to $Y$ as follows:
\begin{enumerate}[\quad]
\item First, choose how the preimages partition $X$;
\item then choose how to assign the preimages to values in $Y$.
\end{enumerate}
For example, if $n = 5$ and $k = 3$, one partition of $X$ into three sets is
$$\{1,4\}, \{2,3\}, \text{ and } \{5\}.$$
Then one way to assign those preimages to the values of $Y$ are
$$\{1,4\} \mapsto 1, \quad \{2,3\}\mapsto 3, \quad \text{and} \quad \{5\} \mapsto 2.$$
In other words we've built the surjective function
$$1 \mapsto 1, \quad 2 \mapsto 3, \quad 3 \mapsto 3, \quad 4 \mapsto 1, \quad\text{and}\quad 5 \mapsto 2.$$
Since we're building surjective functions, we must have exactly $k$ nonempty subsets, and therefore there are $S(n,k)$ ways to do the first step. And since those subsets have to match bijectively to the elements of the image, there are $k!$ ways to do the second step. So
$$\#\{ \text{ surjective functions from $X$ to $Y$ } \} = S(n,k) \cdot k!,$$
and hence
\begin{align*}
S(n,k) &= \#\{ \text{ surjective functions from $X$ to $Y$ } \}/k! \\
&= \frac{1}{k!}\left(k^n - \sum_{\ell=1}^k (-1)^{\ell+1} \binom{n}{\ell} (k - \ell)^n\right)\\
&= \frac{1}{k!} \sum_{\ell=0}^k (-1)^{\ell} \binom{n}{\ell} (k - \ell)^n,
\end{align*}
as desired.
\end{ans}
\end{enumerate}
\end{try}
\pagebreak
\begin{try}(Relations) \label{try:relations}
\begin{enumerate}[(a)]
\item
Which of these relations on $\{0, 1, 2, 3\}$ are equivalence relations? For those that are not, what properties do they lack?
\begin{enumerate}[(i)]
\item $\{ 0 \sim 0 , 1 \sim 1 , 2 \sim 2 , 3 \sim 3\}$
\begin{ans}
This is an equivalence relation.
\end{ans}
\item $\{ 0 \sim 0 , 0 \sim 2 , 2 \sim 0 , 2 \sim 2 , 2 \sim 3 , 3 \sim 2 , 3 \sim 3\}$
\begin{ans}
This relation is symmetric, but is not reflexive ($1 \not\sim 1$) and is not transitive ($0 \sim 2$ and $2 \sim 3$, but $0 \not\sim 3$).
\end{ans}
\item $\{ 0 \sim 0 , 1 \sim 1 , 1 \sim 2 , 2 \sim 1 , 2 \sim 2 , 3 \sim 3\}$
\begin{ans}
This is an equivalence relation.
\end{ans}
\item $\{ 0 \sim 0 , 1 \sim 1 , 1 \sim 3 , 2 \sim 2 , 2 \sim 3 , 3 \sim 1 , 3 \sim 2 , 3 \sim 3\}$
\begin{ans}
This relation is symmetric and reflexive, but is not transitive ($1 \sim 3$ and $3 \sim 2$, but $1 \not\sim 2$).
\end{ans}
\item $\{ 0 \sim 0 , 0 \sim 1 , 0 \sim 2 , 1 \sim 0 , 1 \sim 1 , 1 \sim 2 , 2 \sim 0 , 2 \sim 2 , 3 \sim 3\}$
\begin{ans}
This relation is reflexive, but not symmetric ($1 \sim 2$ but $2 \not\sim 1$) and is not transitive ($2 \sim 0$ and $0 \sim 1$, but $2 \not\sim 1$).
\end{ans}
\end{enumerate}
\medskip
\item For each of the equivalence relations in part (a), list the equivalence classes.
\begin{ans}The equivalence classes are as follows.
\begin{enumerate}[(a)]
\item[(a)] $[0] = \{0\}$, $[1] = \{1\}$, $[2] = \{2\}$, $[3] = \{3\}$.
\item[(c)] $[0] = \{0\}$, $[1] = [2] = \{1,2\}$, $[3] = \{3\}$.
\end{enumerate}
\end{ans}
\item Which of these relations on the set of all people are equivalence relations? For those that are not, what properties do they lack?\begin{enumerate}[(i)]
\item $a \sim b$ if $a$ and $b$ are the same age;
\begin{ans}
This is an equivalence relation:
\begin{enumerate}[1.]
\item A person is the same age as themselves.
\item If person $a$ is the same age as person $b$, the $b$ is the same age as $a$.
\item If $a$ and $b$ are the same age and $b$ and $c$ are the same age, then $a$ and $c$ are the same age.
\end{enumerate}
\end{ans}
\pagebreak
\item $a \sim b$ if $a$ and $b$ have the same parents;
\begin{ans}
This is an equivalence relation:
\begin{enumerate}[1.]
\item A person has the same parents as themselves.
\item If person $a$ has the same parents as person $b$, the $b$ has the same parents as $a$.
\item If $a$ and $b$ have the same parents and $b$ and $c$ have the same parents, then $a$ and $c$ have the same parents.
\end{enumerate}
\end{ans}
\item $a \sim b$ if $a$ and $b$ share a common parent;
\begin{ans}
This is not an equivalence relation since it's not transitive. For example, if $a$ and $b$ share a mother but not a father, and $b$ and $c$ share a father but not a mother, then $a$ and $c$ don't necessarily share a parent in common. It is, however symmetric and reflexive.
\end{ans}
\item $a \sim b$ if $a$ and $b$ have met;
\begin{ans}
This relation is symmetric and reflexive, but is not transitive. If $a$ and $b$ have met and $b$ and $c$ have met, it is not necessarily true that $a$ and $c$ have met.
\end{ans}
\item $a \sim b$ if $a$ and $b$ speak a common language.
\begin{ans}
This relation is symmetric and reflexive, but is not transitive. For example, it may be the case that $b$ speaks English and French, $a$ speaks only English, and $c$ speaks only French.
\end{ans}
\end{enumerate}
\medskip
\item For the following relations on $A$ determine whether they are reflexive, symmetric, and/or transitive. State whether they are equivalence relations or not, and if they are describe their equivalence classes.
\begin{enumerate}
\item Let $A=\ZZ$ and define $\sim$ by $a\sim b$ whenever $a- b$ is odd.
\begin{ans}
This is symmetric, since $a-b = 2k+1$ implies $b-a = -(2k + 1) = 2(-k-1) + 1$. But it is not an equivalence relation since it isn't reflexive or transitive. In particular, for any $a \in \ZZ$, we have $a-a = 0 = 2\cdot 0$, which is even. And for any $a,b,c \in \ZZ$ satisfying $a-b = 2k+1$ and $b-c = 2\ell + 1$, we have
$$a - c = (a-b) + (b-c) = 2k + 1 + 2 \ell + 2 = 2(k + \ell + 1),$$
which is even.
\end{ans}
\item Let $A=\RR$ and define $\sim$ by $a\sim b$ whenever $ab \neq 0$.
\begin{ans}
This is symmetric, since $ab \neq 0$ implies $ba = ab \neq 0$. It is also transitive, since $ab \neq 0$ implies $a \neq 0$; and $bc \neq 0$ implies $ c \neq 0$; and hence $ac \neq 0$. But this is not an equivalence relation since it's not reflexive: $0 \nsim 0$ since $0 \cdot 0 = 0$.
\end{ans}
\pagebreak
\item Let $A = \{f: \ZZ \to \ZZ\}$ and define $\sim$ by $f \sim g$ whenever $f(1) = g(1)$.
\begin{ans}
This is an equivalence relation: for all $f, g, h \in A$ we have
\begin{enumerate}[1.]
\item $f \sim f$ since $f(1) = f(1)$;
\item if $f \sim g$ then $f(1) = g(1)$, so $g(1) = f(1)$ and hence $g \sim f$; and
\item if $f \sim g$ and $g \sim h$, then $f(1) = g(1)$ and $g(1) = h(1)$, so that $f(1) = g(1) = h(1)$, and hence $f \sim h$.
\end{enumerate}
Then the equivalence classes are
$$\cC_i = \{ f: \ZZ \to \ZZ ~|~ f(1) = i \}$$
for each $i \in \ZZ$.
\end{ans}
\end{enumerate}
\medskip
\item Verify that the relation
$$f(x) \sim g(x) \qquad \text{ if } \qquad \frac{d}{dx}f(x) = \frac{d}{dx}g(x)$$
is an equivalence relation on the set
$$D = \{ \text{differentiable functions $\varphi: \RR \to \RR$}\},$$
and describe the set of functions that are equivalent to $f(x) = x^2$.
\begin{ans}Checking the properties of equivalence relations one-by-one, let $f, g$, and $h$ be differentiable functions from $\RR$ to $\RR$.
\begin{enumerate}[1.]
\item Reflexive: $f' = f'$ $\checkmark$
\item Symmetric: If $f' = g'$, then $g' = f'$ $\checkmark$
\item Transitive: If $f'=g'$ and $g' = h'$, then $f' = h'$.
\end{enumerate}
The equivalence class corresponding to $x^2$ is
$$\{x^2 + c ~|~ c \in \RR\},$$
since $f' = \frac{d}{dx} x^2 = 2x$ if and only if $f = \int 2x dx = x^2 + c$ (for $c \in \RR$).
\end{ans}
\end{enumerate}
\end{try}
\pagebreak
%-----------------% HANDOUT 16 %-----------------%
\begin{try}(Relations and digraphs)
For each the relations in Exercise 43(a), draw the corresponding directed graph where
$V = \{0,1,2,3\}$ and
$$a \to b \qquad \text{ if } \qquad a \sim b.$$
What properties of the directed graphs correspond to the symmetric, reflexive, and transitive properties of the corresponding relations? For the digraphs corresponding to equivalence relations, what do the equivalence classes look like?
\begin{ans}
$$\text{(i) } \begin{matrix}
\begin{tikzpicture}
\foreach \x in {0,1,2,3}{
\node[bV, label=below:{\tiny$\x$}] (\x) at (\x,1) {};
}
\foreach \x in {0,1,2,3}{ \draw[->, shorten >= 1pt] (\x) .. controls +(.25,.5) and +(-.25,.5) .. (\x);}
\end{tikzpicture}
\end{matrix}\qquad\qquad
\text{(ii) } \begin{matrix}
\begin{tikzpicture}
\node[bV, label=below:{\tiny$0$}] (1) at (0,0) {};
\node[bV, label=above:{\tiny$1$}] (0) at (0,1) {};
\node[bV, label=above:{\tiny$2$}] (2) at (1,1) {};
\node[bV, label=below:{\tiny$3$}] (3) at (1,0) {};
\draw[->, shorten >= 1pt] (0) .. controls +(-.5,0) and +(-.5,.5) .. (0);
%\draw[->, shorten >= 1pt] (1) .. controls +(-.5,0) and +(-.5,.5) .. (1);
\draw[->, shorten >= 1pt] (2) .. controls +(.5,0) and +(.5,.5) .. (2);
\draw[->, shorten >= 1pt] (3) .. controls +(.5,0) and +(.5,-.5) .. (3);
\draw[->, shorten >= 1pt] (0) to [bend right] (2);
\draw[->, shorten >= 1pt] (2) to [bend right] (0);
\draw[->, shorten >= 1pt] (3) to [bend right] (2);
\draw[->, shorten >= 1pt] (2) to [bend right] (3);
\end{tikzpicture}
\end{matrix}$$
\smallskip
$$\text{(iii) } \begin{matrix}
\begin{tikzpicture}
\node[bV, label=below:{\tiny$0$}] (0) at (0,0) {};
\node[bV, label=above:{\tiny$1$}] (1) at (0,1) {};
\node[bV, label=above:{\tiny$2$}] (2) at (1,1) {};
\node[bV, label=below:{\tiny$3$}] (3) at (1,0) {};
\draw[->, shorten >= 1pt] (0) .. controls +(-.5,0) and +(-.5,-.5) .. (0);
\draw[->, shorten >= 1pt] (1) .. controls +(-.5,0) and +(-.5,.5) .. (1);
\draw[->, shorten >= 1pt] (2) .. controls +(.5,0) and +(.5,.5) .. (2);
\draw[->, shorten >= 1pt] (3) .. controls +(.5,0) and +(.5,-.5) .. (3);
\draw[->, shorten >= 1pt] (1) to [bend right] (2);
\draw[->, shorten >= 1pt] (2) to [bend right] (1);
\end{tikzpicture}
\end{matrix}\qquad\qquad \qquad
\text{(iv) }\begin{matrix}
\begin{tikzpicture}
\node[bV, label=below:{\tiny$1$}] (0) at (0,0) {};
\node[bV, label=above:{\tiny$0$}] (1) at (0,1) {};
\node[bV, label=above:{\tiny$2$}] (2) at (1,1) {};
\node[bV, label=below:{\tiny$3$}] (3) at (1,0) {};
\draw[->, shorten >= 1pt] (0) .. controls +(-.5,0) and +(-.5,-.5) .. (0);
\draw[->, shorten >= 1pt] (1) .. controls +(-.5,0) and +(-.5,.5) .. (1);
\draw[->, shorten >= 1pt] (2) .. controls +(.5,0) and +(.5,.5) .. (2);
\draw[->, shorten >= 1pt] (3) .. controls +(.5,0) and +(.5,-.5) .. (3);
\draw[->, shorten >= 1pt] (0) to [bend right] (3);
\draw[->, shorten >= 1pt] (3) to [bend right] (0);
\draw[->, shorten >= 1pt] (2) to [bend right] (3);
\draw[->, shorten >= 1pt] (3) to [bend right] (2);
\end{tikzpicture}
\end{matrix}$$
\smallskip
$$\text{(v) }\begin{matrix}
\begin{tikzpicture}
\node[bV, label=below:{\tiny$0$}] (0) at (0,0) {};
\node[bV, label=above:{\tiny$1$}] (1) at (0,1) {};
\node[bV, label=above:{\tiny$2$}] (2) at (1,1) {};
\node[bV, label=below:{\tiny$3$}] (3) at (1,0) {};
\draw[->, shorten >= 1pt] (0) .. controls +(-.5,0) and +(-.5,-.5) .. (0);
\draw[->, shorten >= 1pt] (1) .. controls +(-.5,0) and +(-.5,.5) .. (1);
\draw[->, shorten >= 1pt] (2) .. controls +(.5,0) and +(.5,.5) .. (2);
\draw[->, shorten >= 1pt] (3) .. controls +(.5,0) and +(.5,-.5) .. (3);
\draw[->, shorten >= 1pt] (0) to [bend right=15] (1);
\draw[->, shorten >= 1pt] (0) to [bend right = 10] (2);
\draw[->, shorten >= 1pt] (1) to [bend right=15] (0);
\draw[->, shorten >= 1pt] (2) to [bend right = 10] (0);
\draw[->, shorten >= 1pt] (1) to (2);
\end{tikzpicture}
\end{matrix}$$
How the properties of the directed graphs correspond to the symmetric, reflexive, and transitive properties of the corresponding relations:
\begin{enumerate}
\item Reflexivity corresponds to a loop at every vertex.\\
For example, every relation except for (ii) is reflexive; (ii) is not because it's missing a loop on vertex $0$.
\item Symmetry means that for every directed edge, there's the same edge in reverse.\\
For example, every relation except for (v) is symmetric; (v) is not because it has an arrow from 1 to 2, but not the reverse. Note that this is a conditional statement: if there aren't any edges between two different vertices (like in (i)), then there's nothing to check, and \textbf{symmetry holds by default}.
\item Transitivity means that if you can get from one vertex to another in exactly two steps, you can get there in exactly one.\\
For example, (ii) is not transitive since there are arrows
$\TikZ{
\node[bV, label=above:{\tiny$1$}] (a) at (0,1) {};
\node[bV, label=above:{\tiny$2$}] (b) at (1,1) {};
\draw[->, shorten >= 1pt] (a) to (b);
}$
and
$\TikZ{
\node[bV, label=above:{\tiny$2$}] (a) at (0,1) {};
\node[bV, label=above:{\tiny$3$}] (b) at (1,1) {};
\draw[->, shorten >= 1pt] (a) to (b);
}$, but not
$\TikZ{
\node[bV, label=above:{\tiny$1$}] (a) at (0,1) {};
\node[bV, label=above:{\tiny$3$}] (b) at (1,1) {};
\draw[->, shorten >= 1pt] (a) to (b);
}$.
Like symmetry, note that \textbf{transitivity holds by default}, and only fails if you can actually find an example of a two-step walk that doesn't have a shortcut. For example, the ``empty relation'' (nothing is related to anything else), whose digraph looks like
$$\begin{matrix}
\begin{tikzpicture}[scale=.75]
\node[bV, label=below:{\tiny$0$}] (0) at (0,0) {};
\node[bV, label=above:{\tiny$1$}] (1) at (0,1) {};
\node[bV, label=above:{\tiny$2$}] (2) at (1,1) {};
\node[bV, label=below:{\tiny$3$}] (3) at (1,0) {};
\end{tikzpicture}
\end{matrix},$$
is not reflexive (there are \emph{no loops}), but \emph{is} symmetric and transitive, because there's nothing to check.
\end{enumerate}
\end{ans}
\end{try}
\vfill
\begin{try}(Applied graphs)
Pick four of the Examples 2--12 in Section 10.1, and quickly summarize them. What is $V$? What is $E$? And what kind of graph results?
For example, in Example 1,
\begin{align*}
V &= \{ \text{ people } \}\\
E &= \{ a\!-\!b ~|~ a \neq b,\text{ and $a$ and $b$ are acquainted }\}
\end{align*}
The resulting graph is simple.
\end{try}
\vfill
\begin{try}
Let
$$G = \TikZ{
\node[bV, label=left:{$a$}] (a) at (0,1) {};
\node[bV, label=below:{$b$}] (b) at (1,2) {};
\node[bV, label=below:{$c$}] (c) at (2,1) {};
\node[bV, label=below:{$d$}] (d) at (3,1) {};
\draw (b) .. controls +(.5,.5) and +(-.5,.5) .. (b);
\draw (a) to (c) (b) to (c);
\draw (a) to [bend right] (c);
\draw (a) to (b);
\draw (c) to (d);
\draw (d) to [bend right] (c);
}
\qquad
H=
\TikZ{
\node[label=above:{$u$}, bV] (1) at (-.5,1) {};
\node[label=above:{$v$}, bV] (2) at (.5,1) {};
\node[label=right:{$w$}, bV] (3) at (1,0) {};
\node[label=below:{$x$}, bV] (4) at (0,-1) {};
\node[label=left:{$y$}, bV] (5) at (-1,0) {};
\draw (1) to (4) to (5) to (1) to (3) to (5) to (2) to (3) to (4);
}
$$
\begin{enumerate}[(a)]
\item In $G$, what is the neighborhood of $a$? What is the neighborhood of $b$?
\begin{ans}
We have
$$N(a) = \{b,c\} \quad \text{and} \quad N(b) = \{a,b,c\}.$$
\end{ans}
\item Calculate the degrees of each vertex in $G$ and $H$.
\begin{ans}
In $G$, we have
$$\begin{array}{|c||c|c|c|c|} \hline
\text{vertex} & a & b & c & d \\\hline
\deg(\text{vertex}) & 3 & 4 & 5 & 2\\\hline
\end{array}$$
In $H$, we have
$$\begin{array}{|c||c|c|c|c|c|} \hline
\text{vertex} & u & v & w & x & y \\\hline
\deg(\text{vertex}) & 3 & 2 & 4 & 3 & 4 \\\hline
\end{array}$$
\end{ans}
\item Verify the handshake theorem on $G$ and $H$.
\begin{ans}
For $G$, there are 7 edges and $\sum_{v \in V(G)} \deg(v) = 3 + 4 + 5 + 2 = 14 = 2 \cdot 7$.
For $H$, there are 8 edges and $\sum_{v \in V(G)} \deg(v) = 3 + 2 +4+3+4 = 16 = 2 \cdot 8$.
\end{ans}
\end{enumerate}
\end{try}
\vfill
\pagebreak
\begin{try}~
\begin{enumerate}[(a)]
\item Draw $C_6$, $W_6$ $K_6$, and $K_{5,3}$.
\begin{ans}
$$
C_6: \begin{matrix}
\begin{tikzpicture}
\foreach \x in {1,2,...,6}{\node[bV] (\x) at (\x*360/6:1) {};}
\draw (1) to (2) to (3) to (4) to (5) to (6) to (1);
\end{tikzpicture}
\end{matrix}
\qquad
W_6: \begin{matrix}
\begin{tikzpicture}
\node[bV] (0) at (0,0) {};
\foreach \x in {1,2,...,6}{\node[bV] (\x) at (\x*360/6:1) {};
\draw (0) to (\x);}
\draw (1) to (2) to (3) to (4) to (5) to (6) to (1);
\end{tikzpicture}
\end{matrix}\qquad
K_6: \begin{matrix}
\begin{tikzpicture}
\foreach \x in {1,2,...,6}{\node[bV] (\x) at (\x*360/6:1) {};}
\foreach \x in {2,...,6}{\foreach \y in {1,...,\x} {\draw (\x) to (\y);}}
\end{tikzpicture}\end{matrix}
\qquad
K_{5,3}: \begin{matrix}
\begin{tikzpicture}
\foreach \x in {1,2,...,5}{\node[bV] (t\x) at (\x-3,1) {};}
\foreach \x in {1,2,3}{\node[bV] (b\x) at (\x-2,0) {};}
\foreach \x in {1,2,...,5}{\foreach \y in {1,2,3}{\draw (t\x) to (b\y);}}
\end{tikzpicture}
\end{matrix}
$$
\end{ans}
\item Which of the following are bipartite? Justify your answer.
$$\begin{matrix}\begin{tikzpicture}[scale=.75]
\node[bV] (a) at (1,2) {};
\node[bV] (b) at (0,1) {};
\node[bV] (c) at (1,0) {};
\node[bV] (d) at (2,1) {};
\node[bV] (e) at (1,1) {};
\draw(a) to (e) (b) to (e) (c) to (e) (d) to (e);
\end{tikzpicture}\end{matrix}\qquad \qquad \begin{matrix}\begin{tikzpicture}[scale=.75]
\node[bV] (a) at (1,2) {};
\node[bV] (b) at (0,1) {};
\node[bV] (c) at (1,0) {};
\node[bV] (d) at (2,1) {};
\node[bV] (e) at (2,2) {};
\draw(a) to (b) (a) to (d) (a) to (e) (c) to (b) (c) to (e) (c) to (d);
\end{tikzpicture}\end{matrix}\qquad \qquad \begin{matrix}\begin{tikzpicture}[scale=.75]
\node[bV] (a) at (1,2) {};
\node[bV] (b) at (0,1) {};
\node[bV] (c) at (1,0) {};
\node[bV] (d) at (2,1) {};
\node[bV] (e) at (2,2) {};
\node[bV] (f) at (3,1) {};
\draw(a) to (b) (a) to (f) (b) to (e) (b) to (d) (c) to (f) (c) to (d) (d) to (e) (e) to (f);
\end{tikzpicture}\end{matrix}$$
\begin{ans}
$$\begin{matrix}\begin{tikzpicture}[scale=.75]
\node[C] (a) at (1,2) {};
\node[C] (b) at (0,1) {};
\node[C] (c) at (1,0) {};
\node[C] (d) at (2,1) {};
\node[C, black] (e) at (1,1) {};
\draw(a) to (e) (b) to (e) (c) to (e) (d) to (e);
\end{tikzpicture}\end{matrix} \qquad \text{Bipartite: put the white vertices in $V_1$ and the black in $V_2$.}$$
$$\begin{matrix}\begin{tikzpicture}[scale=.75]
\node[C, black] (a) at (1,2) {};
\node[C] (b) at (0,1) {};
\node[C, black] (c) at (1,0) {};
\node[C] (d) at (2,1) {};
\node[C] (e) at (2,2) {};
\draw(a) to (b) (a) to (d) (a) to (e) (c) to (b) (c) to (e) (c) to (d);
\end{tikzpicture}\end{matrix} \qquad \text{Bipartite: put the white vertices in $V_1$ and the black in $V_2$.}$$
$$\begin{matrix}\begin{tikzpicture}[scale=.75]
\node[C, black] (a) at (1,2) {};
\node[C] (b) at (0,1) {};
\node[C, black] (c) at (1,0) {};
\node[C] (d) at (2,1) {};
\node[C] (e) at (2,2) {};
\node[C, black] (f) at (3,1) {};
\draw(a) to (b) (a) to (f) (b) to (e) (b) to (d) (c) to (f) (c) to (d) (d) to (e) (e) to (f);
\end{tikzpicture}\end{matrix} \qquad \text{Not bipartite!}$$
Consider the three vertices colored white. For the sake of contradiction, assume that it is bipartite. Pick any one of them to be in $V_1$. That would force the other two to be in $V_2$. But they are adjacent, which is a contradiction.
\end{ans}
\pagebreak
\item Hypercubes are bipartite.
\medskip
\begin{enumerate}[(i)]
\item
Shade in the vertices of $Q_4$ that have an even number of 0's. Explain why the $4$-cube is bipartite.
\begin{ans}
$$\begin{tikzpicture}[xscale=3.1,yscale=1.9]
\tikzstyle{vertex}=[draw,circle,black,minimum size=20pt,inner sep=1pt, fill=white]
\tikzstyle{vertexA} = [vertex, fill=blue!30]
\tikzstyle{edge1} = [draw=white,double=black,line width=2pt, double distance=2pt]
\tikzstyle{edge2} = [draw=white,double=black,line width=2pt, double distance=2pt]
\tikzstyle{edge3} = [draw=white,double=black,line width=2pt, double distance=2pt]
\tikzstyle{edge4} = [draw=white,double=black,line width=2pt, double distance=2pt]
\tikzstyle{edge} = [draw,thick,-,black]
\node[vertexA] (1000) at (0,0) {$1000$};
\node[vertex] (1010) at (0,1) {$1010$};
\node[vertex] (1100) at (1,0) {$1100$};
\node[vertexA] (1110) at (1,1) {$1110$};
\node[vertex] (0000) at (0.23, 0.4) {$0000$};
\node[vertexA] (0010) at (0.23,1.4) {$0010$};
\node[vertexA] (0100) at (1.23,0.4) {$0100$};
\node[vertex] (0110) at (1.23,1.4) {$0110$};
\node[vertex] (1001) at (-1,-1) {$1001$};
\node[vertexA] (1011) at (-1,2) {$1011$};
\node[vertex] (0011) at (-0.66,2.7) {$0011$};
\node[vertexA] (0001) at (-0.66,-0.3) {$0001$};
\node[vertexA] (1101) at (2,-1) {$1101$};
\node[vertex] (0101) at (2.34,-0.3) {$0101$};
\node[vertex] (1111) at (2,2) {$1111$};
\node[vertexA] (0111) at (2.34,2.7) {$0111$};
\draw[edge4] (0000) -- (0001) (0100) -- (0101) (0110)--(0111) (0010)--(0011);
\draw[edge3] (0000)--(0010) (0100)--(0110);
\draw[edge1] (1000) -- (0000) (0100) -- (1100);
\draw[edge2] (1000) -- (1100) (0000) -- (0100);
\draw[edge1] (1010) -- (0010) (0110) -- (1110);
\draw[edge2] (1010) -- (1110) (0010) -- (0110);
\draw[edge3] (1000) -- (1010) (1100)--(1110);
\draw[edge3] (0001)--(0011) (0101)--(0111);
\draw[edge1] (1001) -- (0001) (0101) -- (1101);
\draw[edge2] (1001) -- (1101) (0001) -- (0101);
\draw[edge1] (1011) -- (0011) (0111) -- (1111);
\draw[edge2] (1011) -- (1111) (0011) -- (0111);
\draw[edge3] (1001) -- (1011) (1101)--(1111);
\draw[edge4] (1000) -- (1001) (1100) -- (1101) (1110)--(1111) (1010)--(1011);
\node[vertexA] at (0,0) {$1000$};
\node[vertex, fill=white] at (2,2) {$1111$};
\end{tikzpicture}$$
None of the shaded vertices are pairwise adjacent. None of the non-shaded vertices are pairwise adjacent. So put all the shaded vertices in $V_1$ and all the rest in $V_2$ to see that $Q_4$ is bipartite.
\end{ans}
\item Explain why $Q_n$ is bipartite in general.\\
{[Hint: Show that a vertex with an even (respectively, odd) number of 0's will never be adjacent to another vertex with an even (respectively, odd) number of 0's.]}
\begin{ans}
Any two vertices with an even number of 0's differ in at least two bits, and so are non-adjacent. Similarly, any two vertices with an odd number of 0's differ in at least two bits, and so are non-adjacent. So let $V_1 = \{$ vertices with an even number of 0's $\}$ and $V_2 = \{$ vertices with an odd number of 0's $\}$.
\end{ans}
\end{enumerate}
\end{enumerate}
\end{try}
\vfill
\pagebreak
\begin{try}~
\begin{enumerate}[(a)]
\item For each of the following pairs of graphs, first list their degree sequences. Then decide whether they are isomorphic or not. If not, say why. If they are, give a bijection on the vertices that preserves the edges, and draw the unlabeled graph that represents the corresponding isomorphism class of graphs.
\begin{center}
%\def\arraystretch{1.5}
\begin{tabular}{l@{\qquad\qquad}l}
(i)&(ii)\\
$\TikZ{[scale=.75]
\foreach \x in {1,2,...,5}{\node[label=left:{$u_{\x}$}, bV] (\x) at (0,\x*0.5) {};}
\draw (1) to (5);}\qquad\qquad \TikZ{[scale=.75]
\foreach \x/\y [count=\c from 1] in {(1,1)/1, (3,1)/2, (1,-1)/4, (3,-1)/5, (1,0)/3}{\node[label=above:{$v_{\c}$}, bV] (\c) at \x {};}
\draw (1) to (2) to (3) to (4) to (5);}$&$\TikZ{[scale=.75]
\foreach \x in {1,2,...,5}{\node[bV] (\x) at (\x*360/5+18:1) {}; \node[anchor=\x*360/5+180+18] at (\x) {$u_\x$};}
\draw (1) to (2) to (3) to (4) to (5) to (1);
}\quad \TikZ{[scale=.75]
\foreach \x in {1,2,...,5}{\node[bV] (\x) at (\x*360/5+18:1) {}; \node[anchor=\x*360/5+180+18] at (\x) {$v_\x$};}
\draw (1) to (3) to (5) to (2) to (4) to (1);
}$\\
{%(i)
\begin{tabular}{p{2.5in}}
\emph{Answer.}\\
Degree sequence: 2,2,2,1,1.\\
These are isomorphic.\\
One isomorphism is given by\\
$u_1 \mapsto v_1, ~ u_2 \mapsto v_2, ~ u_3 \mapsto v_3, $\\
$u_4 \mapsto v_3, ~ u_5 \mapsto v_5$ \\
\dotfill
\end{tabular}} &
{%(ii)
\begin{tabular}{p{2.5in}}
\emph{Answer.} \\
Degree sequence: 2,2,2,2,2.\\
These are isomorphic. \\
One isomorphism is given by\\
$u_1 \mapsto v_1, ~ u_2 \mapsto v_3, ~ u_3 \mapsto v_5$\\
$u_4 \mapsto v_2, ~ u_5 \mapsto v_4$.\\
\dotfill
\end{tabular}}
\end{tabular}
\\
\begin{tabular}{l@{\qquad\qquad}l}
(iii)&(iv)\\
$\TikZ{[scale=.75]
\node[label=above:{$u_1$}, bV] (1) at (-1,1) {};
\node[label=above:{$u_2$}, bV] (2) at (1,1) {};
\node[label=below:{$u_3$}, bV] (3) at (1,-1) {};
\node[label=below:{$u_4$}, bV] (4) at (-1,-1) {};
\node[label=above:{$u_5$}, bV] (5) at (0,0) {};
\draw (1) to (2) to (3) to (1) to (4) to (5) (4) to (3);
}\qquad
\TikZ{[scale=.75]
\node[label=above:{$v_1$}, bV] (1) at (0,1) {};
\node[label=above right:{$v_2$}, bV] (2) at (1,0) {};
\node[label=below:{$v_3$}, bV] (3) at (0.5,-1) {};
\node[label=below:{$v_4$}, bV] (4) at (-0.5,-1) {};
\node[label=above left:{$v_5$}, bV] (5) at (-1,0) {};
\draw (1) to (2) to (3) to (4) to (5) to (1) (5) to (2) to (4);
}
$&$\TikZ{[scale=.75]
\foreach \x in {1,2,...,7}{\node[bV] (\x) at (\x*360/7+90-360/7:1.2) {}; \node[anchor=\x*360/7-90-360/7] at (\x) {$u_\x$};}
\draw (1) to (2) to (3) to (4) to (5) to (6) to (7) to (1) (2) to (7) (3) to (5);
}\quad \TikZ{[scale=.75]
\foreach \x in {1,2,...,7}{\node[bV] (\x) at (\x*360/7+90-360/7:1.2) {}; \node[anchor=\x*360/7-90-360/7] at (\x) {$v_\x$};}
\draw (1) to (2) to (3) to (4) to (5) to (6) to (7) to (1) (2) to (6) (3) to (7);
}$\\
{%(iii)
\begin{tabular}{p{2.5in}}
\emph{Answer.}\\
Left degree sequence: 3,3,3,3,2.\\
Right degree sequence: 4,3,3,2,2.\\
These are not isomorphic\\
(they have different degree sequences).\\
\dotfill
\end{tabular}}&
{%(iv)
\begin{tabular}{p{2.5in}}
\emph{Answer.}\\
Degree sequence: 3,3,3,3,2,2,2.\\
These are not isomorphic.\\
In particular, the right graph has two adjacent vertices of degree 2 ($v_4$ and $v_5$), but the right graph does not.\\
\dotfill
\end{tabular}}
\end{tabular}
\\
\begin{tabular}{l@{\qquad\qquad}l}
(v)&(vi)\\
$\TikZ{[scale=.75]
\node[label=above:{$u_1$}, bV] (1) at (0,1) {};
\node[label=above:{$u_2$}, bV] (2) at (1,1) {};
\node[label=below:{$u_3$}, bV] (3) at (2,0) {};
\node[label=below:{$u_4$}, bV] (4) at (1,0) {};
\node[label=below:{$u_5$}, bV] (5) at (0,0) {};
\draw (1) to (2) to (4) to (5) to (1) to (4) (5) to (2) to (3) to (4);
}\qquad
\TikZ{[scale=.75]
\node[label=above:{$v_1$}, bV] (1) at (-.5,1) {};
\node[label=above:{$v_2$}, bV] (2) at (.5,1) {};
\node[label=right:{$v_3$}, bV] (3) at (1,0) {};
\node[label=below:{$v_4$}, bV] (4) at (0,-1) {};
\node[label=left:{$v_5$}, bV] (5) at (-1,0) {};
\draw (1) to (4) to (5) to (1) to (3) to (5) to (2) to (3) to (4);
}
$&
$\TikZ{[scale=.75]
\node[label=above:{$u_1$}, bV] (1) at (0,1) {};
\node[label=above:{$u_2$}, bV] (2) at (1,.5) {};
\node[label=below:{$u_3$}, bV] (3) at (1,-.5) {};
\node[label=below:{$u_4$}, bV] (4) at (0,-1) {};
\node[label=below:{$u_5$}, bV] (5) at (-1,-.5) {};
\node[label=above:{$u_6$}, bV] (6) at (-1,.5) {};
\draw (1) to (2) to (3) to (4) to (5) to (6) to (1) to (4) (6) to (2) (3) to (5);
}\qquad
\TikZ{[xscale=.75]
\node[label=above:{$v_5$}, bV] (1) at (0,.5) {};
\node[label=above:{$v_2$}, bV] (2) at (1,1) {};
\node[label=below:{$v_3$}, bV] (3) at (1,-1) {};
\node[label=below:{$v_6$}, bV] (4) at (0,-0.5) {};
\node[label=below:{$v_4$}, bV] (5) at (-1,-1) {};
\node[label=above:{$v_1$}, bV] (6) at (-1,1) {};
\draw (1) to (2) to (3) to (4) to (5) to (6) to (1) to (4) (6) to (2) (3) to (5);
}
$\\
{%(v)
\begin{tabular}{p{2.5in}}
\emph{Answer.}\\
Degree sequence: 4,4,3,3,2.\\
These are isomorphic. \\
One isomorphism is given by\\
$u_1 \mapsto v_1, ~ u_2 \mapsto v_3, ~ u_3 \mapsto v_2$\\
$u_4 \mapsto v_5, ~ u_5 \mapsto v_4$.\\
\dotfill
\end{tabular}} &
{%(vi)
\begin{tabular}{p{2.5in}}
\emph{Answer.}\\
Degree sequence: 3,3,3,3,3,3.\\
These are isomorphic. \\
One isomorphism is given by\\
$u_1 \mapsto v_5, ~ u_2 \mapsto v_2, ~ u_3 \mapsto v_3$\\
$u_4 \mapsto v_6, ~ u_5 \mapsto v_4, ~ u_6 \mapsto v_1$.\\
\dotfill
\end{tabular}}
\end{tabular}
\end{center}
\pagebreak
\item How many isomorphism classes are there of simple graphs with 4 vertices? Draw them.
\begin{ans} There are \fbox{11}.
\def\Four{\draw[black!20] (-.5, -.5) rectangle (1.5, 1.5);
\node[bV] (1) at (0,0) {}; \node[bV] (2) at (0,1) {}; \node[bV] (3) at (1,1) {}; \node[bV] (4) at (1,0) {};
}
$$
\begin{matrix}\begin{tikzpicture}[scale=.5]
\Four
\end{tikzpicture}\end{matrix} \qquad
\begin{matrix}\begin{tikzpicture}[scale=.5]
\Four
\draw (1) to (2);
\end{tikzpicture}\end{matrix} \qquad
\begin{matrix}\begin{tikzpicture}[scale=.5]
\Four
\draw (1) to (2) to (3);
\end{tikzpicture}\end{matrix} \qquad
\begin{matrix}\begin{tikzpicture}[scale=.5]
\Four
\draw (1) to (2) (3) to (4);
\end{tikzpicture}\end{matrix} \qquad
\begin{matrix}\begin{tikzpicture}[scale=.5]
\Four
\draw (1) to (2) to (3) to (4);
\end{tikzpicture}\end{matrix} \qquad
\begin{matrix}\begin{tikzpicture}[scale=.5]
\Four
\draw (1) to (2) to (3) (2) to (4);
\end{tikzpicture}\end{matrix}\qquad
\begin{matrix}\begin{tikzpicture}[scale=.5]
\Four
\draw (1) to (2) to (3) to (1);
\end{tikzpicture}\end{matrix} $$
$$
\begin{matrix}\begin{tikzpicture}[scale=.5]
\Four
\draw (1) to (2) to (3) (2) to (4) to (1);
\end{tikzpicture}\end{matrix}\qquad
\begin{matrix}\begin{tikzpicture}[scale=.5]
\Four
\draw (1) to (2) to (3) to (4) to (1);
\end{tikzpicture}\end{matrix} \qquad
\begin{matrix}\begin{tikzpicture}[scale=.5]
\Four
\draw (1) to (2) to (3) to (4) to (1) to (3);
\end{tikzpicture}\end{matrix} \qquad
\begin{matrix}\begin{tikzpicture}[scale=.5]
\Four
\draw (1) to (2) to (3) to (4) to (1) to (3) (2) to (4);
\end{tikzpicture}\end{matrix}
$$
{\small \textbf{Tip:} I've organized these by number of edges. It's much easier to make sure that I've gotten all the possibilities if I focus on one case at a time. For example, if I have 2 edges, then there are two choices: either they share a vertex or they don't. Since the vertices are unlabeled, it doesn't matter how I draw those two cases; there are only two isomorphism classes of graphs with 4 vertices and 2 edges.}
\end{ans}
\item
How many edges does a graph have if its degree sequence is $4, 3, 3, 2, 2$? Draw a graph with this degree sequence. Can you draw a simple graph with this sequence?
\begin{ans}
By the handshake lemma, we have
$$2|E| = 4 + 3+ 3+ 2+ 2 = 14.$$
So there are $14/2 = \fbox{$7$ edges}$. One isomorphism class of simple graphs that has that degree sequence is
$$\begin{matrix}\begin{tikzpicture}[scale=.75]
\node[bV] (a) at (.5,.5){}; \node[bV] (b) at (1,1){}; \node[bV] (c) at (1,0){};
\node[bV] (d) at (2,1){}; \node[bV] (e) at (2,0){};
\draw (a) to (b) to (d) to (e) to (b) to (c) to (a) (c) to (e);
\end{tikzpicture}\end{matrix}.$$
This is not the only isomorphism class of graphs with this degree sequence; for example,
$$\begin{matrix}\begin{tikzpicture}[scale=.75]
\foreach \x in {1,2,3,4,5}{\node[bV] (\x) at (\x, 0){};
\draw (\x) .. controls +(-.5,.5) and +(.5,.5) .. (\x);}
\draw (1) .. controls +(-.5,-.5) and +(.5,-.5) .. (1);
\draw (2) to (3);
\end{tikzpicture}\end{matrix}$$
also has this degree sequence (but is not simple).
\end{ans}
\item For which values of $n, m$ are these graphs regular? What is the degree?
\begin{enumerate}[(i)]
\item $K_n$ \Ans{Regular for all $n$, of degree $n-1$.}
\medskip
\item $C_n$ \Ans{Regular for all $n$, of degree $2$.}
\medskip
\item $W_n$ \Ans{Regular only for $n=3$, of degree $3$.}
\medskip
\item $Q_n$ \Ans{Regular for all $n$, of degree $n$.}
\medskip
\item $K_{m,n}$ \Ans{Regular for $n=m$, of degree $n$.}
\medskip
\end{enumerate}
\item How many vertices does a regular graph of degree four with 10 edges have?
\begin{ans}
By the handshake theorem,
$$2(10) = 2|E| = \sum_{v \in V} \deg(v) = \sum_{v \in V} 4 = 4|V|$$
so \fbox{$|V| = 5$}.
\end{ans}
\pagebreak
\item Show that isomorphism of simple graphs is an equivalence relation.
\begin{proof}We check the properties of equivalence one-by-one as follows.
\begin{enumerate}
\item Reflexive: the identity map on vertices is an isomorphism of a graph to itself.
\item Symmetric: If $f$ is an isomorphism $f: G_1 \to G_2$, then $f: V_1 \to V_2$ is bijective, and therefore has an inverse. Since $f$ preserves adjacency, so does $f^{-1}$. So $f^{-1}: G_2 \to G_1$ is an isomorphism.
\item Transitive: If $f: G_1 \to G_2$ and $g: G_2 \to G_3$ are isomorphisms, then $g \circ f: G_1 \to G_3$ is an isomorphism, since the composition of bijective and edge-preserving maps is bijective and edge-preserving.
\end{enumerate}
\end{proof}
\end{enumerate}
\end{try}
\end{document}