\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{multicol}
\usepackage{latexsym}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\def\zero{\multicolumn{1}{>{\columncolor{white}}c}{0}}
\def\colCell#1#2{\multicolumn{1}{>{\columncolor{#1}}c}{#2}}

\input{preamble.tex}

\begin{document}
\homework{8: Trees}{Due Friday, Week 5}

Do \textbf{one} of the four problems listed here!  Have fun, prove all of your claims, and let me know if you have any questions!

\begin{enumerate}
\item Prove the tree theorem we mentioned in class:
\begin{thm}
For a graph $G$ on $n$ vertices, the following statements are equivalent\footnote{A series of true-false statements are called \textbf{equivalent} if one of them being true means that all of the others are true.  For example, the two statements ``$n$ is odd'' and ``$n+1$ is even'' are equivalent: whenever one of them is true, the other must be true as well.}:
\begin{itemize}
\item $G$ is a tree.
\item $G$ is connected and has $n-1$ edges.
\item $G$  has $n-1$ edges and no cycles.
\item $G$ is a connected graph, and every edge of $G$ is a cut-edge\footnote{An edge $e \in G$ is called a \textbf{cut-edge} if deleting $e$ from $G$ increases the number of connected components of $G$.}.
\end{itemize}
\end{thm}
\item For any graph $G$, let $\delta(G)$ denote the minimum degree over all of the vertices in $G$.  Suppose that $T$ is a tree on $n$ vertices, and that $G$ is a graph with $\delta(G) \geq n$.  Then there is a subgraph of $G$ isomorphic to $T$.
\item Suppose that $T$ is a tree.  As noted in class, $T$ is bipartite. Let $V_1, V_2$ denote a bipartition of $T$'s edges; i.e.\ $V_1 \cup V_2 = V(T)$, and every edge of $T$ has exactly one edge in $V_1$ and another in $V_2$.

Suppose that $|V_1| \geq |V_2|$.  Prove that $T$ has at least one leaf in the larger of the two sets $V_1, V_2$.
\item Prove the claim we made in class on Monday: that the Pr\"ufer algorithm's inverse is in fact an inverse!  In other words, prove that taking any tree $T$, running the Pr\"ufer algorithm on it to get a sequence, and running the claimed inverse map to get a graph $G$ will always return the same tree $T$.
\end{enumerate}



\end{document}