Math 510: Introduction to Graph Theory
Spring 2006

The course is for students in the second year and higher; it is not an introductory graduate course. The absolute minimum requirement is a good understanding of abstraction and a solid modern algebra background (as from a graduate course), and the more graduate math you know, the better (that's the famous "mathematical maturity"). If you aren't sure whether you might be interested or ready for this class, please see me.

We will use the textbook Graph Theory by Reinhard Diestel, third edition (new in 2005; I recommend against using an earlier edition). The text can be read on line. We will cover as many chapters as we can, which is probably about six. Here is a link to the table of contents. Here is a link to Diestel's list of errata. Here is the link to my list of errata (below, on this page).

I will expect you, the students, to study the material and to work on as many of the exercises as you can. I will meet separately with each student frequently (every week, I hope) to discuss your progress and any questions you or I may have. I will frequently collect written work: see the homework assignments below. I will accept a second version of any problem, if you want to rewrite it for a better grade (or any other reason), but only within a reasonable time (let's say, about two weeks from when I returned the first version).

We meet on MWF 2:20 - 3:20 in LN-2205.

Special class times:

Student presentations: Mondays starting 2/27, at 5:00 or 5:10, in LN-2201.

When	Who; what
2/27, 5:10	Brett: conclusion of tree and forest packing and covering
3/6, 5:05	Keith: path covers of digraphs
3/20, 5:05	Justin: structure of factor-critical graphs
3/27, 5:05	Garry: the Rado graph
4/3, 5:05	Tim: random graphs and a Ramsey number
4/10, 5:05	Jackie: list 5-coloring
4/24, 5:05	Qing: König's edge coloring theorem
5/8, 5:10 (postponed from 5/1)	Lucas: tutte invariants

There is a Combinatorics Seminar that meets usually on Thursdays at 1:15 in LN-2201, but occasionally at a different time; check the schedule. All 510 students are invited to attend (if the room is big enough for 510 students).

Class Schedule

All exercises are numbered as in the printed third edition of Diestel's book.

Additional Exercises

• Chapter 1

1. H(G) is the oriented incidence matrix. Prove: Lemma. In H(G), every minor has determinant equal to 0 or +1 or −1.
2. Prove: Theorem. The rank of H(G) equals n − c, where n = |V| and c is the number of components of G.
3. Let B be the unoriented incidence matrix. Prove: Theorem. Over a field F, the rank of B is equal to n − c if F has characteristic 2, and n − b if the characteristic is not 2, where b = the number of bipartite components of G. (N.B. This is properly viewed as a special case of the oriented incidence matrix generalized to signed graphs.)
4. If successful with #24, a research question is to generalize to signed graphs. The generalization should include Mader's Theorem 1.4.3 if possible.

• Chapter 2

With regard to the circuit packing theorem 2.3.2, here are two questions that seem interesting.
1. The bound f(k) given in the theorem is unlikely to be best possible. Let F(k) be the best possible bound. We know F ≤ f. Can you prove anything more about F? For instance, is F(k) ≤ 3k (log k + log log k + 4) or 4k (log k + log log k + 3) (just as indications of what one could ask)? On the other side, prove F(k) ≥ k. Is F(k) ≥ 2k? ck for some c > 1? I'm confident that this question has some results in the literature but is far from solved. Any work you do on any of these questions would make a fine homework problem.
2. The case k = 2 is quite interesting. F(2) is the smallest number of vertices that cover all circuits in every graph that has no two vertex-disjoint circuits. Our f(2) = 41, so F(2) ≤ 41, but the true value is certainly much smaller. What is that true value, or how close can you get to it? You might try doing it directly (I'd be happy with that as a homework exercise), or you might look up Lovász's theorem (see Bollobás, Extremal Graph Theory) to deduce the true value from it.
3. Does every cubic graph with exactly one isthmus have a perfect matching? (Thanks to Justin Almeida.)

4. Prove that the book's definition of a stable marriage is almost impossible to satisfy, directly contrary to the theorem claimed in the book.

• Chapter 3

1. The second proof of Menger's theorem does not prove the following statement:
   • If in a graph G, we have a set P of fewer than κ(A,B) disjoint A-B paths, then there is a set Q of |P| + 1 disjoint A-B paths such that V(Q) contains V(P).
   Question. Is this statement true? Can you prove it or find a counterexample?
2. Prove the following theorem, which is a perhaps more primitive version of Whitney's theorem 3.3.6(i). Theorem. If G is not complete, then the connectivity κ(G) = min{κ_G(x,y) : x, y nonadjacent vertices in G}.

• Chapter 4

1. Prove that G is planar iff there is a simple basis of the cycle space that consists of circuits.
2. Let G be 2-connected. I claim that, for any simple basis of the cycle space that consists of circuits, the sum of the basis is a circuit and these circuits (the basis together with its sum) are the face boundaries in some planar embedding of G. Prove or disprove.
3. Show how to identify the circuits and bonds among all the members of the binary cycle and cocycle spaces of a graph.
4. Suppose H and H' are abstract duals of a graph G. Show that H and H' are 2-isomorphic, i.e., related by a sequence of Whitney 2-operations. (Whitney's 2-isomorphism theorem.)

• Chapter 5

1. Prove that every planar graph with girth at least 4 is 4-colorable (Simplified Grötzsch's Theorem).
2. Can you find a way to prove Grötzsch's Theorem by combining the ideas of the preceding problem and of the 5-Color Theorem (the proof in the book)?
3. Suppose G is the union of G' and G'' that have in common just a single vertex. Show that the chromatic function satisfies
   χ_G(k) = χ_G'(k) χ_G''(k) / k.
4. Prove the Great Big Lemma: The chromatic function (a.k.a. polynomial) satisifies
   χ_G(k) = χ_G-e(k) − χ_G/e(k) for k = 1,2,3,....
   
   (G is a multigraph and contraction is not simplified.)
5. Use the Great Big Lemma to prove the Great Big Theorem:
   1. (G.D. Birkhoff, 1912, for planar graphs; Whitney, 1930s, for all graphs) χ_G(k) is a polynomial function of k = 1,2,3,.... Furthermore, it is monic of degree n = |V|, its coefficients are integers alternating in sign (i.e., the coefficient of k^n-i has sign (−1)ⁱ), and the coefficient of k^n-1 is −|E| (for a simple graph). Exception: if G has a loop, then χ_G(k) = 0.
   2. (R.P. Stanley, 1973) The number of proper pairs (c,α) of a k-coloring c and an acyclic orientation α equals χ_G(k), for k = 1,2,3,....
   3. (R.P. Stanley, 1973) The number of compatible pairs (c,α) of a k-coloring c and an acyclic orientation α equals (−1)ⁿ χ_G(−k), for k = 1,2,3,....
   4. (R.P. Stanley, 1973) The number of acyclic orientations of G equals (−1)ⁿ χ_G(−1).
   Hint: To prove (b, c), use induction on |E| in combination with Lemmas 5.A and 5.B.
   • Lemma 5.A: The number p_G(k) of proper pairs of a k-coloring and an acyclic orientation satisfies
     p_G(k) = p_G-e(k) − p_G/e(k) for k = 1,2,3,....
   • Lemma 5.B: The number q_G(k) of compatible pairs of a k-coloring and an acyclic orientation satisfies
     q_G(k) = q_G-e(k) + q_G/e(k) for k = 1,2,3,....
6. Prove Lemma S1. The chromatic polynomial of a signed graph Σ is not changed by switching.
Warning: The following two problems depend on studying basic signed graph theory first.
7. (a)   Prove Theorem S2. The chromatic polynomial χ_Σ(2k+1) and the zero-free chromatic polynomial χ_Σ*(2k) satisfy the deletion-contraction formula
     c_Σ = c_Σ-e - c_Σ/e,
   where c denotes χ(2k+1) or χ*(2k) and e is any edge with one kind of exception.
   (b)   Deduce that these so-called "polynomials" really are polynomial functions of their arguments and can therefore be extended to all real or complex-number arguments.
8. Prove Theorem S3. χ_Σ(−1) equals a(Σ), the number of acyclic orientations of Σ. Hint: A useful lemma would be that a(Σ) satisfies the deletion-contraction recurrence.

• Chapter 6

1. Prove Lemma. If f is a nowhere-zero k-flow on a graph G, then f restricted to any block G' is a nowhere-zero k-flow on G'.
2. Prove by analyzing the augmentation values ε of augmenting paths that a network with real capacities has a maximum flow, i.e., the supremum of values of flows is attained by a flow.

• Chapter 12

1. Prove Lemma. Let M be a minor-closed class of finite graphs, G \ M its complement, and F = Min(G \ M). Then a graph G is in M if and only if G has a minor that belongs to F.
2. Show that tw(Cⁿ) = 2. Deduce that tw(G) > 1 if G is not a forest.
3. Show that tw(Kⁿ) = n - 1.
4. Show that tw(Kⁿ \ e) = n - 2.
5. This question has three parts. The answer to (b) should be such that it makes (c) true.
   • Here G is a tree. Take for T any spanning tree of the line graph L(G) and for V_t the vertex set of the G-edge t. Prove this is a tree decomposition of G.
   • Define a minimal tree decomposition (Exercise 12.13 might or might not be helpful here) of any graph G.
   • Prove that every minimal tree decomposition of a tree G is obtained as in part (a).

Supplementary Mathematics

• The oriented incidence matrix is the V × E matrix H(G) in which the column corresponding to edge e has one +1 and one −1 in the rows corresponding to the endpoints of e, with 0's elsewhere. (We rarely have to worry about the choice of which endpoint gets which sign; we can just make an arbitrary choice and stick to it.) This definition works for multigraphs without loops. The matrix defined in the book, with only +1's, is the unoriented incidence matrix.
• An algebraic cycle of G over F (where F is a field) is an element of the cycle space of G over F, which is defined to be the null space Nul H(G) (also called Z₁(G; F), especially in algebraic topology). An (algebraic) cocycle is an element of the cocycle space, which is defined to be the orthogonal complement of the cycle space, i.e., it is the row space Row H(G). A binary cycle or cocycle is an algebraic cycle with F = F₂, or equivalently the corresponding subset of E. In this connection I like to use the term circuit for a (nonempty) connected edge set with all degrees equal to 0 or 2 (this is what the book would call a "cycle").
• A signed graph is a graph whose edges are labelled positive or negative. Thus, it is Σ = (G, σ) where σ: E -> {+,−}.
  • A subgraph is balanced if every circuit in it is positive. If all the signs are negative, a balanced subgraph is a bipartite subgraph. If all signs are positive, a balanced subgraph is any subgraph.
  • Switching a vertex set X in a signed graph means reversing the sign of every edge that has one endpoint in X and the other in V \ X. Switching X is equivalent to switching each vertex in X separately (in any order).
  • Coloring a signed graph is done with signed colors. For a signed k-coloring, the color set is C_k = {0, ±1, ±2, ..., ±k}. For a zero-free k-coloring, the color set is C_k \ {0}. A coloring γ is proper if, for each edge e_vw, we have
    γ(v) ≠ σ(e_vw)γ(w). The chromatic polynomial χ_Σ(2k+1) is defined, for k = 1, 2, ..., to be the number of proper signed k-colorings. The number that are zero-free, written χ_Σ*(2k), gives the zero-free chromatic polynomial.
• The "parts" of a tree decomposition: I prefer a more distinctive name: nodal set for V_t and "nodal subgraph" for G[V_t]. (I use the term "node" for a vertex of T. Generally, "node" is a synonym for "vertex" but not used much any more.)

Errata for Diestel, 3d Edition

• Page 38: The definition of stable marriage is incorrect and so are the statement and proof of the Gale-Shapley Theorem. I believe the correct definition is: a matching in which there are no two edges ab and a'b' such that a prefers b' to b and b' prefers a to a'. (You can look this up if you like; there's a book.)
• Section 6.2: The so-called MFMC Theorem is actually (when combined with the corollary) the Integral MFMC Theorem, not the usual MFMC Theorem.
• Chapter 6: The terminology "k-flow" for nowhere-zero k-flow is completely nonstandard. You should always say "nowhere-zero", even though it's slightly longer.
• Chapter 12: The term "(graph) minor theorem" should be "(graph) minors theorem".

To my home page.