\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 Solutions} \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. {\bf Solution:} Consider $2 |E| = \sum_{e \in E} 2$ and note that this is another way of summing vertex degrees. Each term (edge) increments the degree of $2$ vertices. Since each edge is enumerated each vertex has its degree counted. Thus $\frac{1}{|E|} \sum_{v_i\in V} d(v_i) = 2$. Since $2 |E| = \sum_{v_i\in V} d(v_i)$ is even any number of odd terms in the degree sum has to be even. Thus the number of odd degree vertices in $G$ 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. {\bf Solution:} The following is for a connected bipartite graph. The extension is trivial after the statement holds for each connected component. $``\Rightarrow"$ Assume $G(A,B,E)$ is bipartite and pick a cycle $v_1,v_2,\dots,v_k,v_1$ with $v_1 \in A$. Then $v_i \in A$ for $i$ odd and in $v_i \in B$ for $i$ even for a bipartite $G$. An odd cycle has and odd number of vertices, thus $k$ is odd with $v_k \in A$. But then $(v_k,v_1) \in E$ which contradicts the fact that $G$ is bipartite. Therefore a bipartite $G$ has no odd cycles. $``\Leftarrow"$ Let $G$ be a graph with no odd cycles. Define $d(u,v)$ as the shortest distance between the two vertices. Pick an arbitrary vertex $u \in V$ and define $A = \{u\} \cup \{ w \;|\; d(u,w) \mbox{ is even}\}$. Note that $(A,B)$ is a partition of $V$. Notice that an edge with both endpoints in $A$ (or $B$) would create an odd cycle by joining two paths of equal length originating from vertex $u$. By assumption we have no odd cycles and we conclude that $G$ is bipartite with partition $(A,B)$ defined above. \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|$. {\bf Solution:} The number of edges leaving $A$ is computed as $k |A|$. The number of edges leaving $B$ is computed as $k |B|$. Both quantities have to equal the total number of edges. Thus $|E| = k |A| = k |B|$ implying that $|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$. {\bf Solution:} Let $d(v)$ be the degree of vertex $v$ in $G$. The total number of edges one can place incident to $v$ is $n-1$. The complement of $G$ has all except for the ones in $G$. Thus the degree of $v$ in the complement $\bar{G}$ is $n - 1 - d(v)$. \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})$. {\bf Solution:} Let $\phi \in Aut(G)$. Note that $(u,v) \in E \Leftrightarrow (\phi(u), \phi(v)) \in E$ is equivalent to $(u,v) \notin E \Leftrightarrow (\phi(u), \phi(v)) \notin E$ by applying the converse to each direction. By definition of the complement edge set $\bar{E}$ we have $(u,v) \in \bar{E} \Leftrightarrow (\phi(u), \phi(v)) \in \bar{E}$. Thus $\phi \in Aut(\bar{G})$. The other direction is identical. \item Prove that at least one of $G$ and $\bar G$ is connected. {\bf Solution:} Let $G$ be disconnected and write it as $G_1, G_2, \dots, G_k$. Pick any distinct vertices $u$ and $v$. If there is no edge $(u,v)$ in $G$ then they are connected by one in the complement $\bar{G}$. If edge $(u,v)$ is in $G$, pick any other vertex $w$ with no path to $(u,v)$ in $G$ (must exist or $G$ would be connected). Then $u$ and $v$ are connected as $u,w,v$ in $\bar{G}$. Since $u$ and $v$ were picked arbitrarily $\bar{G}$ is connected. With this fact the other direction follows trivially. \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$. {\bf Solution:} Given an $r \times q$ matrix $C$ and an $q \times r$ matrix $D$, the Cauchy-Binet formula states that $det(CD) = \sum_S det(C_S) det(D_S)$ where $S$ spans all possible subsets of $\{1,2,\dots,q\}$ of size $r$ (proof can be found on wikipedia). First note that $M_{ii} = B_i B^T_i$ where $B_i = B\backslash\{i^{th} \mbox{ row}\}$. Then apply the Cauchy-Binet formula with $r = n - 1$ and $q = m$ and $C = B_i$ and $D = B^T_i$. \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. {\bf Solution:} Given $N$ consider the graph (edges) corresponding to it $G_N$. Note that an isolated vertex in $G_N$ indicates a cycle since $n-1$ edges form a cycle on less than $n$ vertices. Pick the cycle and index its vertices with set $I = \{i_1, i_2, \dots, i_k\}$. Define a $n-1$ vector $c$ with ones indexed by $I$ and zeros elsewhere. Notice that $Nc = 0$ since it is the sum of the columns of $N$ corresponding to edges in the cycle. Since $k > 0$ the columns of $N$ are linearly dependent and thus $det(N) = 0$ (note: the removed row does not spoil this fact even if a cycle vertex corresponds to the removed row). If no cycle exists create a sequence $i_1, i_2, \dots, i_{n-1}$ as follows. Remove and edge $e_1$ with a leaf vertex $i_1$. Then edge $e_2$ with leaf $i_2$ etc... After each removal we still have a tree but with one less vertex. Now construct a permutation matrix $P$ to rearrange the rows and columns of $N$ in the same order as they were removed (vertex $i_j$ to row $j$ and edge $e_{j}$ to column $j$). Note that $PNP$ is lower triangular since $i_j \notin e_k$ for $j < k$ (otherwise $i_j$ would not be a leaf at $j^{th}$ removal step). Furthermore all entries on diagonal are $\pm 1$ and $det(N) = det(PNP) = \pm 1$. \item Show that for the complete graph on $n$ vertices $K_n$, \[\det M_{ii} = n^{n-2}.\] Conclude that this implies Cayley theorem. {\bf Solution:} Since $det(M_{ii})$ is the number of spanning trees the total number of trees on $n$ vertices will be given by the complete graph $K_n$ since any possible set of edges may be selected. Consider the diagonal entry of $M_{ii}$. A diagonal entry is the degree of vertex $j$ which is $n-1$ for a complete graph. An off-diagonal entry is a dot product between rows corresponding to distinct vertices. Since we have a complete graph, we have an edge between them, and the dot product is $-1 \cdot 1 = -1$. We can then write $M_{ii}$ in form $n I - ee^T$ where $e$ is a vector of all ones. The determinant can be computed using the matrix determinant lemma as \[det(M_{ii}) = (1 - \frac{e^T I e}{n}) det(n I) = (1 - \frac{n-1}{n}) n^{n-1} = n^{n-2}.\] \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. {\bf Solution:} Do this by induction on dimension $n$. The base case pictured has the Hamiltonian cycle $00, 01, 11, 10$. We assume there exist one for an $n$ dimensional cube (IH). To show for $n+1$, fix the first bit at $0$. Use (IH) on the last $n$ bits to construct a walk using the Hamiltonian cycle without taking the last step. We are now at vertex $0 i_1 i_2 \dots i_n$. Take a step to $1 i_1 i_2 \dots i_n$ switching the first bit. Recreate the walk from before in reverse order. We now find the walk in the same configuration as when we started with the exception of the first bit which is $1$. Take the last step switching the first bit to $0$. We are back where we started visiting each vertex exactly once and constructing a Hamiltonian cycle in an $n+1$-dimensional cube. \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$. {\bf Solution:} The graph is connected and balanced. Thus from any vertex $u$ you can get to $v$ by using depth first search. You will never get stuck at any other vertex $w$ since for each entering edge, there is one that is leaving. We use can use these paths to construct $T$. \item Prove that when the above algorithm stops every edge is traversed exactly once. {\bf Solution:} Assume that the algorithm terminated. This means that all edges of the starting vertex $v$ have been traversed (using the fact that there is the same number leaving as entering). Assume there is an untraversed edge $e$ starting at a visited vertex $u$ (if $u$ does not exist the graph is disconnected). We can then trace a path (or cycle) containing $e$ such that the endpoints (endpoint) are vertices at which the algorithm traversed an edge in $T$. This forms a contradiction as the graph is balances and the tree edge is always selected last. \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$. {\bf Solution:} At each algorithm step at vertex $u$ there are $outdeg(u) - 1$ choices of an edge to take. There are also $outdeg(v)$ choices to start the traversal. Thus the number of possible traversals starting from $v$ with some fixed in-tree $T$ is computed as, \[outdeg(v)! \prod_{u \neq v} (outdeg(u) - 1)! \] Notice that regardless of the edge we chose to start we trace the same Eulerian circuit for every fixed in-tree $T$. Thus we divide the above by $outdeg(v)$ to get \[ \prod_{v \in V} (outdeg(v) - 1)! \] Furthermore, since the number of circuits in the graph must be same no matter where we start, we conclude that their number is given by, \[ d_{in}(G) \prod_{v \in V} (outdeg(v) - 1)! \] where $d_{in}(G)$ is the number of in-trees at any vertex. Since the algorithm and the proof can be repeated identically by using an out-tree (or arborescence) and traversing edges against their direction, we see that this is equivalent to, \[ d(G) \prod_{v \in V} (outdeg(v) - 1)! \] where $d(G)$ is the number of arborescences rooted at any vertex. \end{enumerate} \end{enumerate} \end{document}