\Question{Leaves in a Tree}
A {\em leaf} in a tree is a vertex with degree $1$.
\begin{Parts}
\Part
Consider a tree with $n \ge 3$ vertices. What is the largest possible number of leaves the tree could have? Prove that this maximum $m$ is possible to achieve, and further that there cannot exist a tree with more than $m$ leaves.
\nosolspace{0.5in}
\Part
Prove that every tree on $n \ge 2$ vertices must have at least two leaves.
\nosolspace{0.5in}
%\Part
%Let $k$ be the maximum degree of a tree (The maximum degree of a graph is defined as the largest degree of any vertex in that graph). Prove that the tree contains at least $k$ leaves.
%\nosolspace{0.5in}
\end{Parts}
\Question{Coloring Trees}
\begin{Parts}
\Part
What is the minimum number of colors needed to color a tree? Prove your claim.
\Part
Prove that all trees are \emph{bipartite}: the vertices can be partitioned into two groups so that every edge goes between the two groups.
[\textit{Hint:} How does your answer to part (a) relate to this?]
\end{Parts}
\Question{Edge-Disjoint Paths in a Hypercube}
Prove that between any two distinct vertices $x,y$ in the $n$-dimensional hypercube graph, there are at least $n$ edge-disjoint paths from $x$ to $y$ (i.e., no two paths share an edge, though they may share vertices).
\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 adjacent, or (3) a degree 5 and a degree 6 vertices which are
adjacent. 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 Suppose now that we shift $1/5$ of the charge of a degree $5$ vertex to each of its neighbors that has a negative charge. (We refer to this as ``discharging'' the degree $5$ vertex.) Conclude the proof under the assumption that, after discharging all degree $5$ vertices, there is a degree $5$ vertex with positive remaining charge.
%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 the degree $5$ vertices,
does there exist any vertex with positive charge after discharging?
If there is such a vertex, what are the possible degrees of that vertex?
\Part
Suppose there exists a degree $7$ vertex with positive charge after discharging the degree $5$ vertices.
How many neighbors of degree $5$ might it have?
\Part Continuing from Part (e). 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
parts.
\end{Parts}
\Question{Euclid's Algorithm}
\begin{Parts}
\Part Use Euclid's algorithm from lecture to compute the greatest common divisor of 527 and 323. List the values of $x$ and $y$ of all recursive calls.
\Part Use extended Euclid's algorithm from lecture to compute the multiplicative inverse of 5 mod 27. List the values of $x$ and $y$ and the returned values of all recursive calls.
\Part Find $x \pmod{27}$ if $5x + 2 6 \equiv 3 \pmod{27}$. You can use the result computed in (b).
\Part Assume $a$, $b$, and $c$ are integers and $c>0$. Prove or disprove: If $a$ has no multiplicative inverse mod $c$, then $ax \equiv b \pmod{c}$ has no solution.
\end{Parts}
\Question{Fibonacci GCD}
The Fibonacci sequence is given by $F_n = F_{n-1} + F_{n-2}$, where $F_0 = 0$ and $F_1 = 1$. Prove that, for all $n \geq 0$, $\gcd(F_n,F_{n-1}) = 1$,
\nosolspace{1.5in}