\Question{Leaves in a Tree}
A {\em leaf} in a tree is a vertex with degree $1$.
\begin{Parts}
\Part
Prove that every tree on $n \ge 2$ vertices has at least two leaves.
\Part What is the maximum number of leaves in a tree with $n \ge 3$ vertices?
\end{Parts}
\Question{Build-Up Error?}
What is wrong with the following "proof"?
{\bf False Claim:}~If every vertex in an undirected graph has degree at least 1, then the graph is connected.
{\em Proof:}~We use induction on the number of vertices $n \ge 1$.
{\em Base case:} There is only one graph with a single vertex and it has degree 0. Therefore, the base case is vacuously true, since the if-part is false.
{\em Inductive hypothesis:} Assume the claim is true for some $n \ge 1$.
{\em Inductive step:} We prove the claim is also true for $n+1$. Consider an undirected graph on $n$ vertices in which every vertex has degree at least 1. By the inductive hypothesis, this graph is connected. Now add one more vertex $x$ to obtain a graph on $(n + 1)$ vertices, as shown below.
\vspace{-8pt}
\begin{center}
\includegraphics[width=0.2\textwidth]{src/problems/graphtheory/resources/falseind.pdf}
\end{center}
\vspace{-8pt}
All that remains is to check that there is a path from $x$ to every other vertex $z$. Since $x$
has degree at least 1, there is an edge from $x$ to some other vertex; call it $y$. Thus, we
can obtain a path from $x$ to $z$ by adjoining the edge $\{x,y\}$ to the path from $y$ to $z$. This
proves the claim for $n+1$.
\Question{Graph Coloring}
Prove that a graph with maximum degree at most $k$ is $(k+1)$-colorable.
\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{Proofs in Graphs}
Please prove or disprove the following claims.
\begin{Parts}
\Part Suppose we have $n$ websites ($n \geq 2$) such that for every pair of websites $A$ and $B$,
either $A$ has a link to $B$ or $B$ has a link to $A$. Prove or disprove that
there exists a website that is reachable from every other website by clicking at
most 2 links. (\textit{Hint: Induction})
\Part
In the lecture, we have shown that a connected undirected graph has an Eulerian tour if and only if every vertex has even degree.
Prove or disprove that if a connected graph $G$ on $n$ vertices has exactly $2d$ vertices of
odd degree, then there are $d$ walks ($d>0$) that \emph{together} cover all the edges of
$G$ (i.e., each edge of $G$ occurs in exactly one of the $d$ walks; and each of
the walks should not contain any particular edge more than once).
\end{Parts}
\Question {Triangulated Planar Graph}
In this problem you will prove that every triangulated planar graph (every face has 3 sides; that is, every face has three edges bordering it, including the unbounded face)
contains either (1) a vertex of degree 1, 2, 3, 4, (2) two degree 5 vertices
which are connected together, or (3) a degree 5 and a degree 6 vertices which are
connected together. Justify your answers.
\begin{Parts}
\Part Place a charge on each vertex $v$ of value $6-\operatorname{degree}(v)$. What is
the sum of the charges on all the vertices?
(\textit{Hint}: Use Euler's formula and the fact that the planar graph is
triangulated.)
\Part What is the charge of a degree $5$ vertex and of a degree $6$ vertex?
\Part Move $1/5$ charge from each degree $5$ vertex to each of its negatively charged
neighbors. Conclude the proof in the case where there is a degree $5$
vertex with positive remaining charge.
\Part If no degree $5$ vertices have positive charge after discharging,
does there exist a vertex with positive charge after discharging?
If there is such a vertex, what are possible degrees of that vertex?
\Part
Suppose there exists a degree $7$ vertex with positive charge after the discharging process of degree 5 vertices.
How many neighbors of degree 5 might it have?
\Part Continuing the last question. Since the graph is triangulated,
are two of these degree $5$ vertices adjacent?
\Part Finish the proof from the facts you obtained from the previous
questions.
\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 ``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. 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 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 this 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$ bit-fixing steps.
On the graph below, trace all the paths from source
$x = (110)$ to destination $y = (011)$, so that these paths are the shortest bit-fixing paths that you obtained from part (c). For this, you need to label the vertices in the graph explicitly. This example should convince you that the butterfly network is indeed equivalent to the hypercube routing.
\begin{center}
\includegraphics{src/problems/graphtheory/resources/butterfly.pdf}
\end{center}
\end{Parts}