\documentclass[12pt,letterpaper]{article}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amscd}
\usepackage{enumerate}
\usepackage{fancyhdr}
\usepackage{mathrsfs}
\usepackage{bbm}
\usepackage{framed}
\usepackage{mdframed}
\usepackage{cancel}
\usepackage{mathtools}
\usepackage{verbatim}
\usepackage[letterpaper,voffset=-.5in,bmargin=3cm,footskip=1cm]{geometry}
\setlength{\parindent}{0.0in}
\setlength{\parskip}{0.1in}
\allowdisplaybreaks
\headheight 15pt
\headsep 10pt
\newcommand\N{\mathbb N}
\newcommand\Z{\mathbb Z}
\newcommand\R{\mathbb R}
\newcommand\Q{\mathbb Q}
\newcommand\lcm{\operatorname{lcm}}
\newcommand\setbuilder[2]{\ensuremath{\left\{#1\;\middle|\;#2\right\}}}
\newcommand\E{\operatorname{E}}
\newcommand\V{\operatorname{V}}
\newcommand\Pow{\ensuremath{\operatorname{\mathcal{P}}}}
\DeclarePairedDelimiter\ceil{\lceil}{\rceil}
\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}
\newcommand\hint[1]{\textbf{Hint}: #1}
\newcommand\note[1]{\textbf{Note}: #1}
\newcounter{enum22i}
\newenvironment{22enumerate}{\begin{enumerate}[a.]\itemsep0em\setcounter{enumi}{\value{enum22i}}}{\setcounter{enum22i}{\value{enumi}}\end{enumerate}}
\newenvironment{22itemize}{\begin{itemize}\itemsep0em}{\end{itemize}}
\fancypagestyle{firstpagestyle} {
\renewcommand{\headrulewidth}{0pt}
\lhead{\textbf{CSCI 0220}}
\chead{\textbf{Discrete Structures and Probability}}
\rhead{M. Littman}
}
\fancypagestyle{fancyplain} {
\renewcommand{\headrulewidth}{0pt}
\lhead{\textbf{CSCI 0220}}
\chead{Homework 10}
\rhead{\textit{Wednesday, May 6}}
}
\pagestyle{fancyplain}
\usepackage{graphicx}
\begin{document}
\thispagestyle{firstpagestyle}
\begin{center}
{\huge \textbf{Homework 10}}
{\large \textit{Due: Wednesday, May 6}}
\end{center}
All homeworks are due at 12:55 PM on Gradescope.
Please do not include any identifying information about yourself in the handin, including your Banner ID.
Be sure to fully explain your reasoning and show all work for full credit.
\subsection*{Problem 1}
{
\nopagebreak
{\setcounter{enum22i}{0}
Prove that by joining any number of connected graphs that have
connected Eulerian tours together the resulting graph will also have an
Eulerian tour. In this problem we define joining as merging any two
vertices together into a single new vertex, as depicted in the image
below:
\begin{center}
\includegraphics[scale=0.4]{/course/cs022/problems/graphs/old/graph_merge.png}
\end{center}
}
}
\subsection*{Problem 2}
{
\nopagebreak \newcommand\Cube{\textsf{Cube}}
{\setcounter{enum22i}{0}
Define a \emph{uniformly-random $k$-coloring}
$f : V(G) \to \{1,2,\dots,k\}$
as a coloring of $G$ (where $|V(G)|=n$) where each vertex $v \in V(G)$ is assigned one of the $k$ colors uniformly at random. This might
produce either a proper or improper coloring of $G$. A proper coloring is one where no two adjacent vertices are the same color,
while an improper coloring is one where there is some pair of adjacent vertices that are the same color. So far, we have only looked at
proper colorings.
\begin{22enumerate}
\item In terms of $n$ and $k$, how many (proper or improper) $k$-colorings of $G$ are there?
\item Let $K_n$ be the complete graph on $n$ vertices, with
$n \geq 3$.
\begin{enumerate}[i]
\item For what values of $k$ do
there exist proper $k$-colorings of $K_n$?
\item What is the probability that a uniformly-random $k$-coloring
$f$ is a proper $k$-coloring of $K_n$? You need only consider $k$'s such that a
proper $k$-coloring of $K_n$ is possible.
\end{enumerate}
\item
For $n \geq 1$, define the graph $\Cube_{n}$ as
follows. The vertex set is $\{0,1\}^{n}$ and,
for binary strings $u$ and $v$, $\{u, v\}$ is an edge of
$\Cube_n$ if and only if $u$ and $v$ differ
in exactly one position. For example,
$\Cube_{1}$ is a single edge,
$\Cube_{2}$ is a square,
$\Cube_{3}$ is a 3-dimensional cube.
(If it aids your understanding, try drawing these
small examples.)
What is the minimum number of colors $k$ that are needed to properly $k$-color $\Cube_{n}$?
\end{22enumerate}
}
}
\subsection*{Problem 3}
{
\nopagebreak
{\setcounter{enum22i}{0}
Recall that a Hamiltonian tour is a simple cycle in a graph that visits each vertex exactly once. How many distinct Hamiltonian tours are in the complete graph $K_{n}$?
We consider two Hamiltonian tours the same if they consist of the same set of edges. For example, $K_{3}$ has 1 distinct Hamiltonian tour.
}
}
\subsection*{Problem 4}
{
\nopagebreak
{\setcounter{enum22i}{0}
An \emph{orientation} of a graph $G$ is an assignment that
replaces each edge ${u, v} \in E(G)$ with one of the ordered pairs $(u, v)$
or $(v, u)$ but not both.
An acyclic orientation is an orientation with no directed cycles. That
is, we could not have the following edges: $(x_1, x_2), (x_2, x_3),...,
(x_{k_1}, x_k), (x_k, x_1)$.
Prove that, for $n \geq 1$, we can create an acyclic orientation of all
complete graphs $K_n$.
}
}
\subsection*{Problem 5}
{
\nopagebreak
{\setcounter{enum22i}{0}
A graph $G$ is said to be \emph{weighted} if there is a function $w: E(G) \rightarrow \R$. For any edge $e$, $w(e)$ is the weight
of the edge.
We talked about spanning trees in class. Often, for a weighted graph, we want to find a minimum spanning tree (MST).
$T$ is an MST of a graph $G$ if it is the spanning tree that minimizes $$\sum_{e \in E(T)} w(e)$$
Consider Kruskal's Algorithm, an algorithm for finding minimum spanning trees:
\begin{itemize}
\item Let $S = E(G), \:E(T) = \emptyset$
\item While $S$ is non-empty, remove a minimum weight edge from $S$ and add it to $E(T)$ if doing so will not create a cycle in $T$.
\end{itemize}
Prove that, if $G$ is connected, $T$ as constructed by Kruskal's algorithm is a minimum spanning tree. To do so, you must first prove $T$ is a
spanning tree, then that it is minimal.
}
}
\subsection*{Problem 6}
{
\nopagebreak
{\setcounter{enum22i}{0}
This question is \textbf{optional}. However, we encourage you to complete it,
or at least do some reflection on what you've learned this semester.
You've spent a semester now reading and writing proofs.
We've told you what we think makes a good proof, but we now want
you to think about what you believe. Revisit a proof you wrote earlier
in the semester, and tell us how you would change it now that you have
more experience with proofs and have developed your own proof virtues.
You don't need to rewrite the proof, but you should include the original.
}
}
\end{document}