\documentclass[12pt]{article}

\usepackage{graphicx}

\newfont{\bssdoz}{cmssbx10 scaled 1200}
\newfont{\bssten}{cmssbx10}


\oddsidemargin  0in \evensidemargin 0in \topmargin -0.5in
\headheight 0.25in \headsep 0.25in
\textwidth   6.5in \textheight 9in %\marginparsep 0pt \marginparwidth 0pt
\parskip 1.5ex  \parindent 0ex \footskip 20pt

\begin{document}
\parindent 0ex
\thispagestyle{empty} \vspace*{-0.75in}
{\bssdoz CME 305: Discrete Mathematics and Algorithms}
{\\ \bssten Instructor: Professor Amin Saberi (saberi@stanford.edu) }
{\\ \bssten HW\#1 --  Due 02/03/09}
\vspace{5pt}

\begin{enumerate}

\item For any undirected graph $G(V,E)$, calculate the quantity $\frac{1}{|E|} \sum_{v_i\in V}
d(v_i)$ where the degree of vertex $v_i$ is given by $d(v_i)$. From this deduce that in 
any graph the number of vertices of odd degree is even.

\item Recall the definition of a bipartite graph. Let $G(V,E)$ be a graph and $(A,B)$ 
be a partition of $V$. We say that $G$ is bipartite if all edges in $E$ have one end-point 
in $A$ and the other in $B$. More precisely, for all $(u, v) \in E$ either $u \in A, v \in B$
or $u \in B, v \in A$.

\begin{enumerate}
\item Prove that a graph is bipartite if and only if it doesn't have an odd cycle.
\item A graph is called $k$-regular if all vertices have degree $k$. Prove that if 
a bipartite $G$ is also $k$-regular with $k \geq 1$ then $|A| = |B|$.
\end{enumerate}

\item Let $G(V,E)$ be a simple graph. Define its complement $\bar{G}$ as a graph on the vertex
set $V$ with an edge set $\bar{E}$ (the complement of $E$).  

\begin{enumerate}
\item What is the degree sequence of $\bar{G}$ in terms of the degree sequence of $G$. 
\item An automorphism of a graph $G$ is a permutation of its vertices which preserves 
adjacency (i.e. $(u,v) \in E \Leftrightarrow (\phi(u),\phi(v)) \in E$). Let $Aut(G)$ be 
a set of automorphisms of $G$. Show that $Aut(G) = Aut(\bar{G})$.
\item Prove that at least one of $G$ and $\bar G$ is connected.
\end{enumerate}

\item Prove Cayley's theorem by linear algebra.  Recall that Cayley's theorem 
states that the number of labeled trees on $n$ vertices is $n^{n-2}$.

\begin{enumerate}

\item An oriented incidence matrix $B$ of a directed graph $G(V,E)$ is a matrix with
$n = |V|$ rows and $m = |E|$ columns with entry $B_{ve}$ equal to $1$ if edge $e$ 
enters vertex $v$ and $-1$ if it leaves vertex $v$. Let $M = BB^T$.  Show that for 
any $i \in \{1,\dots,n\}$,
\[\det M_{ii} = \sum_N (\det N)^2,\]
where $M_{ii} = M\backslash \{i^{th}$ row and column\}, and $N$ runs over
all $(n - 1) \times (n - 1)$ submatrices of $B\backslash\{i^{th}$ row\}.
Note that each submatrix $N$ corresponds to a choice of $n-1$ edges of $G$.

\item Show that 
\[\det N = 
\left\{ 
\begin{array}{rl}
\pm 1 & \mbox{if edges form a tree} \\
0 & \mbox{otherwise}
\end{array}
\right.
\] 
This implies that $t(G) = \det M_{ii}$, where $t(G)$ is the number of spanning 
trees of $G$. In this definition of a tree, we treat a directed edge as an 
undirected one.

\item Show that for the complete graph on $n$ vertices $K_n$, 
\[\det M_{ii} = n^{n-2}.\]  Conclude that this implies Cayley theorem.

\end{enumerate}

\item An $n$-dimensional cube can be represented by a graph with $2^n$
vertices with every vertex corresponding to an $n$-bit binary
number.  Two vertices are connected by an edge if their
corresponding binary numbers differ by only one bit. For example,
the following represents a 2-D cube.

\begin{figure}[htp]
\begin{center}
\includegraphics[scale=0.15]{2dcube.png}
\end{center}
\end{figure}

Prove that every $n$-dimensional cube has a Hamiltonian cycle.

\item A balanced digraph $G(V,E)$ is a directed graph with the in-degree 
and the out-degree equal for each vertex. An tree in a directed graph is 
a set of edges such that if directions were ingored the resulting graph 
is a tree. An in-tree is a (directed) tree with a root vertex $v$ such that 
from any vertex $u$ we can follow a directed path to $v$. An out-tree 
(arborescence) is one where the directed paths are from the root to the other 
vertices.

Consider the following algorithm: Given a connected balanced digraph $G(V,E)$, 
choose a spanning in-tree  $T$ rooted at any vertex $v \in V$. Start a path 
from $v$ and traverse the edges of $G$. The rule for choosing the next edge at 
every vertex $u$ is that if there is an unvisited edge going out of $u$ that 
does not belong to $T$, traverse that edge. Otherwise, take the tree-edge going 
out of $u$. Continue the path until there is no way out.

\begin{enumerate}
\item Give a reason why you can always choose the spanning in-tree $T$.
\item Prove that when the above algorithm stops every edge is
traversed exactly once.
\item Prove that the number of Eulerian circuits in $G$ is given by
\[d(G)\prod_{v\in V}(outdeg(v) - 1)!\]
where $d(G)$ is the number of spanning arborescences of $G$ rooted at any vertex $v$.

\end{enumerate}

\item Form a project team of 2 to 4 people and decide on a topic. Submit a list of 
partners and a project topic. Topic ideas are available on the webpage; you may choose 
another if you like, but should clear it with Amin. If you need help finding a team 
let us know. 

The final expectations for the project are $(1)$ a literature survey, $(2)$ understanding 
of chosen topic and an exposition of current state of the art $(3)$ some type of extension
e.g. coding up an algorithm, proving a lemma missing from the paper, solving an open problem
etc...
\end{enumerate}

\end{document}