Errata
This list of errata by chapter is taken from the posts. It will be updated periodically.
Exercise 1.1.22 (first edition)
(Contributed by Stephen Locke.) A factor of -1 to the power n is missing from the right-hand expression in part (b)(ii) of Exercise 1.1.22.
Exercise 1.3.18 (first edition)
(Contributed by Stephen Locke.) In Exercise 1.3.18b (i) the order of multiplication should be inverted, xy being replaced by yx.
Exercise 1.5.13 (first edition)
The adjacency matrix A in Exercise 1.5.13 should be replaced by a related skew-symmetric matrix.
Figure 1.26a
The directed graph shown in Figure 1.26a was first mentioned, in the context of matrices, by M.F. Tinsley (Permanents of cyclic matrices. Pacific J. Math. 10 (1960), 1067–1082). It was rediscovered, in the context of graphs, by K.M. Koh (Even circuits in directed graphs and Lovasz’s conjecture. Bull. Malaysian Math. Soc. 7 (1976), 47–52). This digraph should therefore be named the Koh-Tinsley digraph, not the Koh-Tindell digraph.
Definition of partial order
(Contributed by Guillermo Pineda.) On page 42, it is written that a partial order is an irreflexive binary relation; it is actually reflexive.
Exercise 2.1.16 (first edition)
(Contributed by Stephen Locke.) In Exercise 2.1.16b, the lower bound on n should be six, not five.
Section 2.2: Spanning and Induced Subgraphs
(Contributed by Nima Aghdaii.) In the subsection on Induced Subraphs, at the bottom of page 49 (first printing) or page 48 (second printing), the phrase “a induced subgraph” should be replaced by “an induced subgraph”.
Symmetric difference
(Contributed by Satoru Kudose.) On page 60, one paragraph before Proposition 2.11, it is stated that the operation of symmetric difference was introduced in Section 2.1. This is incorrect. It was introduced in Section 2.2.
Exercise 2.5.7
(Contributed by Cláudio Lucchesi.) Exercise 2.5.7b(i) is incorrect: the transitive triangle is a counterexample.
Section 2.6: Even Subgraphs
(Contributed by Nima Aghdaii.) There is a notational error on page 65 (five lines before the Exercises). The script G in the notation for the bond space should be a simple capital G (as in the notation for the cycle space).
Exercise 2.7.17 (first edition)
This exercise should be attributed to V.B. Mnukhin (The k-orbit reconstruction and the orbit algebra. In Interactions between Algebra and Combinatorics, Acta Appl. Math. 29 (1992), 83–117).
Theorem 3.1 (first edition)
In the first paragraph of the proof of Theorem 3.1, the mapping f should not be from N(x)\{z} to N(y)\{z} but from N(x) to N(y).
Exercise 3.3.3
(Contributed by Nima Aghdaii.) In Exercise 3.3.3b, the graph G should be assumed to be connected.
Exercise 5.3.12
Exercise 5.3.12a on page 128 should read “Show that there is a vine …
Exercise 6.1.7 (first edition)
In Exercise 6.1.7a, the stated equality should be an inequality.
Exercise 6.2.5 (first edition)
Exercise 6.2.5 is incorrect. It should read:
Let T be an optimal spanning tree in a weighted connected graph (G,w) (with positive weights), and let x and y be two adjacent vertices of T. Show that the path xTy=xy is an xy-path of minimum weight in G.
(As such it should no longer be classified as a hard exercise.)
Exercise 7.2.2 (first edition)
Here, the initial flow should be taken to be the zero flow, or any integer-valued flow, otherwise the statement is false. A maximum flow in a network whose capacities are integers need not itself be integer-valued. Consider, for example, the network N=(V,A,c), where V={x,u,v,w,y}, A={(x,u),(x,v),(u,w),(v,w),(w,y)}, and c(a)=1 for all arcs a. The flow f in N with f(x,u)=f(x,v)=f(u,w)=f(v,w)=1/2 and f(w,y)=1, though not integer-valued, is clearly a maximum flow.
Exercise 7.2.4 (first edition)
The network should be assumed to be acyclic. The case where directed cycles are allowed is addressed in Proposition 7.14.
Exercise 9.4.9
There is an error in the statement of this exercise (Tutte’s Wheel Theorem): “any edge” should be replaced by “some edge”.
Theorem 9.20
(Contributed by Benjamin Lévêque and Nicolas Trotignon.) At the end of the statement of Theorem 9.20, and also in the second line of its proof, the phrase ‘clique of G’ should be replaced by ‘clique cut of G’.
Lemma 10.33
(Contributed by Nima Aghdaii.) There is a superfluous end-of-proof symbol on page 270 following the statement of Lemma 10.33.
Corollary 10.39
(Contributed by Cláudio Lucchesi.) The restriction that n is at least three must be added to the statement of Corollary 10.39 (as in the statement of Corollary 10.21.)
Exercise 11.2.5 (first edition)
In Exercise 11.2.5b, the reference to Exercise 10.2.10c should be to Exercise 10.2.10b.
Theorem 11.4
(Contributed by Nima Aghdaii.) In the first line of the proof of Theorem 11.4 on page 289 the word “that” is repeated.
Figure 12.6 (second printing).
This figure is wrongly labelled. The script P’ and script P should be replaced by a script Q’ and script Q, respectively.
Exercise 13.1.1
There is an evident conflict of notation here.
Proof of Theorem 13.19
(Contributed by Frédéric Havet.) In the proof of Theorem 13.19, two names (S and M) are used for the same set, which is both a stable set in H and a matching in G. The stable set S should be renamed M.
Exercise 14.1.4 (first edition)
The addition operation in Exercise 14.1.4 should be replaced by union.
Exercise 14.2.3
(Contributed by Edward Lui.) Exercise 14.2.3 is incorrect. The Chvátal graph is not 4-critical.
Section 14.3: Girth and Chromatic Number
The proof by Paul Erdös of the existence of graphs with arbitrary girth and chromatic number appeared not in his 1961 paper Graph theory and probability II, as stated, but in his earlier paper Graph theory and probability, Canad. J. Math. 11 (1959), 34–38.
Theorem 14.22 (first edition)
In the proof of Theorem 14.22, the term 1=1 should be replaced by i=1 (twice).
Theorem 15.15 (first edition)
A ceiling function is missing from the log term in (15.2).
Exercise 16.1.13
In part (a), “every M-alternating path” should read “every maximal M-alternating path”.
Exercise 16.2.9
In Exercise 16.2.9a, the expression |N(S)|-|S| should be replaced by |S|-|N(S)| (twice). Also, the statement of part ii) is imprecise.
Exercise 17.1.3 (first edition)
(Contributed by Matthias Lenz.) The ceiling function in Exercise 17.1.3a should be replaced by the floor function.
Lemma 17.3
(Contributed by Nima Aghdaii.) In the proof of Lemma 17.3 on page 456 (first edition) or page 462 (second printing), the sentence “We may suppose that H has no such colouring.” should read “We may suppose that H has no such matching.”
Exercise 17.2.8 (first edition)
Exercise 17.2.8a (not due to Shannon) is incorrect: there are counterexamples on just five vertices. Shannon’s bound, stated in Exercise 17.2.8b, can be deduced quite easily by induction from Vizing’s bound (stated in Exercise 17.2.6b).
Exercise 17.2.13
This statement is a conjecture due to A.P. Wojda (A note on the colour class of a self complementary graph. Discrete Math. 213 (2000), 333–336.) Only the assertion of sufficiency has been established, and this should be classified as an easy exercise.
Exercise 18.1.11 (first edition)
The set S should be a nonempty proper subset of V.
Exercise 18.1.19 (first edition)
The bound in part (ii) of Exercise 18.1.19b, while correct, can be sharpened as follows.
Exercise 18.4.5
Part (a) is incorrect. The theorem published by A. Kotzig (Aus der Theorie der endlichen regulären Graphen dritten und vierten Grades. Časopis Pěst. Mat. 82 (1957), 76–92) is somewhat weaker than the statement given in Exercise 18.4.5a.
(Kotzig proved in the same paper that a simple cubic graph is 3-edge-colourable if and only if its line graph is 4-edge-colourable.)
Figure 19.4 (first edition)
This figure is wrongly labelled. The script P’ and script P should be replaced by a script Q’ and script Q, respectively.
Exercise 21.4.5 (first edition)
This exercise should be attributed to S.L. Hakimi (On the degrees of the vertices of a directed graph. J. Franklin Inst. 279 (1965), 290–308).
