Math 581: Topics in Graph Theory
Introduction to Graph Theory
Spring 2003

To the extent there is a special emphasis, it is on the structure of graphs, in particular contributions of Tutte, arguably the greatest graph theorist of the last century. (A short biography from Tutte's home university. The New York Times obituary.)

The course is not normally suitable for first-year graduate students. However, there are no specific prerequisites except the traditional ``mathematical maturity''. Basic graduate algebra is very helpful.

Course time and place:

PLACE: LN-2205
TIME:

Office hours:

My regular office hours, which are mainly for the undergraduates, are

The Seminar

All students are encouraged to attend the Combinatorics and Number Theory Seminar, usually on Mondays, 3:30 - 4:30. There will be talks you can't understand, as well as some you can't help understanding, on all kinds of topics in graph theory and other combinatorics as well as in number theory (and sometimes both at once). (You'll be surprised how much you learn by not understanding a great many talks.)

Course Procedure

I will lecture, for the most part.

Student work: You will have to work hard sometimes to understand the lectures and readings. Keep your colored pencils handy. I will find some way to give you a grade; I expect it will be based on a combination of handed-in problems and (later) student presentations. I will also (eventually!) meet with each of you individually on a regular basis.

I expect you to try all the exercises at the end of the chapters. You don't have to solve all of them! I will collect your written solutions to some or all of the following assignments, some from Tutte and some from the additional problems below. The list of hand-in problems is not compulsory but you should turn in as many as you can.

Syllabus and Assignments

The syllabus is tentative and partial. It will get filled out and corrected as the course progresses.

• Chapter 1: Graphs and Subgraphs.
  • Description: Basics.
  • Hand in ## 1-3.
• Chapter 2: Contractions and the Theorem of Menger.
  • Description: More basics; and famous theorems.
  • Hand in ## 2, 3, 4, 6, 7.
  • # 7. Prove König's theorem directly from Menger's theorem (Theorem II.35).
    König's Theorem. Let G be a bipartite graph with bipartition (U, V). The largest size of a matching (i.e., partial 1-factor) equals the smallest size of a vertex cover (a set X of vertices such that every edge has at least one endpoint in X).
• Chapter 3: 2-Connection.
  • Description: Basic structure theory.
  • Hand in ## 1 - 4.
  • # 4. Prove the following `vertex' version of Theorem III.7.
    Theorem III.7v. Let G be an inseparable graph and let U, V be nonnull vertex sets in G. Then mu_G(U,V) >= 2 with these exceptions: when U = V and |U| = 1, or when G = K₂ (or just possibly one or two other exceptional cases that I missed).
• Chapter 4: 3-Connection.
  • Description: Higher structure theory.
  • Hand in ## 2, 3(i), 5, 6.
• Chapter 6: Digraphs and Paths. (Sections 1-4 only.)
  • Description: Arborescences with trees and Euler tours.
  • Supplement to Theorems 14 and 21: A stronger result is true.
    Theorem VII.14/21'. For a digraph Gamma, the following statements are equivalent.
    (i) Gamma has an Eulerian tour.
    (ii) Gamma is strongly connected and Eulerian.
    (iii) Gamma is graph-connected and Eulerian.
    The equivalence of (iii) with the others was proved in class.

    Hand in ## 1, 4, 6 (optional).

    # 6. See if you can figure out det K_i,j(Gamma, c). (The problem is the sign.)
• Chapter 8: Algebraic Duality. (Omit Section 9.)
  • Description: Algebraic approach to graph structure.
  • Hand in ## 3, 4, 6-10. (Don't do # 5; we haven't covered the relevant material in Chapter 6.)
  • # 7. (Corrected.) (a) Prove the following partial converse of Theorem VIII.20 for a primitive chain-group N.
    Theorem VIII.20'. If D is a cell-base of N, then:
    D - U is a cell-base of N × T if and only if
    D - T is a cell-base of N · U.
    
    (b) Is the theorem true for arbitrary chain-groups?
  • # 8. Here are more examples than you really need to do. In each of them, R is a particular ring, S = {1,2,...,6}, and N means a chain-group from S to R. (Thus any chain is an element f of R^S.) Each problem has two parts, (a) and (b). There are 8 problems, by combining chain-group (1) or (2) with a choice of ring. You should work with at least two of the rings, doing parts (a) and (b).
    The parts are
    1. Find the elementary and primitive chains and the cell-bases.
    2. Find the dual chain group N* and its elementary and primitive chains and its cell-bases.
    
    The chain-groups are:
    1. N_R , the chain group generated by all chains in which exactly four entries are nonzero.
    2. N'_R , the chain group generated by all chains in which exactly four entries are nonzero and the sum of the entries is 0.
    
    The rings are:
    1. R = Z (the integers, called I by Tutte).
    2. R = Z₂ (the integers modulo 2).
    3. R = Z₃ .
    4. R = Z₄ .
  • # 9. Let Omega be an orientation of the graph G and let N be the chain-group from the dart set E(Omega) to R that is generated by the rows of the incidence matrix M(Omega) defined in class. Show that the cycle group Z₁(Omega; R) (which Tutte calls Gamma(Omega, R)) is N*.
  • # 10. Let Omega be an orientation of the graph G. Show that the coboundary group B¹(Omega; R) (which Tutte calls Delta(Omega, R)) equals the chain-group N of the preceding problem.
  • # 11. N being any primitive chain group on any set S, prove the following properties. (They are basic properties of a matroid.) I recommend that you do at least one of the parts; it is not necessary to do all.
    1. Properties (i) and (ii) in Section VIII.11.
    2. Let Q_I be the class of subsets of S that do not contain the support of any primitive chain. Prove:
       1. The null set is in Q_I .
       2. If J is in Q_I and I is a subset of J, then I is in Q_I .
       3. If I and J are in Q_I and |I| < |J|, then there is x in J-I such that (I union x) is in Q_I .
    3. Let Q_B be the class of maximal members of Q_I . Prove:
       1. Q_I is nonempty.
       2. If A and B are in Q_B and x is in A, then there is y in B such that [(A-x) union y] is in Q_B .
    4. Prove that Q_B is the class of complements of cell-bases of N.
  • # 12. Suppose we have a chain-group N on S, and
    S contains T₁ contains T₂ contains ... contains T_k .
    Consider a sequence of reductions and contractions,
    N' = N * T₁ * T₂ * ... * T_k ,
    where each * stands (independently) for · or × . We know that N' can be expressed in the form
    N' = (N × T) · U .
    Problem: find formulas for T and U in terms of the T_i 's.

    # 13. Find a chain-group N over Z₄ with

    1. a non-primitive cell-base;
    2. a cell-base D and cell x in D such that, if g is any chain for which (D intersect Sp(g)) = {x}, then g(x) does not equal 1 .

    # 14. (Supplement to Theorem VIII.14.) Suppose you have a primitive cell-base D and cells x in D and y not in D. Let

    D₁ = D - {x} union {y} .
    Prove that D₁ is a cell-base if and only if y is in Sp g(D,x) .

    # 15. (Supplement to Theorem VIII.7.) N is a chain-group. Is it always true that (N × T)* = N* · T ? If not, can you specify the chain-groups N for which it is true? (It is perfectly reasonable to come up with only a partial answer, such as a necessary condition or a sufficient condition.)

    # 16. Suppose a coboundary delta(g) takes on exactly two values, a and b in R. Prove that delta(g) can be written in the form

    a 1_V + (b-a) Sum_i=1,...,k q_Bi
    for bonds B₁, ..., B_k. Here 1_V denotes the 0-cochain that is identically 1.

To my home page.