Due date Assignment Fri Jan 21 p. 9: #3, 13. p. 10: #15, 29, 30. p. 14: #1, 2, 4. Wed Jan 26 p. 20: #1, 7, 8. p. 21: #15. Also: How many partially directed graphs are there having the same underlying graph G? (You may assume that G is simple.) Wed Feb 2 p. 29: #11; 12 (justify your answer); 18; 26, 27 (for these two, indicate how you got your answer); 31. Wed Feb 9 p. 37: #1.5.1, 1.5.3(ab), 1.5.7(abc: indicate how you get your answer), 1.5.27, 1.5.34, 1.5.36, 1.5.39. Also: Find a minimum cost spanning tree for the underlying weighted graph shown in Fig. 1.6.1 on p. 40. Wed Feb 16 p. 53: 4, 11, 15 p. 59: 3, 6 Wed Feb 23 First Problem: Let n > 0 and t > 0 be integers. Let v be a vertex in the complete simple (Extended graph K_n on n vertices, let C(t) be the number of v-v walks of length t to Feb 25) in K_n, and let A(t) be the number of all walks of length t starting at v. (a) Determine A(t) and C(1). (b) Show that C(t) = A(t - 1) - C(t - 1). (c) Show C(t) = -(-1)A(t - 1) - (-1)2A(t - 2) - ... - (-1)kA(t - k) - ... - (-1)t-1A(1) for t > 2. (d) Show that xn + ... + x = (xn+1 - x)/(x - 1). (e) Mimic (d) to get a nice formula for C(t) from (c); does your formula work for each t > 0? Also: p. 66: 2.3.1, 2.3.19, 2.3.21 (careful; this is the first edition), 2.3.25, 2.3.28 p. 72: 2.4.3 Wed Mar 1 p. 79: 2.5.1 (just I_G and A_G), 2.5.8, 2.5.12. p. 90: 3, 4, 10, 14, 15. Wed Mar 8 p. 243: 4, 5. p. 250: 1, 9. Wed Mar 22 1. Let R1 and R2 be equivalence relations on a set A. Regarding R1 and R2 as subsets of AxA, show that the intersection of R1 and R2 is also an equivalence relation. 2. Let S be the subset of the plane (RxR, where R is the set of real numbers) consisting of all ordered pairs (x,y) where either x and y are both integers or x = y. Show that S is an equivalence relation. 3. Formulate and prove a result about the chromatic number of a graph, generalizing the fact that the chromatic number of G is 2 or less if and only if there is a linear graph mapping from G to P_2. Wed Mar 29 Exam 2, on Ch 2, Ch 3.1, Ch 7.1-7.2. Wed Apr 5 1. Give a nonplanar graph G with an embedding of G into S_1 (the doughnut). Justify why G is nonplanar, and show the embedding into S_1. 2. Give a counterexample to Theorem 9.1.1 in the book (the book's version of this result is slightly misstated; hint: compare it with the version done in class.) Explain where the book's "proof" goes awry. 3. Also do: Problems 9.1.7, 9.1.8, 9.1.15 and 9.1.22. Wed Apr 12 1. For n >= 3, prove that the genus of K_{n}is greater than or equal to the least integer greater than or equal to (n - 3)(n - 4)/12. 2. For each integer n >= 0, prove that there is a graph G whose genus is n. Hint: Use one of Ringel's theorems. 3. Let G be a connected graph. Prove that the genus of G is at most half the cycle rank of G. Do this by using the fact that |V_{G}| - |E_{G}| + r = 2 - 2d, where r is the number of regions of G embedded into S_{d}when d is the genus of G. 4. If G_{1}, ... , G_{k}are the components of a graph G, then the genus of G is at most the sum of the genuses of the graphs G_{1}, ... , G_{k}. 5. If e is a bridge in a connected graph G, and H_{1}and H_{2}are the compnents of G - e, prove that the genus of the graph G is at most the sum of the genuses of H_{1}and H_{2}. 6. If G_{1}is homeomorphic to H_{1}and G_{2}is homeomorphic to H_{2}, is it True or False that G_{1}x G_{2}is homeomorphic to H_{1}x H_{2}? Justify your answer. Wed Apr 19 1. Prove or disprove: the independence number of the complement of a simple graph equals its clique number. 2. The chromatic number of a simple graph is at least as big as the independence number of its complement. 3. Problem 10.1.3 in the book. 4. Problem 10.1.6 in the book. 5. Problem 10.1.9 in the book. Fri Apr 21 In class exam 3. Remember, I will replace the lowest of your 3 exam scores by your homework average (but only if it helps!).