Written by on 10.02.2013 | Errata

I hope that these potential errata haven’t already been found (as I couldn’t see them elsewhere) and if so then I apologize for reapeating them. I also believe that I am reading the first edition of the book so the page numbers are for the 2008 first edition.

1. page 50 in the proof of Theorem 2.5 you write “Suppose, by way of contradiction, that d_F (v) ≤ k” I believe that d_F should be δ.

2. On page 61 you use the notation ∂_{F_1} etc. without, I believe, defining what it means (i.e. the read knows what ∂ means). The obvious and logical conclusion for the reader is that it means ∂ restricted to the subgraph F_1 but it would be nice if …

Exercises 16.1.7 and 16.2.12 (first edition)

Written by on 10.02.2013 | Exercises, Questions

Good afternoon, please help me know how these problems are solved:

a) Let M be a perfect matching in a graph G and S a subset of V. Show that
| M ∩ ∂ (S) | ≡ | S | (mod 2).

b) Deduce that if M is a perfect matching of the Petersen graph, and C is the
edge set of one of its 5-cycles, then | M ∩ C | is even.

16.2.12 Let G: = G [X, Y] be a bipartite graph in each vertex of X is of odd
degree. Suppose that any two vertices of X have an even number of common neighbours.
Show that G has a matching covering every vertex of X

In advance thank you very much.

Errata updated

Written by on 10.02.2013 | Errata

The list of errata has at long last been updated. It includes recent contributions from Evan Swain and Frédéric Havet.

Exercise 16.4.23 (1st edition), 16.5.14 (2nd edition)

Written by on 20.05.2012 | Errata, Exercises

Cláudio Lucchesi remarks (and we agree):

I believe that there are two problems with this exercise.

1) H should be the graph obtained from G 􏰝 K2 by deleting x from one copy of G and y from the other copy of G.

2) The mapping in a) is not a bijection, it is an injection.