Proof of Theorem 17.2

Written by on 17.05.2015 | Errata, Proofs, Using the book

Leonardo Carlos da Cruz has pointed out an error in the proof of Theorem 17.2.

The sentence:

Because the degree of $u$ in $G\setminus e$ is at most $\Delta – 1$, at least one colour $i$ is available at $u$, hence represented at $v$. Likewise, at least one colour $j$ is available at $v$ and represented at $u$.

should read:

Because the degree of $u$ in $G \setminus e$ is at most $\Delta – 1$, at least one colour $j$ is available at $u$, hence represented at $v$. Likewise, at least one colour $i$ is available at $v$ and represented at $u$.

Errata

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:

16.1.7
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.