\documentclass[11pt]{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}{-.875in}
\addtolength{\evensidemargin}{-.875in}
\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{\myhwnum}{1}
\newcommand{\myclass}{21-484 Graph Theory}

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

\begin{document}
% Question 1
\question{1, Diestel 1.2}{Let $d \in \mathbb{N}$ and $V := \{0,1\}^d$; thus, $V$ is the set of all 0\textendash1 sequences of length $d$. The graph on $V$ in which two such sequences form an 
edge if and only if they differ in exactly one position is called the \textit{d-dimensional cube}. Determine the average degree, number of edges, diameter, girth and circumference of this graph.

(Hint for the circumference: induction on $d$.)}

\vspace{.75in}
% Put your answer to question 1 here

\newpage

% Question 2
\question{2, Diestel 1.8}{Show that graphs of girth at least 5 and order n have a minimum degree of $o(n)$. In other words, show
that there is a function $f:\mathbb{N} \to \mathbb{N}$ such that $f(n)/n \rightarrow 0$ as $n \rightarrow \infty$ and $\delta(G) \leq f(n)$
for all such graphs $G$.}

\vspace{.75in}
% Put your answer to question 2 here

\newpage

% Question 3
\question{3, Diestel 1.9}{Show that every connected graph $G$ contains a path of length at least $\min\{2\delta(G), |G|-1\}$.}

\vspace{.75in}
% Put your answer to question 3 here

\newpage

% Question 4
\question{4, Diestel 1.13}{Determine $\kappa(G)$ and $\lambda(G)$ for $G= P^m, C^n, K^n, K_{m,n}$ and the $d$-dimensional cube (Exercise 2); $d,m,n \ge 3$.}

\vspace{.75in}
% Put your answer to question 4 here

\newpage

% Question 5
\question{5, Diestel 1.21}{Show that a tree without a vertex of degree 2 has more leaves than other vertices. Can you find a very short proof that does not use induction?}

\vspace{.75in}
% Put your answer to question 5 here

\newpage

% Question 6
\question{6, Diestel 1.28}{Show that every automorphism of a tree fixes a vertex or an edge.}

\vspace{.75in}
% Put your answer to question 6 here

\newpage

% Question 7
\question{7}{A graph is \textit{self-complementary} if it is isomorphic to its complement. Show that:}
\part{a} The number of vertices in any self-complementary graph is congruent to 0 or 1 mod 4.

\vspace{.75in}
% Put your answer to question 7a here

\part{b} Every self-complementary graph on $4k+1$ vertices has a vertex of degree $2k$.

\vspace{.75in}
% Put your answer to question 7b here

\newpage

% Question 8
\question{8}{A tree is \textit{homeomorphically irreducible} if it has no vertices of degree 2. Draw all non-isomorphic, 
homeomorphically irreducible trees on 10 vertices. Explain why all such trees are represented among your drawings.}

\vspace{.75in}
% Put your answer to question 8 here



\end{document}
