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