% 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 parameter 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}{5}
\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 3.5}{Deduce the $k=2$ case of Menger's theorem (3.3.1) from Proposition 3.1.1.}

\cleardoublepage

% Question 2
\question{2, Diestel 3.17 (i)}{Find the error in the following `simple proof' of
Menger's theorem (3.3.1). Let $X$ be an $A$--$B$ separator of minimum size.
Denote by $G_A$ the subgraph of $G$ induced by $X$ and all the components of
$G-X$ that meet $A$, and define $G_B$ correspondingly. By the minimality of $X$,
there can be no $A$--$X$ separator in $G_A$ with fewer than $|X|$ vertices, so
$G_A$ contains $k$ disjoint $A$--$X$ paths by induction. Similarly, $G_B$
contains $k$ disjoint $X$--$B$ paths. Together, all these paths form the desired
$A$--$B$ paths in $G$.}

\cleardoublepage

% Question 3
\question{3, Diestel 3.18}{Prove Menger's theorem by induction on $||G||$, as
follows. Given an edge $e=xy$, consider a smallest $A$--$B$ separator $S$ in
$G-e$. Show that the induction hypothesis implies a solution for $G$ unless $S
\cup \{x\}$ and $S \cup \{y\}$ are smallest $A$--$B$ separators in $G$. Then
show that if choosing neither of these separators as $X$ in the previous
exercise gives a valid proof, there is only one easy case left to do.}

\cleardoublepage

% Question 4
\question{4, Diestel 3.21}{Let $k \ge 2$. Show that every $k$-connected graph of
order at least $2k$ contains a cycle of length at least $2k$.}

\cleardoublepage

% Question 5
\question{5, Diestel 3.22}{Let $k \ge 2$. Show that in a $k$-connected graph any
$k$ vertices lie on a common cycle.}

\end{document}
