Math 452/852 Assignments

Usually assignments will be made each day, to be due the following Wednesday.
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 Kn 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 
                      |VG| - |EG| + r = 2 - 2d, where r is the number
                      of regions of G embedded into Sd when d is the genus of G.
                   4. If G1, ... , Gk are the components of a graph G,
                      then the genus of G is at most the sum of the genuses of the graphs
                      G1, ... , Gk.
                   5. If e is a bridge in a connected graph G, and H1 and H2
                      are the compnents of G - e, prove that the genus of the graph G is at most
                      the sum of the genuses of H1 and H2.
                   6. If G1 is homeomorphic to H1 and G2 is homeomorphic 
                      to H2, is it True or False that G1 x G2
                      is homeomorphic to H1 x H2? 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!).