Math 581: Topics in Graph Theory
Fall 2010

Matching Theory
Errata and Additions for the Textbook


To the main course page.


See the errata on pages 545-547 of the AMS edition!

Here is a link to the authors' updates page (no entries yet).

Here are errors and omissions I've found (with a little help from my friends students) and also supplementary definitions, etc.:

  1. Hungarian algorithm (p. 15). The algorithm doesn't specify how to find the necessary Hungarian forest.
  2. Hungarian algorithm, four steps (p. 15). The labels 10, etc., should (probably) be 1o, as a superscript "oh" is an established convention for "number" or "numero", i.e., 1o means "no. 1", and so on.
  3. Forest-representative system. The definition is not complete. Is it permitted to use the same pair of points to represent more than one set ("hyperedge") of H?
  4. Theorem 1.4.18 (König's Line-Coloring Theorem). Is there an error in the proof at the point where you are supposed to add the line a0b0?
  5. Is Exercise 1.4.20 stated in the right direction? I don't see how to do either direction in a truly easy way.
  6. In the definition of a network flow on page 43, (i) should read "for all v in V(D) - {s, t}." It makes no sense to quantify u and w, as they are quantified by the summations. Furthermore, restricting u, w ≠ s, t is incorrect.
  7. The extended f and c on page 43 should read that f(u,v) = c(u,v) = 0 if (u, v) is not in E(D). The opposite arc (v, u) is irrelevant.
  8. Theorem 2.2.3 (the time bound of the Edmonds-Karp algorithm) seems to be weaker than it need be. I'm pretty sure my method gives the upper bound q+p/2 < p2 on the number of steps. (I wrote to Lovasz about it. I'll tell you what he says.)
  9. Equation (2.4.1) should be
            Sume: x in e  w(e) ≤ f(x).
    I had a lot of trouble reading this, as usually an edge is e, not E, and anyway the explanation on p. 72, line 1, is wrong as we don't have a fixed edge.
  10. It is odd that an "f-matching" allows repeated edges, but an "f-factor" does not. About this definition, see Extra Question X.5 (not assigned but worth thinking about).
  11. They say on p. 76 that "E is the union of countably many rectangles ...". But E is a right triangle. Surely they mean E is a limit (in some sense) of the union of countably many rectangles. Anyway, what they say can't be right.
  12. Figure 3.3.1 has an incomplete sentence. The caption should end with "barriers."
  13. On p. 111 line -1: co(G-S) should be co(G'-S). (Ryan)
  14. On pp. 111 line -1 - 112 line 1: The subscripts t and k are reversed. The odd components are G1, ..., Gt and the even components are Gt+1, ..., Gk.
  15. In p. 112, par. 3, the explanation is incomplete. It should read: "The sum of the degrees ... is an odd number, but the sum of degrees in a graph is even; this contradicts the assumption that Gi is odd." (Ryan)
  16. In the lines just before (3.4.2), the summations should be Sum1k αi. The summations in (3.4.2) are correct. (Ryan)
  17. On p. 112 line -3, the inequality should be weak, since the sum of α's may equal 0. (This doesn't affect the argument.) (Ryan)
  18. In Theorem 3.4.6 there are several typos involving parentheses. (a) line 1: (Δ+1/2) should be (Δ+1)/2. (b) line s 1, 2: (Δ+1)/2) should be (Δ+1)/2.
  19. In the definition of an elementary bipartite graph on page 122, there's a missing word. G is elementary if the allowed lines form a connected, spanning subgraph; in other words, the allowed lines connect all the vertices. (You probably thought that was what it meant; but the word "spanning" was missing.)
  20. In Chapter 5 the notation co for the number of odd components has miraculously changed to c0. I'll stay with codd and co.
  21. In the proof of Theorem 5.1.3, Claim 3, paragraph 2, "Claim 1" should be "Claim 2".
  22. In Theorem 5.1.6(b), the set T \cap V(H) is an equivalence class only if it is nonempty.
  23. In the proof of Lemma 5.2.8, when proving G is bicritical if G1 and G2 are, in the case of G - {u,v} with u,v in V1 - {x,y}, in the subcase where xy is an edge of M1, there must be a proof that a perfect matching M2 exists in G2'; it is not enough for such a matching to exist in G2. To prove this, note that there must be an edge xz with z in V2 - {x,y} because otherwise y would be a cutpoint. Then G2 - {x,z} has a perfect matching, which cannot contain xy, and which extends by adjoining xz to the required M2.
  24. The definition of 3-blocks at the end of Section 5.2 is not entirely clear. The definition allows multiple edges to exist in the 3-blocks since no edges disappear during the decomposition, and indeed at each step 2 new edges are added. It is then possible to get nonunique 3-blocks from a simple graph: consider the union of two K4's along an edge. But they claim the 3-blocks are unique. It would be possible to define a 3-decomposition that only gives simple 3-blocks, which should be just as good for matching theory, but that isn't what they do. Their intentions are not clear.
  25. In the definition of a k-packing of T-cuts on page 236, the T-cuts should not be numbered from 1 to k. They should be numbered from 1 to (say) t; then t is the size of the k-packing. The maximum size is νk(G, T).
  26. In Exercise 6.5.15, |T| should be even, not odd.
  27. The definition of a potential on p. 243 should allow an infinite value, for use e.g. in 6.6.1 II. That is, a potential should be defined as V −> R union {infinity}. Perhaps even better is V −> R union {infinity, −infinity}.
  28. In Theorem 7.1.5, line 4, "t-matching" should be "b-matching".
  29. In Theorem 7.3.1(iii) on page 275, what does it mean for S to "span a ... subgraph"? There is no definition of this concept. (It is not the same as S spanning an edge.) After going over the proof I see they mean that S induces the subgraph.
  30. In Exs. 8.0.4 and 8.0.5, "|T| odd" must be "|T| even".
  31. The definition of an M-alternating forest F, on page 359, is corrected in the book's Errata on page 547. However, the correction is wrong too. The correction is to add the requirement that the M-edge incident with a vertex v of F at odd distance from the root (the S-vertex of that tree in F) must be an edge of F. That's necessary, but then they removed the requirement that every line at odd distance (in F) from the root should be an M-edge; in other words, that no non-M edge can go outward from an odd-distance vertex in F. They still need that requirement in addition to the new requirement.
  32. Index
    • "Cutpoint" and "Cutset" do not appear; defined on p. xxxi.
    • Under "Digraph" you are also referred to "directed graph" but the entry is under "Graph, directed". It's a pattern to be aware of.
    • "Point cover (in graph)" does not appear; defined on p. xxxii.
  33. Index of Symbols
    • ν(G,T) p. 236.


To the main course page.
To my home page.