\documentclass[12pt]{amsart} 


% Call packages that allow you to invoke certain mathematical symbols.
\usepackage{amssymb,amsmath,amsthm}
\usepackage[margin=0.9in]{geometry}
\usepackage{cases}
\usepackage{url}
\usepackage{hyperref}
\usepackage{tikz}

% Set the title, author, and date information.


% Formally begin the document and make the title.

\begin{document}
\noindent \textbf{Math 451 - Spring 2018 \\
 Homework 4} \\
Due March 1st, 2018 \vspace{-4mm}\\

\small \textit{You know, a tree is a tree, how many more do you need to look at?}\\\vspace{1mm} \hfill---
Ronald Reagan

\vspace{-5mm}
\normalsize
\noindent \hrulefill
\vspace{3mm}\\
\noindent \textbf{Turn in:} 

\vspace{5mm}

\vspace{5mm}
\begin{enumerate}

\item Find all regular trees.  Explain your answer.

\item Let $G$ be a connected graph.  We say a vertex $x$ is a \textbf{cut-vertex} in $G$ provided that $G-x$ is disconnected.  What are all the cut-vertices of a nontrivial tree?  Prove your answer.

\item Let $G$ be a connected graph.  Assume $G$ contains two vertices $u, v$ such that $G-u$ and $G-v$ are trees.  
\begin{enumerate}
	\item Prove that $\deg u = \deg v$.
	\item Classify all connected graphs $G$ with order $n\geq 3$ with the property that deleting any of its vertices gives a tree. (Hint: In this case $G$ must be regular.  What is this common degree?)
\end{enumerate}


\item Find all trees $T$ such that $\overline{T}$ is also a tree.  

\item Exercise 4.27

\item Exercise 4.39



\end{enumerate}


\end{document}
