\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage{amsfonts,amsmath,amssymb,amsthm}

\PassOptionsToPackage{obeyspaces}{url}
\usepackage[colorlinks=true,citecolor=blue,urlcolor=blue,linkcolor=blue,bookmarksopen=true]{hyperref}
\usepackage{tikz}

\usepackage{enumitem}
\setlist{itemsep=0.5em}

%% header definitions
\def\course{MATH 314}
\def\assign{HW \#6}
\def\due{Mar 1}
\def\doclink{\url{https://mathematicaster.org/teaching/graphs2022/hw/hw6.tex}}

%% environments
% theorem style
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{defn}[theorem]{Definition}

% definition style
\theoremstyle{definition}
\newtheorem{problem}{Problem}

% custom
\newenvironment{solution}{\paragraph{Solution.}}{\qed}

%% custom commands
\newcommand*{\arXiv}[1]{\href{http://arxiv.org/pdf/#1}{arXiv:#1}}       % arXiv link
\newcommand*{\eqdef}{\stackrel{\mbox{\normalfont\tiny{def}}}{=}}        % definition by equality
\newcommand*{\abs}[1]{\lvert #1\rvert}     % absolute values, cardinality
\newcommand*{\eps}{\varepsilon}            % prettier epsilon
\newcommand*{\R}{\mathbb{R}}               % real numbers
\newcommand*{\C}{\mathbb{C}}               % complex numbers
\newcommand*{\Q}{\mathbb{Q}}               % rational numbers
\newcommand*{\Z}{\mathbb{Z}}               % integers
\newcommand*{\N}{\mathbb{N}}               % natural numbers
\newcommand*{\F}{\mathbb{F}}               % field
\newcommand*{\family}{\mathcal{F}}         % family
\newcommand*{\GL}{\mathbf{GL}}             % general linear group
\newcommand*{\what}[1]{\widehat{#1}}       % wider hat
\newcommand*{\wbar}[1]{\overline{#1}}      % wider bar
\newcommand*{\mcal}[1]{\mathcal{#1}}       % mathcal
\newcommand*{\mbf}[1]{\mathbf{#1}}         % mathbf
\newcommand*{\mbb}[1]{\mathbb{#1}}         % mathbb

% operators
\let\Pr\relax\DeclareMathOperator*{\Pr}{\mathbf{Pr}}       % probability
\DeclareMathOperator*{\E}{\mathbb{E}}          % expectation
\DeclareMathOperator*{\Var}{\mathbf{Var}}      % variance
\DeclareMathOperator*{\Span}{span}             % span
\DeclareMathOperator{\tr}{tr}                  % trace
\DeclareMathOperator{\rank}{rank}              % rank
\DeclareMathOperator{\supp}{supp}              % support
\DeclareMathOperator{\diam}{diam}
\DeclareMathOperator{\Aut}{Aut}



\begin{document}
\pagestyle{empty}

\noindent
\begin{minipage}{.33\textwidth}
	\flushleft {\bf \course}
\end{minipage}
\begin{minipage}{.33\textwidth}
	\centering {\bf \assign}
\end{minipage}
\begin{minipage}{.33\textwidth}
	\flushright {\bf \due}
\end{minipage}
\vskip3pt
\hrule\hrule\hrule
\vskip5pt

\noindent {\footnotesize This document is from \doclink}
\vskip10pt

\noindent {\small Unless explicitly requested by a problem, do not include sketches as part of your proof.
You are free to use the result from any problem on this (or previous) assignment as a part of your solution to a different problem even if you have not solved the former problem.
}

\vskip20pt

\begin{problem}[0.5 + 0.5 pts]
    Determine the Pr\"ufer code of the following trees (using the standard ordering of the integers).
    \begin{enumerate}
        \item \phantom{hi}
            \begin{center}
                \begin{tikzpicture}[main/.style = {draw, circle}, scale = 1.5]
                    \node[main] (1) at (0,0) {1};
                    \node[main] (2) at (-1,0) {2};
                    \node[main] (3) at (2,0) {3};
                    \node[main] (4) at (1,1) {4};
                    \node[main] (5) at (1,-1) {5};
                    \node[main] (6) at (0,-1) {6};
                    \node[main] (7) at (1,0) {7};
                    \node[main] (8) at (0,1) {8};
                    \draw (2)--(1)--(7)--(3);
                    \draw (8)--(1)--(6);
                    \draw (4)--(7)--(5);
                \end{tikzpicture}
            \end{center}
        \item \phantom{hi}
            \begin{center}
                \begin{tikzpicture}[main/.style = {draw, circle}, scale = 1.5]
                    \node[main] (1) at (0,0) {1};
                    \node[main] (2) at (2,1) {2};
                    \node[main] (3) at (1,1) {3};
                    \node[main] (4) at (1,0) {4};
                    \node[main] (5) at (4,0) {5};
                    \node[main] (6) at (3,0) {6};
                    \node[main] (7) at (4,1) {7};
                    \node[main] (8) at (5,0) {8};
                    \node[main] (9) at (2,0) {9};
                    \draw (1)--(4)--(9)--(6)--(5)--(8);
                    \draw (3)--(2)--(9);
                    \draw (7)--(5);
                \end{tikzpicture}
            \end{center}
    \end{enumerate}
\end{problem}


\begin{problem}[0.5 + 0.5 pts]
    For the following sequences, draw a picture of the (labeled) tree which has that sequence as its Pr\"ufer code (using the standard ordering of the integers).
    Your tree should have vertex-set $[n]$ for some integer $n$.
    \begin{enumerate}
        \item $(5,7,5,1,3,5,5)$
        \item $(4,4,1,2,1,2,3)$
    \end{enumerate}
\end{problem}


\begin{problem}[1 pts]
    Determine (with proof) all trees $T$ (up to isomorphism) on $n\geq 2$ vertices whose Pr\"ufer code uses each element of $V(T)$ at most once (under any arbitrary ordering of $V(T)$).
\end{problem}


\begin{problem}[2 pts]
    (HW5.3 revisited)
    Fix an integer $n\geq 2$ and let $d_1,\dots,d_n$ be a sequence of positive integers with $\sum_{i=1}^nd_i=2n-2$.
    Use Pr\"ufer codes to show that there is a tree with degree sequence $d_1,\dots,d_n$.
\end{problem}


\begin{problem}[2 pts]
    For a graph $G$, define the relation $R$ on $V(G)$ by $u\mathbin R v$ if and only if $u=v$ or there is a cycle in $G$ containing both $u$ and $v$.
    Find a graph $G$ wherein $R$ is \emph{not} an equivalence relation on $V(G)$.
    (You are welcome to define $G$ via a picture, though, of course, you must still demonstrate that $R$ is not an equivalence relation on this $G$)
\end{problem}


\begin{problem}[3 pts]
    For a graph $G$, define the relation $R$ on $E(G)$ by $e\mathbin R s$ if and only if $e=s$ or there is a cycle in $G$ containing both $e$ and $s$.
    Prove that $R$ is an equivalence relation on $E(G)$.
\end{problem}




\end{document}
