% To print single-sided: delete ",twoside" below
\documentclass[11pt,twoside]{article}

% Some very basic packages. Feel free to add your favorites!
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{fancyhdr}
\usepackage{graphicx}

% Set up the page correctly
\addtolength{\oddsidemargin}{-.54in}
\addtolength{\evensidemargin}{-1.2in}
\addtolength{\textwidth}{1.75in}
\addtolength{\topmargin}{-.875in}
\addtolength{\textheight}{1.75in}
\setlength{\parindent}{0pt}
\setlength{\parskip}{5pt plus 1pt}

% Some nifty commands. Thanks Adam Blank!
\newcommand{\question}[2] {\vspace{.25in} \hrule\vspace{0.5em}
\noindent{{\bf #1:} #2} \vspace{0.5em}
\hrule \vspace{.10in}}
\renewcommand{\part}[1] {\vspace{.10in} {\bf (#1)}}

% Add an image centered on the page.
% The first parameter is a scale factor (set to 1 for no scale)
% The second paramter is the image file. Make sure it is in the same folder as your .tex file!
\newcommand{\centergfx}[2]{\begin{center}\includegraphics[scale = #1]{#2}\end{center}}

% Command to insert a minus sign with a dot over it. Stolen from
% http://www.cs.miami.edu/~burt/learning/Math688.931/Other/errata.tex
\newcommand{\monus}{\stackrel{{}^{\scriptstyle .}}{\smash{-}}}

%%%%%%%%%%%%%%%%%%%%%
%		Replace "Name" and                 %
%		   "andrewid" below                   %
%%%%%%%%%%%%%%%%%%%%%
\newcommand{\myname}{Name}
\newcommand{\myandrew}{(andrewid)}
\newcommand{\mysection}{ - X}
\newcommand{\myhwnum}{8}
\newcommand{\myclass}{21-484 Graph Theory}

% Set up the nice header
\pagestyle{fancyplain}
\lhead{\fancyplain{}{\textbf{HW\myhwnum}}}
\rhead{\fancyplain{}{\myname \ \myandrew \ \mysection}}
\chead{\fancyplain{}{\myclass}}

\begin{document}

% Question 1
\question{1, Diestel 7.17}{Prove the Erd\H{o}s-S\'os conjecture for the case when the tree considered is a path.

(Hint. Use Exercise 9 of Chapter 1.)}

\newpage

% Question 2
\question{2, Diestel 7.18}{Can large average degree force the chromatic number up if we exclude some tree as an induced subgraph? 
More precisely: For which trees $T$ is there a function $f : \mathbb{N} \to \mathbb{N}$ such that, for every $k \in \mathbb{N}$, 
every graph of average degree at least $f(k)$ either has chromatic number at least $k$ or contains an induced copy of $T$?}

\newpage

% Question 3
\question{3, Diestel 7.21}{Given a graph $G$ with $\varepsilon(G) \geqslant k \in \mathbb{N}$, find a minor $H \preccurlyeq G$ such that\\
$\delta(H) \geqslant k \geqslant |H|/2$.}

\newpage

%Question 4
\question{4, Diestel 7.23}{Show that any function $h$ as in Lemma 3.5.1 satisfies the inequality $h(r) > \frac18 r^2$ for all even $r$, 
and hence that Theorem 7.2.3 is best possible up to the value of the constant $c$.}

\newpage

% Question 5
\question{5, Diestel 7.33}{Prove Hadwiger's conjecture for $r = 4$ from first principles. Hint: Use induction on $|G|$. Color a shortest cycle
in $G$ (if $G$ has a cycle) and extend the coloring to the rest of the graph.}

\newpage

% Question 6
\question{6, Diestel 7.35}{Prove Corollary 7.3.5: A graph with $n > 2$ vertices and no $K^5$ minor has at most $3n - 6$ edges.}


\end{document}
