\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}


%%%%% 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 3}
\author{NAME}
%\date{\today}                                           % Activate to display a given date or no date

\begin{document}
\maketitle

%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{enumerate}[\qquad]
\item[\bf 1.3.8] {\bf Which of the following are graphic sequences? Provide a construction of a proof of impossibility for each.}\\


\begin{enumerate}
\item $(5,5,4,3,2,2,2,1)$
\item $(5,5,4,4,2,2,1,1)$
\item $(5,5,5,3,2,2,1,1)$
\item $(5,5,5,4,2,1,1,1)$
\end{enumerate}


\bigskip



%%%%%%%%%%%%%%%%%%%%%%%%%
\item[\bf 1.3.18] {\bf For $k \geq 2$, prove that a $k$-regular bipartite graph has no cut-edge.}\\


\bigskip



%%%%%%%%%%%%%%%%%%%%%%%%%
\item[\bf 1.3.25] {\bf Prove that every cycle of length $2r$ in a hypercube is contained in a subcube of dimension at most $r$. Can a cycle of length $2r$ be contained in a subcube of dimension less than $r$?}\\


\bigskip



%%%%%%%%%%%%%%%%%%%%%%%%%
\item[\bf 1.3.32] {\bf Prove that the number of simple even graphs with vertex set $[n]$ is $2^{\binom{n-1}{2}}$.}\\
(Hint: establish a bijection with the set of all simple graphs on $V(G) = [n-1]$.) 

\bigskip



%%%%%%%%%%%%%%%%%%%%%%%%%
\item[\bf 1.3.44] {\bf Let $G$ be a loopless graph with average vertex degree $a = 2e(G)/n(G)$.}\\

\begin{enumerate}
\item {\bf Prove that $G - x$ has average degree at least $a$ if and only if $d(x) \leq a/2$.}

\item {\bf Use part (a) to give an algorithmic proos that if $a > 0$, then $G$ has a subgraph with minimum degree greater than $a/2$. }

\item {\bf Show that there is no constant $c$ greater than $1/2$ such that $G$ must have a subgraph with minimum degree greater than $ca$; this proves that the bound in part (b) is best possible.} (Hint: used $K_{1,n-1}$.) 

\end{enumerate}

\bigskip



%%%%%%%%%%%%%%%%%%%%%%%%%
\item[\bf 1.3.63] {\bf Let $d_1, \dots, d_n$ be integers such that $d_1 \geq \cdots \geq d_n \geq 0$. Prove that there is a loopless graph (multiple edges allowed) with degree sequence $d_1, \dots, d_n$ if and only if $\sum_i d_i$ is even and $d_1 \leq d_2 + \cdots d_n.$ (Hakimi [1962])  }\\


\bigskip



%%%%%%%%%%%%%%%%%%%%%%%%%
\item[\bf 1.4.8] {\bf Prove that there is an $n$-vertex tournament with in-degree equal to out-degree at every vertex if and only if $n$ is odd.}\\


\bigskip



%%%%%%%%%%%%%%%%%%%%%%%%%
\item[\bf 1.4.10] {\bf Prove that a digraph is strongly connected if and only if for each partition of the vertex set into non-empty sets $S$ and $T$, there is an edge from $S$ to $T$.}\\


\bigskip



%%%%%%%%%%%%%%%%%%%%%%%%%
\item[\bf 1.4.14] {\bf Let $G$ be an $n$-vertex digraph with no cycles. Prove that the vertices of $G$ can be ordered as $v_1, \dots, v_n$ so that if $v_iv_j \in E(G)$, then $i<j$.}\\


\bigskip


%%%%%%%%%%%%%%%%%%%%%%%%%
\item[\bf 2.1.2] {\bf Let $G$ be a graph.}
\begin{enumerate}
\item {\bf Prove that $G$ is a tree if and only if $G$ is connected and every edge is a cut edge.}
\item {\bf Prove that $G$ is a tree if and only if $G$ is loopless and adding any edge with endpoints in $V(G)$ creates exactly one cycle.}
\end{enumerate} 



\bigskip



%%%%%%%%%%%%%%%%%%%%%%%%%
\item[\bf 2.1.18] {\bf Prove that every tree with maximum degree $\Delta > 1$ has at least $\Delta$ leaves. Show that this is the best possible by constructing an $n$-vertex tree with exactly $\Delta$ leaves foe each choice of $n$, $\Delta$ with $n > \Delta \geq 2$.}\\

\end{enumerate}


\end{document}  