### Errata

**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.4.6a**

(Contributed by Jeannette Dooley.) The graph H should be formed by joining the first and fourth (not first and third) vertices of P.

**Exercise 1.5.12a (first edition), 1.5.11a (second printing)**

(Contributed by Carmela.) The graph should be required to have no isolated vertices.

**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. Paciﬁc 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”.

**Exercise 2.4.7 (first edition), 2.4.8 (second printing)**

(Contributed by Stefan Gulan.) The graph G should be a *simple* connected graph (with an even number of edges).

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

**Proposition 2.13**

(Contributed by Evan Swain.) The notation ∂_{F}(X) is undefined. It denotes the edge cut of F associated with X.

**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.3b (first edition), 3.3.4b (second printing)**

(Contributed by Nima Aghdaii.) The graph G must be assumed connected.

**Hint to Exercise 4.2.5b**

The equation should be w_n-w_{n-1}=f_{n+1}+f_n.

(Perhaps F_n should have been defined as the fan with n spokes.)

**Exercise 4.2.11**

(Contributed by Frédéric Havet.) The word “the” occurs twice in succession. One instance should be removed.

**Exercise 4.2.15d**

(Contributed by Frédéric Havet.) The notion of “fundamental cycle” is defined later, in Section 4.3.

**Theorem 5.1**

(Contributed by Mark Tannous.) Figure 5.2 is misleading because v might well lie on one of the paths P’ or Q’. Referring to that figure later, after the definition of x, would resolve this problem, as the given proof remains valid even if v happens to lie on P’ (in which case x=v).

**Section 5.2**

(Contributed by Donovan Hare.) In the definition of a separation of a connected graph on page 119, “nonempty” should be replaced by “nontrivial”.

**Exercise 5.2.1**

(Contributed by Donovan Hare.) The case where G has just one edge must be excluded.

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

**Theorem 8.10**

(Contributed by Joe Weinstein.) It should be stated explicitly that no clause may contain both a literal and its negation.

The last sentence of the proof should be changed to:

One may verify that (x_1 ∨ x_2 ∨ · · · ∨ x_k) is satisfiable if and only if the conjunction of these k-2 clauses is satisfiable. We leave the details as an exercise (8.3.3).

**Exercises 8.3.2, 8.3.3**

(Contributed by Joe Weinstein.) See corrections to Theorem 8.10.

**Section 9.1**

(Contributed by Evan Swain.) On page 201, line 9 (first edition), page 208, line 8 (second printing), “Section 8.3″ should be “Section 8.2″.

**Theorem 9.1**

(Contributed by Donovan Hare.) In the proof of Theorem 9.1, the concept of reachability for undirected graphs is undefined.

Theorem 9.2 (alternative proof)

(Contributed by Nicolas Trotignon.)

**Exercise 9.1.14 (first edition), 9.1.15 (second printing)**

(Contributed by I.V. Hicks) For the stated conclusion to hold, it is necessary to require G to be simple and the edges e and f to be nonadjacent.

**Exercise 9.3.2a**

The stated inequality is valid only for nontrivial graphs

**Essential Edge Connectivity (p. 217)**

**Exercise 9.4.9 (first edition), 9.4.8 (second printing)**

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

**Theorem 10.26**

(Contributed by Yaad Blum.) In Case 2 of the proof, one cannot apply Exercise 9.2.3 directly, as the union of B and C might be separable. One must apply Exercise 9.2.3 to A union C, where A is an appropriate subgraph of B, namely the union of all paths in B between pairs of vertices of attachment of B.

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

(Contributed by Yaad Blum.) In the proof, the term G+e should be replaced by H+e (twice). Also, it should be assumed that G is 2-connected.

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

(Contributed by Carmela.) In order for figure 11.3 to correspond to the proof of the theorem, graph G23 should be changed to G13 throughout.

**Theorem 11.6**

(Contributed by Frédéric Havet.) In the statement of the theorem “FIVE COLOUR” should be hyphenated.

