\documentclass[11pt]{amsart}
\usepackage{geometry}                % See geometry.pdf to learn the layout options. There are lots.
\geometry{letterpaper}                   % ... or a4paper or a5paper or ... 
%\geometry{landscape}                % Activate for for rotated page geometry
\usepackage[parfill]{parskip}    % Activate to begin paragraphs with an empty line rather than an indent
\usepackage{amsfonts, amscd, amssymb, amsthm, amsmath}
\usepackage{pdfsync}%leaves makers for tex searching
\usepackage{enumerate}

%%%%% Margins %%%%% 
\setlength{\topmargin}{1in} %top/bot margins
\setlength{\oddsidemargin}{\topmargin} %sidemargins

\setlength{\textheight}{11in} \setlength{\textwidth}{8.5in}
\setlength{\hoffset}{-1in} \setlength{\voffset}{-1in} \setlength{\evensidemargin}{\oddsidemargin} \addtolength{\textheight}{-2 \topmargin}\addtolength{\textwidth}{-2\oddsidemargin}
\setlength{\headheight}{0pt} \setlength{\headsep}{20pt} \setlength{\footskip}{20pt}
\addtolength{\textheight}{-\footskip} \addtolength{\textheight}{-\headheight} \addtolength{\textheight}{-\headsep}



%%%%% Theorems %%%%% 
\theoremstyle{plain}
	\newtheorem{thm}{Theorem}[section]
	\newtheorem{lemma}[thm]{Lemma}
	\newtheorem{prop}[thm]{Proposition}
	\newtheorem{cor}[thm]{Corollary}
\theoremstyle{definition}
	\newtheorem*{defn}{Definition}
	\newtheorem{remark}[thm]{Remark}
\theoremstyle{example}
	\newtheorem*{example}{Example}


%%%%% Pictures %%%%% 
\usepackage{etex} %fixes the fight that pictex has with every other drawing package
\usepackage{pictexwd}
\usepackage{tikz}
\tikzstyle{V}=[draw, fill =black, circle, inner sep=0pt, minimum size=4pt]

