\documentclass{article}
\usepackage{amsthm, amssymb, amsmath,verbatim}
\usepackage[margin=1in]{geometry}
\usepackage{enumerate}
\usepackage{graphicx}

\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\N}{\mathbb{N}}



\newtheorem*{claim}{Claim}
\newtheorem{ques}{Question}


\title{Math 154 Homework 3}
\date{Fall 2021}

\begin{document}

\maketitle

This homework is due on gradescope by Friday October 15th at 11:59pm pacific time. Remember to justify your work even if the problem does not explicitly say so. Writing your solutions in \LaTeX is recommend though not required.

Please cite any other students with whom you collaborated on any problems.

\begin{ques}[Short Cycles, 30 points]
If $G$ is a connected graph on $n$ vertices with $n$ edges, we know it must contain a cycle. Prove that if $G$ has $n+1$ edges, it must contain a cycle of length at most $(2n/3)+2$. Hint: Consider $G$ as a tree plus two extra edges. Consider how the tree connects those $4$ endpoints and how to connect them up to make a cycle.
\end{ques}

\begin{ques}[MSTs Have the Same Edge Weights, 30 points]
Let $G$ be a weighted graph and let $T$ and $T'$ be two different Minimum Spanning Trees of $G$. Show that the set of weights of edges in $T$ is the same as the set of the weights of the edges in $T'$. Conclude that if the edges of $G$ all have distinct weights that there is a unique minimum spanning tree.

Hint: If $e\in T$ has a weight not in $T'$ try adding it to $T'$. This will allow you to improve $T'$ unless there is a cycle containing only $e$ and edges of lighter weight. In the latter case, find a way to improve $T$.
\end{ques}

\begin{ques}[Average Number of Leaves, 20 points]
How many trees on vertices labelled $1,2,\ldots,n$ have the vertex labelled $k$ as a leaf? Use this to compute the average number of leaves of a tree with vertices labelled $1,2,\ldots,n$ and show that this number is approximately $n/e$ for large values of $n$.
\end{ques}

\begin{ques}[Last Caley Edges, 20 points]
Recall that in our proof of Caley's Theorem that when converting a tree on vertices labelled $1,2,\ldots,n$ that we stopped removing leaves when there were two vertices left. Prove that these vertices are the one labelled $n$ and the neighbor of this vertex along the unique path from the vertex labelled $n$ and the vertex labelled $n-1$.
\end{ques}

\begin{ques}[Extra credit, 1 point]
Approximately how much time did you spend on this homework?
\end{ques}

\end{document} 