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

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