\documentstyle[12pt,twoside]{article} \input{macros-course} \addtolength{\textheight}{.1in} \begin{document} \pset{8}{April 3, 1997}{April 10, 1997} {\bf Reading:} Rosen 7.1-7.4 (skip isomorphism), 7.8, 8.1 \begin{problems} \problem Answer the following questions concerning the poset consisting of the elements \{\{a\},\{b\},\{d\},\{a,b\},\{a,d\},\{b,d\},\{c,d\},\{a,c,d\},\{b,c,d\}\} under $\subseteq$. \bparts \ppart Draw the Hasse diagram for this poset. \ppart Find the maximal elements \ppart Find the minimal elements \ppart Is there a greatest element? \ppart Is there a least element? \ppart Find all upper bounds of \{\{b\},\{d\}\}. \ppart Find the least upper bound of \{\{b\},\{d\}\} if it exists. \ppart Find all lower bounds of \{\{a,c,d\},\{b,c,d\}\}. \ppart Find the greatest lower bound of \{\{a,c,d\},\{b,c,d\}\} if it exists. \eparts %GRAPHS \problem Each of the following sets of people needs to hold a meeting. Draw a conflict graph for these meetings, and schedule them into the smallest possible number of time slots without sending someone to two meetings at the same time. \begin{eqnarray*} C_1 &= &\set{\mbox{Karger},\mbox{Sussman},\mbox{Abelson}}\\ C_2 &= &\set{\mbox{Sussman},\mbox{Ward},\mbox{Minsky}}\\ C_3 &= &\set{\mbox{Karger},\mbox{Minsky},\mbox{Abelson}}\\ C_4 &= &\set{\mbox{Ward},\mbox{Minsky},\mbox{Abelson}}\\ C_5 &= &\set{\mbox{Karger},\mbox{Sussman}}\\ C_6 &= &\set{\mbox{Sussman},\mbox{Minsky},\mbox{Abelson}} \end{eqnarray*} \problem Give the adjacency matrix of the graph $W_4$. How many (simple or not) paths of length $2$, $3$ and $4$ are there between the center vertex and each other vertex? \problem Prove that any tree with a degree $k$ vertex has at least $k$ leaves. \problem What is wrong with the following ``theorem'' and ``proof?''\\ {\em False theorem:} If every vertex in a graph has degree at least one then the graph is connected.\\ {\em False proof:} We prove the result by induction on the number of vertices. Let $P(n)$ be ``if every vertex in a graph with $n$ vertices has degree at least one then the graph is connected.''\\ Base case. $P(2)$ is true since the only graph satisfying the assumption is that with two vertices and one edge between them which is easily seen to be connected.\\ Inductive step. Assume $P(n)$ is true. Now, take any graph with $n$ vertices with minimum degree at least one and add a new vertex to it. By inductive hypothesis the graph on $n$ vertices is connected. Since the new vertex satisfies the assumption it must have degree at least one, so it must have an edge connecting it to one of the remaining $n$ vertices. Thus the whole graph is connected. Hence $P(n+1)$ is true. Thus, $P(n)$ is true for all $n$. \bigskip The proof has buildup error. In the inductive step instead of considering a graph with $n+1$ vertices, a vertex is added to a pre-existing graph of $n$ vertices. It is not true however, that any $n$-subgraph of a graph with $n+1$ vertices of degree at least one, has also vertices of degree at least one. Consider for example the graph of $4$ vertices consisting of two disjoint line segments. \bigskip \end{problems} \noindent The next problems are going to prove an interesting fact about graphs that that can be colored with two colors. These graphs are called {\em bipartite} because you can divide them into two groups (colors) such that every edge has one endpoint in each group. We prove: \begin{theorem} A graph is bipartite if and only if it contains no cycles of odd length. \end{theorem} It is enough to prove this theorem for a connected graph, because then we can apply it separately to each component of an arbitrary graph. \begin{problems} \problem Prove that a graph contains an odd-length circuit if and only if it contains an odd length cycle (hint: consider the shortest odd length circuit). If a graph contains an odd-length cycle, then obviously it contains an odd-length ciruit (the cycle itself). Now suppose that the graph contains an odd-length circuit, and consider an odd-length circuit of minimum length (say $n$). If it is a cycle then we are done. Suppose, to arrive at a contradiction, that the circuit is not a cycle. Then some vertex $\bar{i}$ (other than the initial) is repeated. The circuit has the form $$ (i_1,i_2),\ldots,(i_k,\bar{i}),\ldots,(\bar{i},i_l),\ldots,(x_n,x_1) $$ Consider the circuits $(i_1,i_2),\ldots,(i_k,i_l),\ldots,(x_n,x_1)$ and $(\bar{i},i_{k+1}),\ldots,(i_{l-1},\bar{i})$. Their lengths are less than $n$, and since the sum of their lengths is odd, one of them has odd length. So we have a smaller circuit of odd length and we obtain a contradiction. \bigskip \problem Prove that if $G$ is bipartite then it contains no circuits of odd length. Let $G$ be bipartite and suppose that it has a circuit of length $2n+1$. Then (by pigeonhole) there are $n+1$ nodes of the same colour, so two of them must be adjacent. Thus we obtain a contradiction. \bigskip \problem Suppose $G$ is a connected graph with no odd cycles (or circuits). Fix a particular vertex $u$. \begin{problemparts} \problempart Prove that for any vertex $v$, the length of every path from $u$ to $v$ is odd or the length of every path from $u$ to $v$ is even. Let $p1$ and $p2$ be two paths connecting $u$ and $v$. If one has odd length and the other even, than the concatinated path is an odd cycle. This contradicts the hypothesis. \problempart Suppose I color a vertex accoring to the odd/evenness of its paths from $u$. Prove this is a legal coloring. Deduce that $G$ is bipartite. Suppose $v$ has even colour. Then there is an odd length path to each of its neighbors, so they have odd colour. \end{problemparts} \problemopt Suppose we are in a connected maze (undirected graph) and explore it according to the following rules: \begin{enumerate} \item Never traverse an edge more than once in each direction \item The first time we enter a room, mark our entering edge. Do not use the entering edge to exit a room unless it is the only remaining choice under the first rule. \end{enumerate} Prove that we get stuck (can't apply either rule) only at our starting point, and that by then every edge has been traversed in both directions. \bigskip First we show that we can only get stuck at the origin. For any vertex $i$, let $index(i)$ denote the sum of incomming edges minus the sum of outgoing edges. We claim the following invariants. For any node $i$ that is not the starting point, $$ index(i) = \{ \begin{array}{cc} +1 & \mbox{after entering } i \\ 0 & \mbox{after leaving } i\end{array} $$ while for the starting point $o$ we have $$ index(o) = \{ \begin{array}{cc} 0 & \mbox{after entering } i \\ -1 & \mbox{after leaving } i\end{array} $$ These invariants are easily proved by induction on the number of visits to the node. The base cases (0 visits) is obvious. Now suppose the claim holds for $n$ visits. On the $n+1$th visit to node $i$, I decrement it's index by 1. By the inductive hypothesis it was 0, so now it becomes -1. This implies that there is an exit available (otherwise the index would be 0,or 1), so I exit and the index becomes 0 again. The proof for the origin is similar. We can only get stuck in a node only if all edges of this node have been traverced in both directions or if there are only outgoing edges, i.e if the index is $0$ or $-1$ after entering. But the only node with this property is the starting point. Now we prove that when we're stuck, each edge has been traversed twice. Suppose, to obtain a contradiction, that $(i,j)$ is an edge that has not been traversed in both directions. Then node $i$ must also have a free incomming edge (because it's index is $0$). We can assume without loss of generality that this edge is marked (becasue the marked edge is the last one to be used as an exit). Since a marked edge indicates a first visit, and we started at $o$, there is a path of incomming edges from $i$ to $o$. So $o$ has an outgoing edge, which contradict either the fact that it's index is 0, or the assumption that we are stuck. \end{problems} \end{document} % Local Variables: % mode: latex % TeX-master: t % End: