% 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}{2}
\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 1.31}{Prove or disprove that a graph is bipartite if and only if no two adjacent vertices have the same distance from any other vertex.}

% Put your answer to question 1 here

\cleardoublepage

% Question 2
\question{2, Diestel 1.35}{Prove or disprove that every connected graph contains a walk that traverses each of its edges exactly once in each direction.}

% Put your answer to question 2 here

\cleardoublepage

% Question 3
\question{3, Diestel 1.49}{Let $A = (a_{ij})_{n \times n}$ be the adjacency matrix of the graph $G$. Show that the matrix $A^k = (a_{ij}')_{n \times n}$ displays, for all $i,j \le n$, the number $a'_{ij}$ of walks of length $k$ from $v_i$ to $v_j$ in $G$.}

% Put your answer to question 3 here

\cleardoublepage

% Question 4
\question{4}{Let $G$ be a connected graph whose edges have been assigned real numbers. As mentioned on page 14 of the text, $G$ has at least one spanning tree. The \emph{weight} of a spanning tree is the sum of the numbers on its edges. The \emph{spectrum} of a spanning tree is the list of the numbers on its edges (each number listed as many times as it occurs on the edges of the tree) in non-decreasing order. Show that any two spanning trees of minimum weight (among all spanning trees of $G$) must have the same spectrum.}

% Put your answer to question 4 here

\cleardoublepage

% Question 5
\question{5}{An oriented complete graph is called a \emph{tournament}. The  \emph{outdegree} of a vertex v, written $od(v)$, is the number of edges directed away from v.
Let $T$ be a tournament with $n$ vertices. Find a formula for the number of directed 3-cycles in $T$ in terms of $n$ and the outdegrees of the vertices of $T$.}

% Put your answer to question 5 here

\cleardoublepage

% Question 6
\question{6}{Let $G$ be a graph with vertices $\{v_1,v_2,\ldots,v_n\}$. Let the matrix $M$ be defined by
\[ m_{ij} = \begin{cases}
d(v_i) & \text{if $i=j$}\\
-1 & \text{if $v_i$ is adjacent to $v_j$}\\
0 & \text{otherwise.}
\end{cases} \]
The \textbf{Matrix Tree Theorem} states that the number of spanning trees of $G$ is equal to the value of any cofactor of $M$. Use the matrix tree theorem to find the number of spanning trees in $K_{n,n}$.}

% Put your answer to question 6 here

\end{document}
