\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}
\usepackage{graphicx}
\usepackage{epstopdf}
\DeclareGraphicsRule{.tif}{png}{.png}{`convert #1 `dirname #1`/`basename #1 .tif`.png}
\usepackage[pdftex,bookmarks]{hyperref}

\tikzstyle{V}=[draw, fill =black, circle, inner sep=0pt, minimum size=4pt]


%%%%% 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\diam{\mathrm{diam}} 
\def\End{\mathrm{End}} 
\def\ev{\mathrm{ev}} 
\def\half{\hbox{$\frac12$}}
\def\Hom{\mathrm{Hom}} 
\def\qtr{\mathrm{qtr}} 
\def\rad{\mathrm{rad}} 
\def\tr{\mathrm{tr}} 
\def\Tr{\mathrm{Tr}} 
\def\vep{\varepsilon}


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


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

\begin{document}
\maketitle



\begin{enumerate}[\qquad]
\item[\bf 2.1.13]{\bf Prove that every graph with diameter $d$ has an independent set with at least $\lceil (1+d)/2 \rceil$ vertices.}


\bigskip

\item[\bf 2.1.40]{\bf Let $G$ be a tree with $k$ leaves. Prove that $G$ is the union of paths $P_1, \dots , P_{\lceil k/2\rceil}$ such that $P_i \cap P_j \neq \emptyset$ for all $i \neq j$. }


\bigskip

\item[\bf 2.1.44]{\bf Prove or disprove: If a simple graph with diameter 2 has a cut-vertex, then its complement has an isolated vertex.}


\bigskip

\item[\bf 2.1.47] \emph{Diameter and radius}\\
\begin{enumerate}
\item {\bf Prove that the distance function $d(u,v)$ on pairs of vertices of a graph satisfies the triangle inequality: $d(u,w) \leq d(u,v) + d(v,w)$.}
\item {\bf Use part (a) to prove that $\diam(G) \leq 2 \rad(G)$ for every graph $G$.}
\item {\bf For all positive integers $r$ and $d$ that satisfy $f \leq d \leq 2r$, construct a simple graph with radius $r$ and diameter $d$.} (Hint: build a suitable graph with one cycle.)

\end{enumerate}


\bigskip

\item[\bf 2.1.62]{\bf Let $G$ be a connected graph with $n$ vertices. Define a new graph $G'$ having one vertex for each spanning tree of $G$, with vertices adjacent in $G'$ if and only if the corresponding trees have exactly $n(G) - 2$ common edges. PRove that $G'$ is connected. Determine the diameter of $G'$.} (an example is given in the book)



\bigskip

\item[\bf 2.1.68]{\bf Can the graph below be decomposed into edge-disjoint spanning trees? Into isomorphic edge-disjoint spanning trees?}


\centerline{\begin{tikzpicture}
\foreach \x in {1,2,3}{
	\foreach \y in {1,2,3}{
		\node[V, %label=right:{\tiny \x\y} %<- uncomment to see how the vertices are labeled
				](\x\y) at (\x+\y, .5*\x-.5*\y){}; 
}}
	\draw (31)--(21)--(11)--(12)--(13)--(23)--(33)--(32)--(31)--(22)--(32)--(23)--(22)--(12)--(21)--(22)--(13);
\end{tikzpicture}}
\bigskip

\NOTE{MORE TO COME}
\end{enumerate}



\end{document}  