\bigskip
\textit{\textbf{Note:} This homework consists of two parts. The first part (questions 1-6) will be graded and will determine your score for this homework. The second part (questions 7-9) will be graded if you submit them, but will not affect your homework score in any way. You are strongly advised to attempt all the questions in the first part. You should attempt the problems in the second part only if you are interested and have time to spare.}
\rule{6in}{2px}
\section*{Part 1: Required Problems}
\bigskip
\Question{Degree Sequences}
The \emph{degree sequence} of a graph is the sequence of the degrees of the vertices, arranged in descending order, with repetitions as needed. For example, the degree sequence of the following graph is $(3,2,2,2,1)$.
\begin{figure}[H]
\centering
\includegraphics[width=5cm]{src/problems/graphtheory/resources/deg-seq-ex.png}
\end{figure}
For each of the parts below, determine if there exists a simple undirected graph $G$ (i.e. a graph without self-loops and multiple-edges) having the given degree sequence. Justify your claim.
\begin{Parts}
\Part
$(3,3,2,2)$
\Part
$(3,2,2,2,2,1,1)$
\Part
$(6,2,2,2)$
\Part
$(4,4,3,2,1)$
\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
The \emph{double} of a graph $G$ consists of two copies of $G$ with edges joining
the corresponding ``mirror'' vertices. More precisely, if $G = (V,E)$, where $V = \{v_1,v_2,\dots,v_n\}$ is the set of vertices and $E$ the set of edges, then the double of the graph $G$ is given by $G_1 = (V_1, E_1)$, where
\[
V_1 = \{v_1,v_2,\dots,v_n, v_1', v_2', \dots, v_n'\},
\]
and
\[
E_1 = E \cup \{(v_i',v_j') | (v_i,v_j) \in E\} \cup \{(v_i,v_i'), \forall i \}.
\]
Here is an example,\\
\begin{figure}[H]
\centering
\includegraphics[width=10cm]{src/problems/graphtheory/resources/bipartite-ii-G-ex.png}
\end{figure}
Draw the double of the following graph:\\
\begin{figure}[H]
\centering
\includegraphics[width=6cm]{src/problems/graphtheory/resources/bipartite-ii-G-p.png}
\end{figure}
\Part
Now suppose that $G_1$ is a bipartite
graph, $G_2$ is the double of $G_1$, $G_3$ is the double of $G_2$, and so on. (Each $G_{i+1}$ has twice as many vertices as $G_i$).
Show that $\forall n \geq 1$, $G_n$ is bipartite.
\textit{Hint: Use induction on $n$.}
% \Part
% Prove that a graph is bipartite if and only if it can be $2$-colored. (A graph can be $2$-colored if every vertex can be assigned one of two colors such that no two adjacent vertices have the same color).
\end{Parts}
\Question{Planarity and Graph Complements}
Let $G = (V, E)$ be an undirected graph. We define the complement of $G$ as $\overline{G} = (V, \overline{E})$ where $\overline{E} = \{(i,j) | i,j \in V, i \neq j\} - E$; that is, $\overline{G}$ has the same set of vertices as $G$, but an edge $e$ exists is $\overline{G}$ if and only if it does not exist in $G$.
\begin{Parts}
\Part Suppose $G$ has $v$ vertices and $e$ edges. How many edges does $\overline{G}$ have?
\nosolspace{0.5in}
\Part Prove that for any graph with at least 13 vertices, $G$ being planar implies that $\overline{G}$ is non-planar.
\nosolspace{1.5in}
\Part Now consider the converse of the previous part, i.e., for any graph $G$ with at least 13 vertices, if $\overline{G}$ is non-planar, then $G$ is planar. Construct a counterexample to show that the converse does not hold.
\textit{Hint: Recall that if a graph contains a copy of $K_5$, then it is non-planar. Can this fact be used to construct a counterexample?}
\nosolspace{2in}
\end{Parts}
\Question{Eulerian Tour and Eulerian Walk}
% mathematica code:
% Graph[EdgeAdd[
% VertexContract[
% GraphDisjointUnion[CompleteGraph[4], CompleteGraph[4]], {1,
% 5}], {2 <-> 6, 4 <-> 8}], VertexSize -> Small,
% VertexLabels -> Automatic]
\begin{figure}[H]
\centering
\includegraphics[width=8cm]{src/problems/graphtheory/resources/Eulerian-labelled.png}
\end{figure}
\begin{Parts}
\Part Is there an Eulerian tour in the graph above? If no, give justification. If yes, provide a counter-example.
\Part Is there an Eulerian walk in the graph above? If no, give justification. If yes, provide a counter-example.
\Part What is the condition that there is an Eulerian walk in an undirected graph? Briefly justify your answer.
\end{Parts}
\nosolspace{1cm}
\Question{Trees and Components}
\begin{Parts}
\Part
%(4 Points)
Bob removed a degree $3$ node from an $n$-vertex tree.
How many connected
components are there in the resulting graph? Please provide an explanation.
\Part
%(4 Points)
Given an $n$-vertex tree, Bob added 10 edges to it and then Alice removed
5 edges.
If the resulting graph has 3 connected components,
how many edges must be removed in order to remove all cycles
from the resulting graph? Please provide an explanation.
\end{Parts}
\Question{Hamiltonian decompositions of a complete graph}
\begin{Parts}
\Part
% (4 Points)
(Walecki's Theorem)
Let $K_n$ be the complete graph on $n$ vertices.
\begin{enumerate}[(i)]
\item If $n$ is an odd positive integer, then the edge set of $K_n$ can be partitioned into $x$ edge-disjoint Hamiltonian cycles (a Hamiltonian cycle is a cycle where
each vertex appears exactly once).
\item If $n$ is an even positive integer, then the edge set of $K_n$ can be partitioned into $y$ edge-disjoint Hamiltonian cycles and one perfect matching (a perfect matching is a set of edges such that every vertex is a part of exactly one edge in the set).
\end{enumerate}
Assume the above theorem is true. What are $x$ and $y$?
\Part
%(4 Points)
Give a partition of the edges of $K_5$ with vertices $\{1,2,3,4,5\}$ into edge-disjoint Hamiltonian cycles.
%(Each path should be a sequence (or list) of edges in $K_5$, where an edge is written as a pair of vertices from the set $\{0, 1, 2, 3, 4\}$ - e.g: $\{0, 1\}, \{1, 2\}$.)
\Part
%(4 Points)
Give a partition of the edges of $K_6$ with vertices $\{1,2,3,4,5,6\}$ into edge-disjoint Hamiltonian cycles and a perfect matching.
\end{Parts}
\bigskip
\textit{\textbf{Note:} This concludes the first part of the homework. The problems below are optional, will not affect your score, and should be attempted only if you have time to spare.}
\rule{6in}{2px}
\bigskip
\section*{Part 2: Optional Problems}
\bigskip
\Question{Planarity}
Consider graphs with the property $T$:
For every three distinct vertices $v_1, v_2, v_3$ of graph $G$, there are at
least two edges among them.
Prove that if $G$ is a graph on $\ge 7$ vertices, and $G$ has property $T$, then
$G$ is nonplanar.
\nosolspace{1.5in}
\Question{Connectivity}
Consider the following claims regarding connectivity:
\begin{Parts}
\Part Prove: If $G$ is a graph with $n$ vertices such that for any two non-adjacent vertices $u$ and $v$, it holds that $\deg u + \deg v \ge n - 1$, then $G$ is connected.
[\textit{Hint:} Show something more specific: for any two non-adjacent vertices $u$ and $v$, there must be a vertex $w$ such that $u$ and $v$ are both adjacent to $w$.]
\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 Prove: For a graph $G$ with $n$ vertices, if the degree of each vertex is at least $n/2$, then $G$ is connected.
\Part Prove: If there are exactly two vertices with odd degrees in a graph, then they must be in the same connected component (meaning, there is a path connecting these two vertices).
[\textit{Hint:} Proof by contradiction.]
\end{Parts}
\Question{Hypercube Routing}
Recall that an $n$-dimensional hypercube contains $2^n$ vertices, each labeled
with a distinct $n$ bit string, and two vertices are adjacent if and only if
their bit strings differ in exactly one position.
\begin{Parts}
\Part The hypercube is a popular architecture for parallel computation. Let
each vertex of the hypercube represent a processor and each edge represent a
communication link. Suppose we want to send a packet from vertex $x$ to vertex
$y$. Consider the following ``left-to-right bit-fixing'' algorithm:
\begin{quote} In each step, the current processor compares its address to the
destination address of the packet. Let's say that the two addresses match up
to the first $k$ positions (reading the bits from left to right). The processor then forwards the packet and the
destination address on to its neighboring processor whose address matches
the destination address in at least the first $k+1$ positions. This process
continues until the packet arrives at its destination.
\end{quote}
Consider the following example where $n=4$: Suppose that the source vertex is
$(1001)$ and the destination vertex is $(0100)$. Give the sequence of
processors that the packet is forwarded to using the left-to-right bit-fixing algorithm.
\Part The \emph{Hamming distance} $H(x, y)$ between two $n$-bit strings $x$ and
$y$ is the number of bit positions where they differ. Show that for an
arbitrary source vertex and arbitrary destination vertex, the number of edges
that the packet must traverse under the left-to-right bit-fixing algorithm is the Hamming distance
between the $n$-bit strings labeling source and destination vertices.
%\Part Consider the following example where $n=3$: Suppose that $x$ is $(110)$
%and $y$ is $(011)$. What is the length of the shortest path between $x$ and
%$y$? What is the set of all vertices and the set of all edges that lie on
%shortest paths between $x$ and $y$? Do you see a pattern? You do not need to
%prove your answer here -- you'll provide a general proof in part (d).
%\Part Answer the last question for an arbitrary pair of vertices $x$ and $y$ in
%the hypercube. Can you describe the set of vertices and the set of edges that
%lie on shortest paths between $x$ and $y$? Prove that your answers are
%correct. ({\em Hint:} Consider the bits where $x$ and $y$ differ.)
\Part There is another famous graph, called the butterfly network, which is
another popular architecture for parallel computation. You will see this
network in CS 170 in the context of circuits for implementing the FFT (fast
fourier transform). Here is a diagram of the butterfly network for $n =
3$. In general, the butterfly network has $(n+1) \cdot 2^n$ vertices organized into
$n+1$ columns of $2^n$ vertices each. The vertices in each column are labeled with the bit strings in $\{0,1\}^n$, and
all vertices in the same row have the same label. The source is on the leftmost column and the destination is on the right.
It turns out the $n$-butterfly network is equivalent to the
$n$-dimensional hypercube unrolled into $n$ left-to-right bit-fixing steps.
On the graph below,
label the vertices in the graph explicitly
and trace the path from source $x = (110)$ to destination $y = (011)$.
Convince yourself that the left to right paths in the butterfly network are indeed equivalent to the hypercube routing obtained by the left-to-right bit-fixing algorithm.
\begin{center}
\includegraphics{src/problems/graphtheory/resources/butterfly.pdf}
\end{center}
\end{Parts}