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

%%%%%%%%%%%%%%%%%%%%%
%		Replace "Name" and                 %
%		   "andrewid" below                   %
%%%%%%%%%%%%%%%%%%%%%
\newcommand{\myname}{Name}
\newcommand{\myandrew}{(andrewid)}
\newcommand{\mysection}{ - X}
\newcommand{\myhwnum}{3}
\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}{Suppose that 13 people are each dealt 4 cards from a standard
52-card deck. Show that it is possible for each of them to select one of their
cards so that no two people have selected a card of the same rank.}

% Put your answer to question 1 here

\cleardoublepage

% Question 2
\question{2, Diestel 2.4}{Moving alternatively, two players jointly construct a
path in some fixed graph $G$. If $v_1, \ldots, v_n$ is the path constructed so
far, the player to move next has to find a vertex $v_{n+1}$ such that $v_1,
\ldots, v_{n+1}$ is again a path. Whichever player cannot move loses. For which
graphs $G$ does the first player have a winning strategy, for which the second?}

% Put your answer to question 2 here

\cleardoublepage

% Question 3
\question{3, Diestel 2.10}{Prove \textit{Sperner's theorem:} in an $n$-set $X$
there are never more than $\binom{n}{\lfloor n / 2 \rfloor}$ subsets such that
none of these contain another.

(Hint. Construct $\binom{n}{\lfloor n / 2 \rfloor}$ chains covering the
power set lattice of $X$.)}

% Put your answer to question 3 here

\cleardoublepage

% Question 4
\question{4, Diestel 2.18}{Show that a graph $G$ contains $k$ independent edges
if and only if $q(G-S) \le |S| + |G| - 2k$ for all sets $S \subseteq V(G)$.}

% Put your answer to question 4 here

\cleardoublepage

% Question 5
\question{5, Diestel 2.24}{Show that if $G$ has two edge-disjoint spanning
trees, it has a connected spanning subgraph all whose degrees are even.}

% Put your answer to question 5 here

\cleardoublepage

% Question 6
\question{6}{Show that a tree $T$ has a perfect matching if and only if $q(T-v)
= 1$ for every $v \in V(T)$.}

% Put your answer to question 6 here

\end{document}
