## 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!).
```