**Figure 12.5 (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 12.3.6**

(Contributed by Frédéric Havet.) ”2-edge colouring” should be replaced by “2-edge-colouring” (twice), and ”k-edge colouring” by “k-edge-colouring”.

**Exercise 12.3.11**

(Contributed by Frédéric Havet.) “finite” should be replaced by “infinite”.

**Page 317 (first edition), page 321 (second printing)**

The last sentence of the first paragraph is missing a full stop.

**Exercise 13.1.1**

There is an evident conflict of notation here.

**Exercise 13.2.7**

(Contributed by Frédéric Havet.) The graph G should be loopless in part (a) also.

**Exercise 13.2.17**

(Contributed by Frédéric Havet.) Add at the beginning: A hypergraph is *intersecting *if any two of its edges have a nonempty intersection.

**Exercise 13.3.6**

(Contributed by Frédéric Havet.) The term “fit” should be replaced by “discrepancy” (three times).

**Exercise 13.4.1**

(Contributed by Frédéric Havet.) G_{n,p} should be replaced by {\cal G}_{n,p} throughout.

In the last formula, the last k should be replaced by k(n).

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

**Page 366 (second printing)**

(Contributed by Frédéric Havet.) Gallai-Roy should be replaced by Gallai–Roy (twice).

**Exercise 14.1.4 (first edition)**

The addition operation in Exercise 14.1.4 should be replaced by union.

**Exercise 14.1.16**

(Contributed by Frédéric Havet.) “decreasing sequence” should be replaced by “decreasing subsequence”.

**Exercise 14.1.25 (first edition), 14.1.27 (second printing)**

(Contributed by Frédéric Havet.) The concept of a “claw-free graph” has not been defined. A *claw-free *graph is one which contains no induced K_{1,3}.

**Exercise 14.2.3**

(Contributed by Edward Lui.) Exercise 14.2.3 is incorrect. The Chvátal graph is not 4-critical.

**Exercise 14.2.9**

(Contributed by Yaad Blum.) It must be assumed here that k is at least three. The Hajos join of two 2-critical graphs is not 2-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.10 (first edition), 14.11 (second printing)**

(Contributed by Ning Bo.) In the last but one line of the proof of this theorem (on pages 371 and 376, respectively), the coefficient in the denominator of the last term should be 4, not 8.

**Section 14.6**

(Contributed by Yaad Blum.) Only the first 20 terms in the expansion of A(G,x) given on page 381 (first edition) and page 387 (second printing) are correct. The last four terms should be removed.

(Contributed by Evan Swain.) On page 381 (first edition), page 387 (second printing), “σ(e)” should be “σ(a)”.

**Theorem 14.22 (first edition)**

In the proof of Theorem 14.22, the term 1=1 should be replaced by i=1 (twice).

**Section 14.7**

(Contributed by Frédéric Havet.) In line 1, “polyomial” should be replaced by “polynomial”.

**Theorem 15.15 (first edition)**

A ceiling function is missing from the log term in (15.2).

**Section 15.5.**

(Contributed by Frédéric Havet.) In line 7, “that that” should be replaced by “that”.

**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 16.2.14 (first edition), 16.2.15 (second printing)**

(Contributed by Frédéric Havet.) The term “factor” is defined later, in Section 16.4.

**Exercise 16.2.23 (first edition), 16.2.24 (second printing)**

(Contributed by Frédéric Havet.) “matching covered” should be hyphenated.

**Exercise 16.4.12**

(Contributed by Frédéric Havet.) The symbol n should be changed (for example to p), as it does not signify the order of G here.

**Exercise 16.4.23 (first edition), 16.5.14 (second printing)**

(Contributed by Cláudio Lucchesi)

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.

**Exercise 16.4.22**

(Contributed by Frédéric Havet.) Problem 16.17 MINIMUM-WEIGHT EULERIAN SPANNING *SUPER*GRAPH.

**Chapter 17**

(Contributed by Frédéric Havet.) There are several instances where the hyphen is missing in ”edge colourable”.

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

**Exercise 17.1.5**

(Contributed by Jesus Alva.) “For i=1,2, let e_i=u_iv_i” should be replaced by “Let e_1=u_1u_2 and e=v_1v_2″

**Lemma 17.3**

(Contributed by Nima Aghdaii.) In the proof of Lemma 17.3 on page 456 (first edition), 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.”

(Contributed by Evan Swain.) At the end of the first paragraph of the proof of Lemma 17.3 on page 456 (first edition), page 462 (second printing), “saturating” should be “covering”.

**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 17.4.2**

(Contributed by Frédéric Havet.) Delete H, which serves no purpose.

**Exercise 18.1.9**

(Contributed by Frédéric Havet.) The concept of t-toughness is defined later, in Exercise 18.1.22.

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

**Section 18.2**

(Contributed by Frédéric Havet.) The several instances of “Int C” and “Ext C” should be changed to “Int(C)” and “Ext(C)”, respectively.

(Contributed by Frédéric Havet.) In the example following the proof of Theorem 18.2, “modulo” should be changed to “mod”.

**Theorem 18.9**

(Contributed by Vašek Chvátal) At the end of the first paragraph of the proof, one should add: Observe that the hypothesis implies that every vertex of G, and hence every vertex of G’, has degree at least two: if d_1 were at most 1, then d_{n-1} would necessarily be less than n-1, contradicting the hypothesis.

**Theorem 18.10**

(Contributed by Frédéric Havet.) In line 2 of the proof, change “proper bridge” to “nontrivial bridge”.

**Exercise 18.4.2**

(Contributed by Frédéric Havet.) A hyphen should be inserted in “3-edge colourings”.

**Exercise 18.4.5 (first edition), 18.4.6 (second printing)**

The concept of *Hamilton decomposition *has not been defined. It is a decomposition of the graph into Hamilton cycles.

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.

**Chapter 19.**

(Contributed by Frédéric Havet.) On page 506, the concept of blocker is defined for clutters, but not for hypergraphs in general. This can be corrected as follows. To each hypergraph H, one can associate a clutter H’ on the same vertex set whose edges are the minimal edges of H. It is easily seen that every transversal of H is a transversal of H’, and vice versa. When studying transversals of hypergraphs, one may thus restrict one’s attention to clutters.

**Page 510 (first edition)**

(Contributed by Frédéric Havet.) Gallai-Roy should be replaced by Gallai–Roy (twice).

**Section 20.5**

(Contributed by Frédéric Havet.) By convention, current flows from the positive to the negative pole, and not (as defined here) in the opposite direction.

(Contributed by Frédéric Havet.) It would perhaps be clearer to state Kirchhoff’s Voltage Law in its general form, namely “the voltage drops in D\e constitute a tension”, and then note that when the wires are of unit resistance, voltage drops are equal to currents.

**Corollary 20.27**

(Contributed by Frédéric Havet.) In the last line of the proof, 2m(v-1) should be replaced by 2m(n-1).

**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).

**Proof of Lemma 21.27**

(Contributed by Jim Geelen.) The proof of Lemma 21.27 is not valid for graphs with parallel edges.

Proof of Lemma 21.27 (corrected)

**Conjectures 82 and 85.**

(Contributed by Frédéric Havet.) The concept of “prism over a graph” has not been defined. The prism over a graph G is the cartesian product G x K_2.