\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$.
\nosolspace{1cm}
\Question{Proofs in Graphs}
Please prove or disprove the following claims.
\begin{Parts}
\Part In Old California, all roads were one way streets. Suppose Old California had
$n$ cities ($n \geq 2$) such that for every pair of cities $X$ and $Y$,
either $X$ had a road to $Y$ or $Y$ had a road to $X$. Prove or disprove that
there existed a city which was reachable from every other city by traveling through at
most 2 roads.
[\textit{Hint:} Induction]
\Part
In lecture, we have shown that a connected undirected graph has an Eulerian tour if and only if every vertex has even degree.
Consider a connected graph $G$ with $n$ vertices which has exactly $2m$ vertices of
odd degree, where $m > 0$. Prove or disprove that there are $m$ walks that \emph{together}
cover all the edges of $G$ (i.e., each edge of $G$ occurs in exactly one of the $m$ walks,
and each of the walks should not contain any particular edge more than once).
\end{Parts}
\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 connected to each other (meaning, there is a path connecting these two vertices).
[\textit{Hint:} Proof by contradiction.]
\end{Parts}
\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.
\Part
Prove that every tree on $n \ge 2$ vertices must have at least two leaves.
\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 bipartite.
[\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).