\Question{Short Answer: Graphs}
\begin{Parts}
\Part
(4 Points) Bob removed a degree $3$ node in an $n$-vertex tree, how many connected
components are in the resulting graph? (An expression that may
contain $n$.)
\Part
(4 Points) Given an $n$-vertex tree, Bob added 10 edges to it, then Alice removed
5 edges and the resulting graph has 3 connected components.
How many edges must be removed to remove all cycles
in the resulting graph? (An expression that may contain $n$.)
%\Part
%Give a gray code for 3-bit strings. (Recall that a gray code is a
%sequence of bitstrings where adjacent elements differ by one. For
%example, the gray code of 2-bit strings is $00,01,11,10$. Note the
%last string is considered adjacent to the first and $10$ differs in
%one bit from $00$. Answer should be sequence of three-bit strings: 8
%in all.)
\Part
(4 Points) True or False: For all $n \geq 3$, the complete graph on $n$ vertices, $K_n$ has more
edges than the $n$-dimensional hypercube. Justify your answer.
\Part
(4 Points) A complete graph with $n$ vertices where $n$ is an odd prime can have all its edges
covered with $x$ edge-disjoint Hamiltonian cycles (a Hamiltonian cycle is a cycle where
each vertex appears exactly once). What is the number, $x$, of
such cycles required to cover the a complete graph? (Answer should be an expression that depends on $n$.)
\Part
(4 Points) Give a set of edge-disjoint Hamiltonian cycles that covers the edges of $K_5$, the complete
graph on $5$ vertices.
(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)$.)
\end{Parts}
\Question{Bipartite Graph}
A bipartite graph consists of $2$ disjoint sets of vertices (say $L$ and $R$), such that no $2$ vertices in the same set have an edge between them.
% For example, if we had a bipartite graph that consists of vertices $\{1, 2, 3, 4\}$, such that set A = $\{1, 2\}$ and B = $\{3, 4\}$, there cannot exist an edge between $1$ and $2$, and similarly there cannot exist an edge between $3$ and $4$. \\
For example, here is a bipartite graph (with $L=\{\hbox{{\color{green}{green}} vertices}\}$ and $R =\{\hbox{{\color{red}{red}} vertices}\}$), and a non-bipartite graph.
\begin{figure}[hpb]
\begin{minipage}{0.49\textwidth}
\centering
\includegraphics[scale=.3]{src/problems/graphtheory/resources/k_3_3.png}
\end{minipage}
\begin{minipage}{0.49\textwidth}
\centering
\includegraphics[scale=.3]{src/problems/graphtheory/resources/non-bipartite.png}
\end{minipage}
\caption{A bipartite graph (left) and a non-bipartite graph (right).}
\label{fig:bipartite}
\end{figure}
In discussion 02A, we've proved that a graph has no tours of odd length if it is a bipartite. Now, please prove the reversed direction: If undirected G has no tours of odd length, it is a bipartite. \\
\nosolspace{1in}
\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{Modular Exponentiation}
Compute the following:
\begin{Parts}
\Part $13^{2018} \pmod {12}$
\nosolspace{1.5cm}
\Part $8^{11111} \pmod 9$
\nosolspace{1.5cm}
\Part $7^{256} \pmod {11}$
\nosolspace{1.5cm}
\Part $3^{160} \pmod {23}$
\nosolspace{1.5cm}
\end{Parts}
\Question{Euler's Totient Function}
Euler's totient function is defined as follows:
$$\phi(n) = | \{i: 1 \leq i \leq n, \texttt{gcd}(n,i) = 1\} |$$
In other words, $\phi(n)$ is the total number of positive integers less than or equal to $n$ which are relatively prime to it.
Here is a property of Euler's totient function that you can use without proof:
For $m,n$ such that \texttt{gcd}($m,n$) = 1, $\phi(mn) = \phi(m) \cdot \phi(n)$.
\begin{Parts}
\Part
Let $p$ be a prime number.
What is $\phi(p)$?
\Part
Let $p$ be a prime number and $k$ be some positive integer.
What is $\phi(p^k)$?
\Part
Let $p$ be a prime number and $a$ be a positive integer smaller than $p$.
What is $a^{\phi(p)} \pmod{p}$?\\\emph{(Hint: use Fermat's Little Theorem.)}
\Part
Let $b$ be a positive integer whose prime factors are $p_1,p_2,\hdots, p_k$.
We can write $b = p_1^{\alpha_1}\cdot p_2^{\alpha_2} \hdots p_k^{\alpha_k}$.
Show that for any $a$ relatively prime to $b$, the following holds:
$$\forall i \in \{1,2,\hdots,k\}, \hspace{0.2cm} a^{\phi(b)} \equiv 1 \pmod{p_i}$$
\end{Parts}
\Question{Just a Little Proof}
Suppose that $p$ and $q$ are distinct odd primes and $a$ is an integer such that $\text{gcd}(a,pq)=1$. Prove that $a^{(p-1)(q-1)+1}\equiv a \pmod{pq}$.
\nosolspace{5cm}