\usepackage{graphicx}
\usepackage{epstopdf}
\DeclareGraphicsRule{.tif}{png}{.png}{`convert #1 `dirname #1`/`basename #1 .tif`.png}
\usepackage[pdftex,bookmarks]{hyperref}


%%%%% Color  %%%%% 
\usepackage{color}
\definecolor{dred}{rgb}{.65, 0, 0.15}
\newcommand{\NOTE}[1]{{\color{blue}#1}}
\newcommand{\MOVED}[1]{{\color{gray}#1}}


%%%%% Alphabets %%%%% 
\def\cA{\mathcal{A}}\def\cB{\mathcal{B}}\def\cC{\mathcal{C}}\def\cD{\mathcal{D}}\def\cE{\mathcal{E}}\def\cF{\mathcal{F}}\def\cG{\mathcal{G}}\def\cH{\mathcal{H}}\def\cI{\mathcal{I}}\def\cJ{\mathcal{J}}\def\cK{\mathcal{K}}\def\cL{\mathcal{L}}\def\cM{\mathcal{M}}\def\cN{\mathcal{N}}\def\cO{\mathcal{O}}\def\cP{\mathcal{P}}\def\cQ{\mathcal{Q}}\def\cR{\mathcal{R}}\def\cS{\mathcal{S}}\def\cT{\mathcal{T}}\def\cU{\mathcal{U}}\def\cV{\mathcal{V}}\def\cW{\mathcal{W}}\def\cX{\mathcal{X}}\def\cY{\mathcal{Y}}\def\cZ{\mathcal{Z}}

\def\AA{\mathbb{A}} \def\BB{\mathbb{B}} \def\CC{\mathbb{C}} \def\DD{\mathbb{D}} \def\EE{\mathbb{E}} \def\FF{\mathbb{F}} \def\GG{\mathbb{G}} \def\HH{\mathbb{H}} \def\II{\mathbb{I}} \def\JJ{\mathbb{J}} \def\KK{\mathbb{K}} \def\LL{\mathbb{L}} \def\MM{\mathbb{M}} \def\NN{\mathbb{N}} \def\OO{\mathbb{O}} \def\PP{\mathbb{P}} \def\QQ{\mathbb{Q}} \def\RR{\mathbb{R}} \def\SS{\mathbb{S}} \def\TT{\mathbb{T}} \def\UU{\mathbb{U}} \def\VV{\mathbb{V}} \def\WW{\mathbb{W}} \def\XX{\mathbb{X}} \def\YY{\mathbb{Y}} \def\ZZ{\mathbb{Z}}  

\def\fa{\mathfrak{a}} \def\fb{\mathfrak{b}} \def\fc{\mathfrak{c}} \def\fd{\mathfrak{d}} \def\fe{\mathfrak{e}} \def\ff{\mathfrak{f}} \def\fg{\mathfrak{g}} \def\fh{\mathfrak{h}} \def\fj{\mathfrak{j}} \def\fk{\mathfrak{k}} \def\fl{\mathfrak{l}} \def\fm{\mathfrak{m}} \def\fn{\mathfrak{n}} \def\fo{\mathfrak{o}} \def\fp{\mathfrak{p}} \def\fq{\mathfrak{q}} \def\fr{\mathfrak{r}} \def\fs{\mathfrak{s}} \def\ft{\mathfrak{t}} \def\fu{\mathfrak{u}} \def\fv{\mathfrak{v}} \def\fw{\mathfrak{w}} \def\fx{\mathfrak{x}} \def\fy{\mathfrak{y}} \def\fz{\mathfrak{z}}
\def\fgl{\mathfrak{gl}}  \def\fsl{\mathfrak{sl}}  \def\fso{\mathfrak{so}}  \def\fsp{\mathfrak{sp}}  
\def\GL{\mathrm{GL}} \def\SL{\mathrm{SL}}  \def\SP{\mathrm{SL}}

\def\<{\langle} \def\>{\rangle}
\def\ad{\mathrm{ad}} 
\def\Aut{\mathrm{Aut}}
\def\dim{\mathrm{dim}} 
\def\End{\mathrm{End}} 
\def\ev{\mathrm{ev}} 
\def\half{\hbox{$\frac12$}}
\def\Hom{\mathrm{Hom}} 
\def\qtr{\mathrm{qtr}} 
\def\tr{\mathrm{tr}} 
\def\Tr{\mathrm{Tr}} 
\def\vep{\varepsilon}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\title{Homework 5}
\author{TEMPLATE}
%\date{\today}                                           % Activate to display a given date or no date

\begin{document}
\maketitle

%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{enumerate}[\qquad]
\item[\bf 2.2.3] {\bf Let $G$ be the graph below. Use the Matrix Tree Theorem to find a matrix whose determinant is $\tau(G)$.}\\

$$\begin{tikzpicture}[scale=2]
\node[V, label=below:{1}](1) at (0,0){};
\node[V, label=below:{2}](2) at (1,0){};
\node[V, label=above:{3}](3) at (1,1){};
\node[V, label=above:{4}](4) at (0,1){};
\draw (1) to [bend left = 30] (2)
	(1) to [bend left = 10] (2)
	(1) to [bend right = 10] (2)
	(1) to [bend right = 30] (2)
	(2) to [bend right = 10] (3)
	(2) to [bend left = 10] (3)
	(4) to [bend right = 10] (3)
	(4) to [bend left = 10] (3)
	(4) to [bend right = 20] (1)
	(4) to [bend left = 20] (1);
\draw
	(1) to (3)
	(4) to (1);
\end{tikzpicture}$$

\bigskip



%%%%%%%%%%%%%%%%%%%%%%%%%
\item[\bf 2.2.10] {\bf Compute $\tau(K_{2,m})$. Also, compute the number of isomorphism classes of spanning trees of $K_{2,m}$.}\\
\bigskip



%%%%%%%%%%%%%%%%%%%%%%%%%
\item[\bf 2.2.23] {\bf Prove that if the Graceful Tree Conjecture is true and $T$ is a tree with $m$ edges, then $K_{2m}$ decomposes into $2m-1$ copies of $T$.}  {\small (Hint: Apply the cyclically invariant decomposition of $K_{2m-1}$ for trees with $m-1$ edges from the proof of Theorem 2.2.16.)}\\




\bigskip



%%%%%%%%%%%%%%%%%%%%%%%%%
\item[\bf 2.2.31] {\bf An \emph{up-down labeling} is a graceful labeling for which there exists a critical value $\alpha$ such that every edge joins vertices with labels above and below $\alpha$. Prove that ecery caterpillar has an up-down labeling. Prove that the 7-vertex tree that is not a caterpillar has no up-down labeling.}\\


\bigskip



%%%%%%%%%%%%%%%%%%%%%%%%%
\item[\bf 2.2.33] {\bf Let $T$ be an orientation of a tree wuch that the heads of the edges are all distinct; the one vertex that is not a head is the {\sl root}. Prove that $T$ is a union of paths from the root. Prove that for each vertex of $T$, exactly one path reaches it from the root. }\\
\bigskip



%%%%%%%%%%%%%%%%%%%%%%%%%
\item[\bf 2.3.2] {\bf Prove or disprove: if $T$ is a minimum-weight spanning tree of a weighted graph $G$, then a $u,v$-path in $T$ is a minimum-weight $u,v$-path in $G$.}\\
\bigskip



%%%%%%%%%%%%%%%%%%%%%%%%%
\item[\bf 2.3.4] {\bf In the graph obtained from $K_5$ by deleting two non-incident edges, assign weights $(1,1,2,2,3,3,4,4)$ to the edges in two ways: one way so that the minimum-weight spanning tree is unique, and another way so a minimum-weight spanning tree is not unique. }\\


\newcount\mycount
\begin{tikzpicture}[scale=2]
  \foreach \number in {1,...,5}{
      % Compute angle:        
      	\mycount=\number
        	\advance\mycount by -1
  	\multiply\mycount by 72
      \node[V, label=\the\mycount:{$v_{\number}$}] (\number) at (\the\mycount:1cm) {};
    } 

\draw (1) to node [right] {x} (2);
\draw (1) to [bend right=10] node [above right] {x} (3);
\draw (1) to node [right] {x} (5);
\draw (2) to node [above] {x} (3);
\draw (2) to [bend left=10] node [right] {x} (4);
\draw (3) to  node [left] {x} (4);
\draw (3) to [bend right=5] node [below ] {x} (5);
\draw (4) to node [below] {x} (5);
\end{tikzpicture}





\bigskip



%%%%%%%%%%%%%%%%%%%%%%%%%
\item[\bf 2.3.10] {\bf Prim's Algorithm grows a spanning tree from a given vertex of a connected weighted graph $G$, iteratively adding the cheapest edge from a vertex already reached to a vertex not yet reached, finishing when all the vertices of $V(G)$ have been reached. (Ties are broken arbitrarily.) Prove that Prim's Algorithm produces a minimum-weight spanning tree of $G$.}\\


\end{enumerate}


\end{document}  