Introduction to Graph Theory

Spring 2003

This course is an introduction to fundamental concepts of graph theory. We study the book

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.

PLACE: LN-2205

TIME:

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

I will be happy to see you at these or other times as far as possible. If necessary we can make appointments.

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

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.

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_{2}(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- Find the elementary and primitive chains and the cell-bases.
- Find the dual chain group N* and its elementary and primitive chains and its cell-bases.

The chain-groups are:- N
_{R}, the chain group generated by all chains in which exactly four entries are nonzero. - 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:- R = Z (the integers, called I by Tutte).
- R = Z
_{2}(the integers modulo 2). - R = Z
_{3}. - R = Z
_{4}.

- # 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
_{1}(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
^{1}(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.
- Properties (i) and (ii) in Section VIII.11.
- Let Q
_{I}be the class of subsets of S that do not contain the support of any primitive chain. Prove:- The null set is in Q
_{I}. - If J is in Q
_{I}and I is a subset of J, then I is in Q_{I}. - 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}.

- The null set is in Q
- Let Q
_{B}be the class of maximal members of Q_{I}. Prove:- Q
_{I}is nonempty. - 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}.

- Q
- 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
_{1}contains T_{2}contains ... contains T_{k}.

Consider a sequence of reductions and contractions,- N' = N * T
_{1}* T_{2}* ... * 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
_{4}with- a non-primitive cell-base;
- 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
_{1}= D - {x} union {y} .

Prove that D_{1}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_{1}, ..., B_{k}. Here 1_{V}denotes the 0-cochain that is identically 1. - S contains T

To my home page.