# Math 510: Introduction to Graph TheorySpring 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.

 Week of Topic Reading sections Problems to work on Problems to hand in 1/23 - 1/27 Basic concepts:  Graphs and multigraphs;  Degree;  Standard examples 1.1 - 1.4, 1.10 Ch. 1 (as many as you can) 1/30 - 2/3 Basic concepts:  Connectivity;  Trees;  Biparticity;  Minors;  Eulerian tours 1.4 - 1.8 (ditto) I. Due 2/1: Ch. 1 ## 3, 4, 16 2/6 - 2/10 Basic concepts:  Cycle and cocycle spaces;  Matching 1.9 - 1.10, 2.1 Ch. 1, 2 (as many as you can; low numbers in Ch. 2) II. Due 2/15: Ch. 1 ## 15, 20, 24, 27, 31, 35(optional) 2/13 - 2/17 Matching 2.1 - 2.2 Ch. 2 (as many as you can) 2/20 - 2/24 Packing;Connectivity 2.2 - 2.4, 3.1 Ch. 2 (as many as you can) 2/27 - 3/3 Connectivity:  Menger's theorem,  Structure 3.1 - 3.3 Ch. 3 (as many as you can) III. Due 2/27: Ch. 2 ## 1, 2, 5, 11, 12, 14 3/6 - 3/10 Connectivity:  Menger's theoremPlanarity 3.3, 3.5, 4.1 - 4.2 Ch. 3, 4 (as many as you can) 3/20 - 3/24 Bridges of a  subgraph; Planarity:  Equivalent embeddings,  Kuratowski's theorem 4.3 - 4.4 Ch. 4 (as many as you can) 3/27 - 3/31 Planarity:  Kuratowski's theorem,  MacLane's criterion; Projective planarity of signed graphs; Duality 4.4 - 4.6;Lecture Ch. 4 (as many as you can) 4/3 - 4/7 Coloring:  Chromatic polynomial  Chromatic number  Chromatic index Lecture;5.1, 5.3 Ch. 5 (as many as you can; see below) 4/10 Coloring:  Chromatic number 5.1 Ch. 5 (as many as you can) IV. Due Wed. 4/12 1:00 sharp:Ch. 3 ## 2, 6, 8, 12, 17, 21 Web I 4/19 - 4/21 Coloring signed graphs; Flows:  Circulations;  Nowhere-zero flows Lecture;6.1, 6.3 Ch. 5 (as many as you can) V. Due Wed. 4/19:Ch. 4 ## 4, 11Ch. 5 ## 4, 7 4/24 - 4/28 Nowhere-zero flows:  Group flows;  Planar duality and 4CT;  Conjectures 6.3 - 6.5 Ch. 6 (as many as you can) VI. Due Thurs. 4/27:Ch. 4 ## 20, 23, Web III,Ch. 5 ## 10, 21, Web IV, V 5/1 - 5/5 Flows:  6-Flow Theorem;  Network flows 6.6;6.2 Ch. 6 (as many as you can) 5/8 - 5/12 Forbidden minors:  WQOs,  Tree decomposition 12.1, 12.3 Ch. 12 (some), espec. 12-14, Web I-IV VII. Due Fri. 5/12:Ch. 5 # Web VI,Ch. 6 ## 9, 15, 18, 19, Web I

• 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
1. With regard to the circuit packing theorem 2.3.2, here are two questions that seem interesting.

2. 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.
3. 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.
4. Does every cubic graph with exactly one isthmus have a perfect matching? (Thanks to Justin Almeida.)

5. 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 kn-i has sign (−1)i), and the coefficient of kn-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)n χG(−k), for k = 1,2,3,....
4. (R.P. Stanley, 1973) The number of acyclic orientations of G equals (−1)n χ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 pG(k) of proper pairs of a k-coloring and an acyclic orientation satisfies
pG(k) = pG-e(k) − pG/e(k) for k = 1,2,3,....
• Lemma 5.B: The number qG(k) of compatible pairs of a k-coloring and an acyclic orientation satisfies
qG(k) = qG-e(k) + qG/e(k) for k = 1,2,3,....
6. Prove Lemma S1. The chromatic polynomial of a signed graph Σ is not changed by switching.
7. Warning: The following two problems depend on studying basic signed graph theory first.
8. (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.
9. 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(Cn) = 2. Deduce that tw(G) > 1 if G is not a forest.
3. Show that tw(Kn) = n - 1.
4. Show that tw(Kn \ 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 Vt 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 Z1(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 = F2, 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 Ck = {0, ±1, ±2, ..., ±k}. For a zero-free k-coloring, the color set is Ck \ {0}. A coloring γ is proper if, for each edge evw, we have
γ(v) ≠ σ(evw)γ(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 Vt and "nodal subgraph" for G[Vt]. (I use the term "node" for a vertex of T. Generally, "node" is a synonym for "vertex" but not used much any more.)