


\documentclass[11pt]{article}
\usepackage{graphicx}
\usepackage{fullpage}
\usepackage{enumerate}
\usepackage{amsmath,amsthm,amssymb}
\usepackage{hyperref}
\usepackage{multicol}
\usepackage{soul}
\usepackage{graphicx}                                          
\usepackage{float}                                                

\vfuzz2pt 
\hfuzz2pt 

\newtheorem{thm}{Theorem}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}
\theoremstyle{remark}
\newtheorem{remark}[thm]{Remark}
\newtheorem*{fact*}{Fact}
\numberwithin{equation}{section}

\newtheoremstyle{probstyle}  
{3ex}                        
{0pt}                        
{\normalfont}                
{-3ex}                       
{\normalfont\bfseries}       
{.}                          
{.5em}                       
{}                           
\theoremstyle{probstyle}
\newtheorem{problem}{Problem}

\newcommand{\abs}[1]{\left\vert#1\right\vert}
\newcommand{\set}[1]{\left\{#1\right\}}
\newcommand{\R}{\mathbb R}
\newcommand{\eps}{\varepsilon}
\setlength\parindent{0pt}
\setul{.25ex}{}

\begin{document}
	\title{Math 154 Homework \#3\vspace{-3ex}}
\date{Spring 2023}
	\maketitle
	\begin{center}
		Due date: \textbf{11:59pm} Pacific Time on \textbf{Wed, Apr 26} (via \href{https://www.gradescope.com/}{Gradescope})
	\end{center} 
	\vskip 3ex
	\thispagestyle{empty}
	
	\noindent\emph{On the first page of your work, please write a list of everyone with whom you collaborated on this assignment, as well as any outside sources you consulted, apart from the textbook, your notes, and the course staff. If you did not collaborate with anyone, please explicitly write, “No collaborators.”}\\
	
	
	\begin{problem} In a tree, a \textbf{leaf} is a vertex of degree 1. Prove that any tree on $n\geq 2$ vertices has at least two leaves.
	\end{problem}

	\begin{problem} 
	Show that if $G$ is a graph in which there is a \ul{unique} path between each pair of vertices, then $G$ is a tree. \\
	
	\emph{In fact, the converse is also true: in any tree, there is a unique path between each pair of distinct vertices. This means that we can give another characterization of trees: $G$ is a tree if and only if there is a unique path between each pair of distinct vertices. If you are interested, I encourage you to try proving this as well!}
	\end{problem}








	
	\begin{problem}\mbox{}   
	\begin{itemize}
		\item[\textbf{(a)}] Prove that any forest with $n$ vertices and $k$ components has exactly $n-k$ edges.
		\item[\textbf{(b)}] Prove that any $n$-vertex graph with at least $n$ edges contains a cycle.
	\end{itemize}	
	\end{problem}
	
	\begin{problem}   
		Answer \textbf{Question 3.3} at the end of chapter 3 of the textbook.\\
		
		\textit{For part (a), you can interpret ``show all your work" as ``specify the order in which the vertices and the edges are added to the tree." For parts (a)--(d), you do not need to show any work or justify your answers. And this is the graph you should reference for this problem:}
		
		\begin{figure}[H]
			\centering
			\begin{minipage}{.36\textwidth}
				\includegraphics[width=1\linewidth]{./hw3_graph}
				
			\end{minipage}
		\end{figure}
		

	\end{problem}
	

	
	
	
	
\end{document} 