\documentclass[11pt]{scrartcl} \usepackage[headheight=1pt, includeheadfoot, headsep=1cm, top=1.5cm, bottom=1.3cm, left=2cm, right=2cm]{geometry} \usepackage{mathtools} \usepackage{amsmath,amsthm, amscd, amssymb, amsfonts} \usepackage[english]{babel} \usepackage{fancyhdr} \usepackage{enumitem} \setlist{itemsep=0.5em} \usepackage{xcolor} \definecolor{forestgreen}{rgb}{0.13, 0.55, 0.13} \usepackage[colorlinks = true, linkcolor = forestgreen, urlcolor = forestgreen, citecolor = forestgreen, anchorcolor = forestgreen]{hyperref} \usepackage{multicol} \usepackage{multienum} \usepackage{euler} \usepackage[OT1]{eulervm} \renewcommand{\rmdefault}{pplx} \usepackage{tikz} \usepackage{mathabx} \usepackage{lastpage} \usepackage{tikz} \usepackage{verbatim} \usetikzlibrary{shapes.geometric,shapes.multipart,arrows,calc} \pgfdeclarelayer{background} \pgfdeclarelayer{foreground} \pgfsetlayers{background,main,foreground} \tikzset{ edge/.style = {black, ultra thick, outer sep=2pt}, vertex/.style = {draw=black, very thick, fill=white, circle, minimum width=8pt, inner sep=2pt, outer sep=1pt}, arc/.style = {black, ultra thick, outer sep=2pt, decoration={markings, mark=at position #1 with {\arrow[scale=1.5]{latex}}}, postaction=decorate}, arc/.default = 0.58 } %% header, footer definitions \def\course{MATH 314} \def\courselink{https://www.gsanmarco.com/graph-theory} \def\assignment{HW \#6} \def\assignlink{hw06.tex} \def\due{Due on Feb 28} \pagestyle{fancy} \fancyhead[L]{\course} \fancyhead[C]{\assignment} \fancyhead[R]{\due} %\renewcommand{\footrulewidth}{0.4pt} %\fancyfoot{} %\fancyfoot[R]{\fontsize{8}{10} \selectfont Page \thepage~of \pageref{LastPage}} %\fancyfoot[L]{\fontsize{10}{12} \selectfont Source file available at \href{\courselink}{\textbf{\courselink}}} %% 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} \newtheorem{Solution}{Solution} % custom \newenvironment{solution}{\noindent\textbf{Solution.}}{\qed} %% custom commands \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} \begin{document} \noindent 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. \vskip10pt \begin{problem}[0.5 + 0.5 pts] Determine the Pr\"ufer code of the following trees, using the ordering $v_1\leq v_2\leq \dots$ for the vertices. \begin{multicols}{2} \begin{enumerate}[leftmargin=*, label=(\alph*)] \item \phantom{hi} \begin{center} \begin{tikzpicture}[main/.style = {draw, circle}, scale = 1.5] \node[main] (1) at (0,0) {$v_1$}; \node[main] (2) at (-1,0) {$v_2$}; \node[main] (3) at (2,0) {$v_3$}; \node[main] (4) at (2,1) {$v_4$}; \node[main] (5) at (2,-1) {$v_5$}; \node[main] (6) at (-1,-1) {$v_6$}; \node[main] (7) at (1,0) {$v_7$}; \node[main] (8) at (-1,1) {$v_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 (1,-1) {$v_1$}; \node[main] (2) at (2,1) {$v_2$}; \node[main] (3) at (1,1) {$v_3$}; \node[main] (4) at (2,-1) {$v_4$}; \node[main] (5) at (4,0) {$v_5$}; \node[main] (6) at (3,0) {$v_6$}; \node[main] (7) at (5,1) {$v_7$}; \node[main] (8) at (5,-1) {$v_8$}; \node[main] (9) at (2,0) {$v_9$}; \draw (1)--(4)--(9)--(6)--(5)--(8); \draw (3)--(2)--(9); \draw (7)--(5); \end{tikzpicture} \end{center} \end{enumerate} \end{multicols} \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 $\{v_1, \dots, v_n\}$ for some integer $n$. \begin{multicols}{2} \begin{enumerate}[leftmargin=*, label=(\alph*)] \item $(v_5,v_7,v_5,v_1,v_3,v_5,v_5)$ \item $(v_4,v_4,v_1,v_2,v_1,v_2,v_3)$ \end{enumerate} \end{multicols} \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] 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}