Math 510: Introduction to Graph Theory
Spring 2008

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 (Springer-Verlag, 2005). 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 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.

HOMEWORK: I will frequently collect written work: see the homework assignments.

• I expect you to try (almost) every hand-in problem (as well as other problems). If you can't solve the problem but you have some work that makes sense, write it up and turn it in.
• 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).
• Also, if you don't turn in a problem by the due date, I will accept a late paper (within a reasonable time, about two weeks), but I won't usually allow rewrites of late problems.
• If you have an emergency, be sure to tell me so I can adjust the requirements as necessary.

We meet on MWF 1:10 - 2:10 in LN-2205.
Office hours MWF 2:30 - 3:30, but I will usually be around much later on MWF afternoons, so stop in if you wish.

Special class times:
    Th 2/7 at noon in LN-2205.
    Th 3/13 at noon in LN-2205.
    Th 4/10 at noon in LN-2205.
    Th 4/17 at noon in LN-2205.
    Th 4/24 at noon in LN-2205.
    Th 5/1 at noon in LN-2205 instead of F 5/2.

The Combinatorics Seminar meets on Tuesdays at 1:15 in LN-2205. (Occasionally at a different time; check the schedule.) All 510 students are invited to attend (if the room is big enough for 510 students—Sorry, bad old joke, slap).

Supplementary Mathematics

• Synonym lists:
  • Cycle, circuit, circle, polygon. These are names for a (nonempty) connected edge set with all degrees equal to 0 or 2 (this is what the book would call a "cycle").
• 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.
• 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 10, Theorem 1.3.4: The theorem's meaning is not apparent from the statement. A meaningful statement would be: Given numbers d ≥ 2 and g in N, every graph G with δ(G) ≥ d and g(G) ≥ g has order |G| ≥ n₀(d,g).
• Page 30, # 6: There is something wrong with the statement of the second half; for instance, what do they mean by d? Can you figure out what it should be?
• 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.