Introduction to Graph Theory - Second Edition

by Douglas B. West

Corrections Page

This page contains corrections to mathematical aspects of the text. Most items are minor errors in notation; others are omissions of conditions in exercises, etc. The typos in notation appear in this list instead of the list of typos because notational typos can confuse a reader.

Contributors names appear in parenthesis. In particular, "JG" denotes John Ganci, who has read the book amazingly carefully, and "FG" denotes Fred Galvin, who has contributed many improvements for the text and exercises. Please send contributions for this page to dwest@math.uiuc.edu.

Related pages

• Comments and updates (corrections to references, comments on proofs or exercises, etc.)
• Minor typos (errors in spelling, punctuation, etc.)
• Supplementary Exercises (to be added in later editions)
• Index page for Introduction to Graph Theory
• Index page for Math 412

Corrections found SINCE the FOURTH printing

• p8 - Prop1.2.24: when corrections were made to this page for the fourth printing, the printer did not produce the page correctly. Each instance of "f ¹" should be "f ^-1". The minus signs are in the file that produced the page, but they were not printed on the page. (Rongheng Lin)
• p12 - Exm1.1.35: the "+e" and "-e" used in defining the paw and the kite have not been defined; here the notation should be replaced with words (FG)
• p17 - Exr1.1.23a: the effect of loops on vertex degrees is introduced later, so this exercise should not appear until later (FG)
• p21 - before Lem1.2.5: the meaning of when a walk contains a path is not given clearly; the edges in order must be traversed in the direction they would be when following the path (FG)
• p24 - before Lem1.2.15: in saying what it means for a closed walk to contain a cycle, the restriction "closed" can be dropped, and the same clarification as above about following edges in the right direction is needed (FG)
• p29 - Prop1.2.29: "maximal path P" should be "nontrivial maximal path P" so that P has at least two vertices (Michael Pelsmajer)
• p33 - Exr1.2.30: "nearest to n" should be "in {n-1,n}" (FG)
• p34 - Exr1.2.36: "the trails in this list" should be "such trails", and the problem (particularly part (a)) should be restricted to loopless graphs (FG)
• p34 - Exr1.2.43: "an even number of edges" should be "2k edges" (FG)
• p45 - Thm1.3.31: we must also ensure that d' is well defined, which requires that \Delta < n (FG)
• p51 - Exr1.3.42: the problem must be restricted to simple graphs, but it can be strengthened by specifying only the minimum degree. It is as easy and more natural without the pigeonhole principle, and in the next edition the problem will ask for a proof of impossibility for Q₄ (FG)
• p52 - Exr1.3.54: Closing parenthesis missing at end of hint (Leen Droogendijk)
• p52 - Exr1.3.58: "k largest elements" should be "d_k largest elements"
• p55 - Exm1.4.7: the expression for the edge set of a functional digraph is missing a right parenthesis (Peter Hamburger)
• p57 - App1.4.14: for purposes of this discussion, the digraph should be acyclic and W should be the full set of sinks (FG)
• p62 - after Def1.4.27: the sentence saying that an oriented graph is the same thing as a loopless simple digraph is nonsense, since simple digraphs can have opposed edges. The formal definition is given correctly. (Stephen Hartke)
• p65 - Exr1.4.34: The hint on p510 is misleading. More accurate is changing the last sentence to "Reduce the number of differences by performing a 3-cycle reversal in G or in H that involves a vertex of maximum outdegree in F". (FG)
• p67 - Exm2.1.2: A tree is a path if and only if its maximum degree is at most 2 (Michael Pelsmajer)
• p75 - Exr2.1.2b: requires restriction to simple graphs in order to forbid loops from G (FG)
• p75 - Exr2.1.13: requires restriction to connected graphs (FG)
• p76 - Exr2.1.28: "Let" should be "For n\ge2, let" (FG)
• p76 - Exr2.1.29: "tree" should be "nontrivial tree" (Mike Pelsmajer)
• p76 - Exr2.1.30: "tree" should be "nontrivial tree" (FG)
• p77 - Exr2.1.38: "d'_T" should be "d_T'"
• p77 - Exr2.1.41: The problem of finding the largest $f(n)$ such that some $n$-vertex graph with $n+f(n)$ edges has no two cycles with the same length was originally posed by Erdős in 1975. The mention of Chen-Lehel-Jacobson-Shreve [1988] in the IGT text is only a small part of the story. Shi [1988] proved roughly $f(n)\ge\sqrt{2n-4}$. The C-L-J-S paper and also Lai [1990] proved $f(n)\le O(\sqrt{n\log n})$. Lai [2020] improved the lower bound to $f(n)\ge 1.55\sqrt n$, and Boros-Caro-Füredi-Yuster [2001] proved $f(n)\le 1.98\sqrt n$. The restriction of the problem to $2$-connected graphs has been solved asymptotically; the number of edges is $n+f_2(n)$ where $f_2(n)\sim \sqrt{n}$. The lower bound is in Boros-Caro-Füredi-Yuster [2001], upper bound in Ma-Yang [2021]. (Chunhui Lai)
• p78 - Exr2.1.52: In part (a), k denotes the eccentricity of x (Bruno Petazzoni)
• p79 - Exr2.1.57: In part (b), "a tree T" should be "an n-vertex tree T" and the hint will be deleted (Leen Droogendijk)
• p79 - Exr2.1.60: The closed-form expression for the upper bound requires k > 2 (FG)
• p79 - Exr2.1.61: Add the restrictions k\ge2 and g\ge3 (FG)
• p79 - Exr2.1.65: The restriction can be weakened to n\ge k+3, but a restriction to simple graphs must be added (FG)
• p80 - Exr2.1.69: There are 9 vertical edges, not 12, and "v_3,2" should be "h_3,2" (FG)
• p80 - Exr2.1.73: "sufficiency" should be "necessity" (FG)
• p93 - Exr2.2.12: The formula may also use the numbers of vertices and edges of G (Alexandr Kostochka)
• p104 - Exr2.3.6: "the subgraph consisting of" should be "the spanning subgraph whose edges are", to include the case where all weights are odd (Leen Droogendijk)
• p106 - Exr2.3.31: it should be stated more clearly that the set of code words is required to be prefix-free, as in Huffman's algorithm (Larry Brown)
• p109 - Def3.1.6: As stated, an M-augmenting path could have length 0. It should be specified that the endpoints are distinct (Haiko Muller)
• p117 - Thm3.1.30: requires restriction to simple graphs or hypothesis that every vertex has at least k neighbors; same for Rem3.1.31 (FG). Also, the reference to Alon's paper is incorrect and should be deleted (Bruce Priddy)
• p117 - Rem3.1.31: "total domination number satisfies a bound asymptotic to this" should be "one can obtain a dominating set with asymptotically the same size having the additional property of inducing a connected subgraph
• p119 - Exr3.1.12: "single path" should be "single nontrivial path"
• p119 - Exr3.1.13: the bold and solid edges should be switched (Peter Winkler)
• p120 - Exr3.1.23: in the hint, "proper subset" should be "nonempty proper subset" and "minimal nonempty" should be "nonempty" (FG)
• p121 - Exr3.1.36: restrict to simple graphs (FG)
• p123 - Exr3.1.60: "sharp" should be "almost sharp"; in the graph described the smallest dominating set has size 3m-2
• p129 - Rem3.2.12: "reachable in X and T" should be "reachable in X and Y, respectively" (Guilherme Ottoni)
• p130 - Appl3.2.14: in the definition of the demand at y, the superscripts "+" and "-" should be interchanged (Dan Cranston)
• p137 - Thm3.3.3: At the bottom of the page, the set in which the 1-factor is to be found is the union of M₁ and M₂ together with {xy,yz} (Jerry Grossman)
• p148 - Exr3.3.29c: should begin as "Use part (b) to conclude that nonnegative integers d₁,...,d_n with d₁\ge...\ge d_n are . . ." (Ebrahim Ghorbani)
• p152 - Def4.1.7: The graph K₁ has no disconnecting set (not even the empty set); its edge-connectivity must be taken to be 0 by convention (Sandi Klavzar)
• p153 - Thm4.1.11: The 2-vertex graph with a triple-edge must be excluded. When "graph" forbids multiedges in the third edition, that wil not be a problem, but still K₄ must be handled separately, since it has no vertex cut (Songling Shan)
• p154 - Thm4.1.11: The picture is not sufficiently general, since deleting {v₁,v₂} may leave three components. To be more precise, for each v∈S delete the edge to H₁ if there is only one such edge; otherwise there is only one edge from v to H₂ and we delete that. Now every path from V(H₁) to V(H₂) traverses a deleted edge (Robert McCann)
• p155 - Rem4.1.18: When multiple edges are allowed, a multi-edge has no cut-vertex but is not 2-connected, so an exception is needed here (Rob Ellis). In the third edition, "graph" will forbid multi-edges, so this difficulty will disappear.
• p159 - Exr4.1.22: The complete graph must be excluded. The point is to show that G has no separating set of size at most k
• p163 - Def4.2.7: We must also require that the endpoints of the ear have degree at least 3 in G. (Sandi Klavzar)
• p163 - Thm4.2.8: When multiple edges are allowed, a multi-edge can be viewed as having an ear decomposition but is not 2-connected, so an exception is needed here (Rob Ellis). In the third edition, "graph" will forbid multi-edges, so this difficulty will disappear.
• p160 - Exr4.1.25: in part (a), when |S|=n(G)/2, one can only guarantee that one side of the cut has this property, not both (Tao Jiang). Furthermore, to make the statement correct, one should first assume that the edge-connectivity is less than the minimum degree (Randy Komperda)
• p169 - Thm4.2.21: The first statement fails in the special case where all pairs of vertices are joined by at least two edges (Bruce Sagan). In future editions, such statements will be made only for simple graphs, which is the context of interest for connectivity, to avoid such difficulties
• p170 - Thm4.2.23: Again, the context of simple graphs will fix the problem in the sufficiency proof here that k distinct neighbors are needed (instead of \dlt(G)\ge k), which indeed is guaranteed by a v,V(G)-{v}-fan. The problem that z might be an internal vertex in a w,N(z)-fan will be corrected by defining paths in an x,U-fan to reach U only at their endpoints. (Bruce Sagan)
• p173 - Exr4.2.8: The exercise should be restricted to graphs with more than two vertices. (Alexandr Kostochka)
• p174 - Exr4.2.24: It is not necessary that S and T be disjoint (Leen Droogendijk)
• p175 - Exr4.2.28: Change "nonnegative" to "positive" or change "X,Y-paths" to "paths from X to Y". With the specific definition given for X,Y-paths (no internal vertices in X or Y), there is a technical counterexample with 0 weights. (Stephen Hartke)
• p175 - Exr4.2.29: The edge implication and vertex implication should be separated and should be stating for individaul vertex pairs, yielding stronger statemens (Leen Droogendijk)
• p175 - Exr4.2.30: The statement should be restricted to simple graphs (Shir Kehila)
• p182 after Rem4.3.14: The reference to Theorem 4.2.25 should be to the *second* Theorem 4.2.24 (Nick Matteo)
• p195-6 Exm5.1.15 - Prop5.1.16: It should be observed that we may assume without loss of generality that the intervals in a representation are closed, since that is used in the proof of the proposition (Bruce Sagan)
• p195 - bottom: "a, d, . . ." should be "a, e, d, . . ." (Andrew Badr)
• p197 - Thm5.1.21: in line 4 of the proof, "the longest path" should be "a longest path" (Bruce Sagan)
• p204 - Exr5.1.55: the unequal sign should be the incongruent sign (FG)
• p213 - Thm5.2.20: at the beginning of the last paragraph, "x\in V(G)" should be "x\in V(H)" (Bruce Sagan)
• p215 - Exr5.2.9: require also that G is nontrivial, since the statement is not true when G is 1-critical (Bruce Sagan)
• p217 - Exr5.2.25: part (a) should specify that G has n vertices
• p217 - Exr5.2.32: part (a) should require k\ge3
• p218 - Exr5.2.37b: should be restricted to simple graphs (FG)
• p218 - Exr5.2.39: n\ge2 is required (Bruce Sagan)
• p225 - Lem5.3.16: it must also be required that G is connected (Bruce Sagan) (Note: 5.3.16-17 will be replaced in the next edition by a single, less technical proof, with the stronger statement in 5.3.16 becoming an exercise)
• p230 - Exr5.3.10: "{n-1\choose i}" should be "{n-1\choose i-1}" (Leen Droogendijk)
• p231 - Exr5.3.23: S should be restricted to be the vertex set of a cycle of length at least 4 (Peter Hamburger)
• p232 - Exr5.3.32: "\chi(G;k)" should be "\chi(G;-k)" (Nathan Reading)
• p240 - Prop6.1.18: loops must be forbidden (FG)
• p242 - Prop6.1.26: n\ge3 is required (Bruce Sagan)
• p243 - Exr6.1.6: should restrict to "loopless" (Mike Pelsmajer)
• p245 - Exr6.1.30: It should be specified that k is finite (Yiu Yu Ho)
• p245 - Exr6.1.34: "dodecahedron" should be "icosahedron" (Jerry Grossman)
• p246 - Exr6.1.36: n\ge3 is required (Brendon Rhoades)
• p246 - Exr6.1.37: l\ge2 is required (Jerry Grossman)
• p247 - before Lem6.2.4: The first sentence of the paragraph should be "We will prove that a graph with fewest edges among nonplanar graphs with no Kuratowski subgraph must be 3-connected" (this is the goal in Lem 6.2.7) (Jerry Grossman)
• p248 - Lem6.2.7: To avoid isolated vertices, one should require G to be connected or assume that the number of vertices plus number of edges has been minimized (Wasin So)
• p250 - Thm6.2.11: in the next-to-last line, "u,v,x" should be "u,v,w" (John Harper)
• p251 - Def6.2.12: emphasizing here the duality between deletion and contraction (as in matroids) produced an error; this definition does not allow deletion of isolated vertices. The correct definition is that H is a minor of G if H can be obtained from G by contracting a subset of the edges in a subgraph of G (Bruce Sagan)
• p256 - Exr6.2.12: deletion of isolated vertices must also be allowed (Andre Kundgen)
• p265 - after Exm6.3.17: The leading term for the number of edges in the grid with n points should be 2n, not n (Alexis Seferlis)
• p270 - Exr6.3.7: it needs to be assumed also that H' is 2-connected (Bruce Sagan)
• p271 - Exr6.3.17: the floor symbol on (n+2)/6 should be ceiling, like the instance before it
• p271 - Exr6.3.24: "|i-j| <= k" should be "0 < |i-j| <= k" for clarity (the graph is simple)
• p272 - Exr6.3.28-29: It should be noted that we consider only drawings in which incident edges do not cross. Even better is to count only pairs of nonincident edges that cross an odd number of times.
• p283 - Exr7.1.13: C₅ is another example (FG)
• p283 - Exr7.1.15: the reference to Ex3.3.22 should be to Ex3.3.23 (Roland Loetscher)
• p285 - Exr7.1.35: set bracket missing at the end of the definition of P
• p285 - Exr7.1.38: this exercise should assume also the hypothesis from Theorem 7.1.17 that G has no double triangle with both triangles odd (John Caughman)
• p287 - Prop7.2.3: "S\subseteq V" should be "S\subset V(G)" (Bruce Sagan)
• p289 - Def7.2.10: "at least n" should be "at least n(G)" (Luke St. Clair)
• p297 - Exr7.2.30: Ore's Condition is that for each pair of nonadjacent vertices, the degree sum is at least the number of vertices. The sufficiency of this condition for the existence of Hamiltonian cycles is an immediate corollary of Lemma 7.2.9, but it is not the statement of Lemma 7.2.9. (Lale Ozkahya)
• p301 - Thm7.3.2: in line 2 of this page, "solid" and "bold" should be switched (Sun-Yuan Hsieh)
• p301 - Lem7.3.3: "xy,uv are distinct" should be "xu,yv are distinct, with x and y on the same side of the cut" (Bruce Sagan)
• p304 - Lem7.3.10: "girth less than 4" should be "girth at most 4" (Gabe Cunningham); also, "bridgeless" should be added to first part of the hypothesis (Leen Droogendijk)
• p310 - after Thm7.3.24: It should be observed that both existence and nonexistence of nowhere-zero k-flows is preserved by subdivision (Leen Droogendijk)
• p317 - Exr7.3.22: the case (k,t)=(2,3) is an exception
• p322 - Thm8.1.6: since it has not been shown that every vertex of G lies in some Q, it remains possibile that ω(H)<ω(G), but that does not affect the rest of the proof (Leen Droogendijk)
• p325 - above Alg8.1.12: The reference to Theorem 5.3.17 should be to Lemma 5.3.16 (Leen Droogendijk)
• p346 - Exr8.1.23: G has n vertices (Leen Droogendijk)
• p345 - Exr8.1.21: The requirement n>k is missing (Leen Droogendijk)
• p347 - Exr8.1.35: only induced odd cycles of length at least 5 are forbidden
• p372 - Exr8.2.9: this problem should be stated for partition matroids, not transversal matroids, and then it is a (-) problem
• p373 - Exr8.2.16: this problem should specify using the dual version of the base exchange property (Lemma 8.2.33)
• p374 - Exr8.2.22: in order to be a (-) problem, this should follow and use Exr8.2.24
• p375 - Exr8.2.31: the second part of this exercise doesn't seem to make much sense
• p379 - Thm8.3.3: the last term in the example list at the bottom of the page should be "10", not "0" (Zhaojun Wu). Alternatively, the pair underneath it should be "1,4" instead of "4,1" (M. Falahat).
• p387 - Thm8.3.15: the conclusion holds for m at least 2 (Leen Droogendijk)
• p395 - Exr8.3.32: the square root sign should apply to all of n(G)-3
• p395 - Exr8.3.33: "proved that" should be "proved that if"
• p399 - Cor8.4.9: "less than n-1" should be "at most n-1" (Leen Droogendijk)
• p408 - Thm8.4.24: in the last sentence, "Claim 3" should be "Claim 2" (Leen Droogendijk)
• p409 - after Prop8.4.25: For m=4, the bound should be n≤18, not n≤20 (Dan Cranston)
• p410 - Lem8.4.29: "the kernel" should be "a kernel" (Leen Droogendijk)
• p414 - below picture: Gallai's Conjecture should be stated for connected graphs (Leen Droogendijk)
• p415 - line below picture: superscript 2 should be superscript 1 (Leen Droogendijk)
• p417 - Lem8.4.36: "s_i,t_j-path" should be "v_si,v_tj-path" (Leen Droogendijk)
• p418 - Thm8.4.38: "the j neighbors" should be "the successors of the j neighbors" (Leen Droogendijk)
• p423 - Exr8.4.19: "lg n" should be "\ceil{lg n}"
• p423 - Exr8.4.22: "\dlt(G)" should be "\dlt(H)", and n should be n(G)
• p427 - after Rem8.5.5: The k here is the p of Theorem 8.5.4 (Leen Droogendijk)
• p429 - Theorem 8.5.11: The theorem statement should use k rather than m to agree with the usage of k in the proof (Leen Droogendijk)
• p434 - bottom: it is not true that all forests are balanced graphs; the statement should be for trees (Andrey Ruhkin)
• p444 - Thm8.5.33: the exponent n is missing on the upper bound in the inequality to be proved by induction in the second paragraph
• p449 - Exr8.5.4: "at least" should be "at most", and it should be required that there be r vertices in the first partite set and s vertices in the second (Luis Goddyn)
• p450 - Exr8.5.25: "\rho(G)=\max_{G\esub H}e(G)/n(G)" should be "\rho(H)=\max_{G\esub H}e(G)/n(G)" (Michael Pelsmajer)
• p470 - Exr8.6.25: it must be required that G and H each have at least two vertices
• p480 - RemA.27: In the third paragraph, "we began with L" should be "we began with S" (Alexander Johnson)
• p506 - ExrB.16: "Given a graph G" should be "Given a graph G without isolated vertices" (Andre Kundgen)
• p515 - Arborescence: "outdegree at most one" should be "indegree at most 1" (Gitta Marchand)
• p538 - Alon [1990]: the wrong paper is cited; it should be N. Alon, Transversal numbers of uniform hypergraphs, Graphs and Combinatorics 6 (1990), 1-4.
• p540 - Bollobás [1981]: the correct citation is Discrete Math. 33 (1981), 1-19 (Simon Spacapan)
• p548 - Ghouila-Houri: the volume number is 251, not 156 (Art Busch)
• p552 - missing reference: Jacobs K. (1969) Der Heiratssatz. In: Jacobs K. (eds) Selecta Mathematica I. Heidelberger Taschenbücher 49. Springer, Berlin, Heidelberg. (Jacobus Swarts)
• p561 - missing reference: Richardson M., Solutions of irreflexive relations, Ann. of Math. (2) 58 (1953), 573-590; errata 60 (1954), 595. (Jacobus Swarts)
• p588 - Whitney's Theorem: the page number should be 161 (Dave Keller)

All subsequent corrections listed on this page WERE MADE for the second printing of the second edition, EXCEPT for those in the first section below, which were made later.

Corrections IMPLEMENTED for the fourth printing (this section only)

• p8 - Prop1.1.24: Logicians say that there are too many simple graphs to form a set; graph theorists mostly ignore this. To finesse the difficulty, just rephrase this statement as "On any set of simple graphs, the isomorphism relation is an equivalence relation." (Ken Bogart, Gerard Chang)
• p8 - Prop1.1.24: "f ^-1(x)f ^-1(y)\in E(H)" should be "f ^-1(x)f ^-1(y)\in E(G)" (Hasnor Lot)
• p18 - Exr1.1.45: The problem is correctly stated but should be marked "+". However, the graph given as a solution in the solution manual has a nontrivial automorphism and hence is incorrect. The next version of the manual will have a picture of a graph that looks more symmetric but in fact has no such automorphism (Luis Dissett)
• p50 - Exr1.3.33: The number of vertices should be 1 plus the binomial coefficient d(x)+1 choose 2, not d(x) (Reza Dorrigiv). The "k=5" in part (b) should be "d(x)=5" (Gerard Chang)
• p94 - Exr2.2.26: "Frucht [1979]" should be "Rosa [1967]" (JG)
• p98 - Thm2.3.7: "w(u,z)" should be "w(uz)" (JG)
• p99 - App2.3.9: The name "Guan Meigu", given in the Chinese order, should be given in the English order "Meigu Guan" for consistency
• p104 - Exr2.3.7: The reference to Exercise 2.1.34 should be to Exercise 2.1.37 (JG, Gabor Hetyei)
• p105 - Exr2.3.19: The C-L-R reference has now been added to the bibliography and the author index
• p109 - Def3.1.7: This definition is too restrictive, since sometimes it is convenient to take the symmetric difference of graphs that don't have the same vertex set. Having defined symmetric difference of sets, it should be extended to graphs by letting G\symd H be the subgraph of G\cup H with edge set E(G)\symd E(H) and no isolated vertices. (JG)
• p111 - Before Cor3.1.13: The statement about the Marriage Theorem would be clearer as follows: "If, for some k\in\NN, every man is compatible with exactly k women and every woman is compatible with exactly k men, then a perfect matching must exist."
• p118 - Thm3.1.34: Various slight inaccuracies in the proof and figure are fixed by changing all appearances of "N(S')" to "R", where R is defined to be the set N(S')\cup S' of vertices dominated by S'. (The last character of the first paragraph has been corrected from S to T in the second printing.) For further clarity, after its first sentence the second paragraph continues as "Since S' is a maximal independent subset of S, every vertex of S-S' has a neighbor in S'. Similarly, T' dominates T-T'. Hence S'\cup T' is a dominating set." In the final paragraph, the second sentence becomes "Since each vertex of S-S' has a neighbor in S', each such vertex has at most one neighbor in T', because S'\cup T' is independent and G is claw-free."
• p122 - Exr3.1.51b: Mentioning diameter in a lower bound requires the graph to be connected. Here the upper bound can be improved to n-\ceiling{(2 diam(G))/3}. The lower bound should have the ceiling function applied to it, at which point one can add "Show that both inequalities are sharp for all n." (JG)
• p122 - Exr3.1.53: Rem3.1.33 says that the constructions in this exercise show that its bounds are sharp; this exercise should therefore require minimum degree 2 and 3 for the examples (FG)
• p122 - Exr3.1.56: The second part is incorrect; there is in fact a dominating set of five pairwise non-attacking queens on the eight-by-eight chessboard
• p123 - Exr3.1.57: Restrict to n at least 4 (JG)
• p123 - Exr3.1.58: Restrict to r at least 3 (FG)
• p123 - Exr3.1.59: Restrict to connected graphs (JG) and n > 2 (FG)
• p123 - Exr3.1.60: Restrict to connected graphs, and "\dlt(G)\le k" should be "\dlt(G)\ge k" (FG)
• p125 - pre-Alg3.2.1: It was not clearly explained how negative weights can be eliminated. Replace negatives by 0, and then after running the algorithm to find a maximum weight perfect matching, discard the edges of weight 0 to find a maximum weight perfect matching in the original problem (Gerard Chang)
• p131 - Thm3.2.18: In order to show that the algorithm terminates, one must show that no man can be rejected by all the women, after which the argument about the length of the remaining lists applies. Proving this claim takes only a few lines, but there is not room on the page for the proof as a correction, so I have added it as an exercise at the end of the section. (Gerard Chang)
• p132 - top parg: In the matching listed, "ca" should be "za" (JG)
• p146 - Exr3.3.12: "one endpoint in T" should be "at least one endpoint in T"
• p150 - Exm4.1.4: Require k to be at least 2 (Don Monk)
• p152 - Def4.1.7: These definitions of k-edge-connected and edge-connectivity should be restricted to graphs with at least two vertices, and the edge-connectivity of K₁ should be taken by convention to be 0 (FG)
• p153 - above Them4.1.11: "has diameter 2" should be "has diameter 2 and is simple" (FG)
• p160 - Exr4.1.26: F should be restricted to be nonempty
• p160 - Exr4.1.29: It would be clearer to add "of G" after "bond"
• p163 - Def4.2.7: The definition given for "ear" is inadequate, as it allows a graph to grow through a cut-edge. It should be this: "An ear of a graph G is a path that is maximal with respect to internal vertices having degree 2 in G and is contained in a cycle in G." (Dan Pritikin)
• p165 - Prop4.2.13: In the containment inequalities specifying the main case, "S" should be "S\cap D" (Shive Bansal)
• p172 - Thm4.2.25: in line 2 on this page, the definitions should be I={i\in[m]: a_i\notin R} and J={j\in[m]: b_j\notin R} (also similar correction to example, labels I,J,R added to figure, and fuller explanation of last line of proof) (JG)
• p173 - Exr4.2.10: should be (+)
• p174 - Exr4.2.19: "belong to a common cycle" should be "equal or belong to a common cycle"
• p203 - Exr5.1.50: last line missing from bottom of page, should be "minimizing \sum e(G_i)/k_i has the desired property.) (Lovász [1966])"
• p216 - Exr5.2.14b: k should be at least 2
• p270 - Exr6.3.10: "Tovey-Steinberg" should be "Steinberg-Tovey" (and the citation on p565 should move one page earlier)
• p296 - Exr7.2.18: "two graphs" should be "two nontrivial graphs" (the factors should have at least two vertices each)
• p297 - Exr7.2.26-7: in these problems, n must be at least 2
• p305 - Def7.3.11: "3-colorable" should be "3-edge-colorable" (Candida Nunes da Silva)
• p307 - first paragraph: Tait's Theorem states this equivalence for the duals of plane triangulations, not for the triangulations themselves (Candida Nunes da Silva)
• p310 - before Thm7.3.25: The sentence beginning "Nevertheless" should end with "in cubic 3-edge-colorable graphs" (the Petersen graph is cubic but not 4-flowable) (Candida Nunes da Silva)
• p325 - Exm8.1.13: "c,e,d,b,h,g,a,u" should be "c,e,d,b,h,u,g,a", and the reverse order should be similarly corrected. Also, "the graph G above" should refer explicitly to the graph illustrating Theorem 8.1.11. (Yaokun Wu)
• p336 - Exm8.1.36: the last line is nonsense - showing that the only p-critical cycle-powers are odd cycles and their complements reduces the SPGC to showing that all p-critical graphs are cycle-powers
• p338 - Thm8.1.39: all of the constant vectors of 1s in the first display should have a transpose indication on them (Yaokun Wu)
• p352 - Exm8.2.13: "``augments'' I<sub>2</sub>" should be "``augments'' I₁"
• p376 - Exr8.2.46: there is no "graph below" - just construct a graph and an abstract dual of it that is not a geometric dual of it
• p393 - Exr8.3.13: "(3^k-1)/2" should be "(3^k+1)/2" (Gerard Chang)
• p403 - Thm8.4.18: In the last paragraph on the page, "{f_i(k),f_j(k)}" should be "{f_k(i),f_k(j)}" (Sandeep Joshi)
• p419 - Thm8.4.40: the originator of this proof is Feng Tian, not Tian Feng (in Western notation); the family name is Tian. Prof. Tian has recently found a proof that is still shorter than the 1988 proof presented here
• p426 - Rem8.5.5: the numbers don't make any sense. Better would be "The probability that a random 64-vertex graph has a 10-clique or independent 10-set is bounded by ((2⁶)¹⁰/10!)2^-44, which is less than .03. If the first random one has such a 10-set, generate another. The probability of continued failure is the product of numbers less than 1 and soon becomes incomprehensibly small." (Borys Bradel)
• p437 - second paragraph: the text says that when pn is a constant larger than 1, the number of vertices outside the giant component becomes o(n). This is wrong. The point is that the order of the largest component becomes linear in n, and the fraction of the vertices contained in it depends on c. Outside the component, the fraction is 1 minus this, so again the number of vertices is linear in n (Jerry Grossman)
• p452 - Exr8.5.39: the first right parenthesis should be deleted (Jozef Skokan)
• p452 - Exr8.5.40: the first right parenthesis should be deleted (Jozef Skokan)
• p458 - Thm8.6.16: should be restricted to connected graphs
• p486 - ThmA.42: In the last line of the page, the dot should be three dots (Don Monk)
• p503 - ThmB.10: In the next-to-last paragraph, "P" should be "Q" twice in the first sentence (Andre Kundgen)
• p546 - Feng, T.: should be Tian, F.
• p551 - P. Hall: "representation" should be "representatives" (David Pike)
• p572 - Lucas/Luczak: the mention of Lucas should be deleted from the line for Luczak (Jozef Skokan)
• p583 - "Nordhaus-Gaddum Theorem": the missing page reference is 202 (David Pike)

Corrections for Chapters 1-7 IMPLEMENTED for the second printing

• p32 - Exr1.2.19: False as stated; the vertex set should be the set of congruence classes mod n, with i and j adjacent if and only if they have elements differing by r or s.
• p36 - figure: upper left vertex of lower square should be "010" (Arnoud Hobbel)
• p37 - Prop1.3.9: "an X,Y-bigraph" should be "a k-regular X,Y-bigraph" (JG)
• p37 - Prop1.3.11: In the display, "d_G(v_i)" should be "d_G(v_j)" (Mozart Menezes)
• p37 - Prop1.3.11: "\sum(G-v_i)" should be "\sum e(G-v_i)" (JG)
• p41 - Thm1.3.23: "K_n,k,k" should be "K_n-k,k" (JG)
• p49 - Exr1.3.19: G should be restricted to be simple
• p49 - Exr1.3.22: the statements are not valid for graphs containing K₄; "triangle-free" should be added to the hypotheses on G (also at one point the argument needs the graphs to be simple)
• p54 - before Def1.4.3: "(head, tail)" should be "(tail, head)" (JG)
• p63 - Exr1.4.6: "D₄" should be "D₃" (since D₄ is shown in the text)
• p63 - Exr1.4.12: the definition of connection relation on p60 (index incorrectly said p59) was not what is needed here. Thus this exercise should be "For a digraph D, define a relation on V(D) that is satisfied by the pair (x,y) if D has an x,y-path and a y,x-path. Prove that this is an equivalence relation and that its equivalence classes are the vertex sets of the strong components of D." (JG)
• p64 - Exr1.4.15: "0\le n" should be "0\le j\le n" (JG)
• p64 - Exr1.4.16: Both parts should require n to be a prime number.
• p68 - Thm2.1.4: condition D should also forbid loops (Mark Ellingham)
• p70 - Prop2.1.7: in the explanatory paragraph at the end of the proof referring to the figure, the roles of T and T' should be switched (JG)
• p77 - Exr2.1.38: the last "T'" should be "T" (JG)
• p84 - Exm2.2.6: the last spanning tree in the figure should be a star centered at the lower-left vertex (JG)
• p93 - Exr2.2.14: "vertex [n]" should be "vertex set [n]" (JG)
• p94 - Exr2.2.24: The question should be "Of the graphs with vertex set {0,...,n-1} that have n-1 edges, how many are gracefully labeled by their vertex names?"
• p103 - Exr2.3.4: The missing "graph below" was the graph obtained from K₅ by deleting two non-incident edges (Ed Pegg)
• p118 - Thm3.1.34: first paragraph should end with "T", not "S" (JG)
• p119 - Exr3.1.15: part (a) was valid only for k at least 2 (Thyagarajan Nandagopal)
• p122 - Exr3.1.41: not true in the generality stated; should be "Let G be a non-bipartite graph having exactly one cycle, C. Prove that \alpha(G)>=(n(G)-1)/2, with equality if and only if G-V(C) has a perfect matching
• p122 - Exr3.1.51: restrict to simple graphs and reverse the first inequality sign
• p126 - Def3.2.6: "u_i...v_n and v_j...v_n" should be "u₁...v_n and v₁...v_n"
• p137 - Thm3.3.3: At the bottom of the page, the set in which the 1-factor is to be found is the symmetric difference together with {xy,yz}
• p138 - Thm3.3.3: Just before the end, we produce a 1-factor of C+{xy,yz}, not a 1-factor of C (JG)
• p140 - Thm3.3.9: The degree needs to be positive (David Norris & Aaron Lippold)
• p141 - Thm3.3.13: "f(v) edges at v" should be "f(v) vertices of degree 1 corresponding to v" (JG)
• p146 - Exr3.3.9: restrict to graphs without isolated vertices (Dmitry Fon-Der-Flaass)
• p147 - Exr3.3.19: The hint should refer to Corollary 3.3.8, not Theorem 3.3.9.
• p155 - Prop4.1.15: "G[_]" should be "G[\bar S]" (Jason Tedor)
• p158 - Exr4.1.6: valid only for connected graphs
• p159 - Exr4.1.18: should be restricted to simple graphs
• p159 - Exr4.1.24a: should be restricted to n\ge4 (Carey Radebaugh)
• p164 - Def4.2.9: "closed ear in G" should be "closed ear in "P₀\union...\unionP_i" (JG)
• p164 - Def4.2.11: as in the undirected case, the complete doubly-directed digraph has no separating set; take its connectivity to be the number of vertices whose deletion reduces it to a single vertex
• p165 - Prop4.2.13: "nonempty vertex subset" should be "nonempty proper vertex subset" (JG)
• p167 - Thm4.2.17: "v\in(V₁\cap V₂)" should be "v\in(V₁\cap V₂)-S". Also, "V(G₁)\cap V(G₂)" should be "V₁\cap V₂". Also, at the bottom "{x" and "y}" should be "{x}" and "{y}" (JG)
• p168 - Thm4.2.17: in the top paragraph, the last two occurrences of "v" should be "u" (JG)
• p179 - Alg4.3.9: "f(uv>0)" should be "f(uv)>0" (JG)
• p179 - Exm4.3.10: "u,v" should be "u,x" (JG)
• p185 - Thm4.3.18: the theorem statement was missing the condition that \sum p_i = \sum q_j
• p193 - Exm5.1.10: the notation for the cartesian product was introduced by Nesetril [1981], not Rodl
• p199 - Exr5.1.6: "\chi(H)_k=\omega(H)_k+k" should be "\chi(H_k)=\omega(H_k)+k"
• p200 - Exr5.1.17: "\chi(G)\le4" should be "\chi(G)\le3"
• p203 - Exr5.1.44b: the missing quantity to be minimized is 1+r(D)
• p204 - Exr5.1.51: the attribution has been corrected, but still a hyphen between "k+1" and "coloring" was missing
• p206 - Thm5.2.3: "no two edges" should be "no two vertices" (Jozef Skokan)
• p212 - Thm5.2.20: The last sentence on the page should end "H'+xy" (JG)
• p216 - Exr5.2.17: drop "and that this bound is sharp" in part a. The bound is not always sharp; consider for example n=12 and m=63
• p216 - Exr5.2.22: "has a transmission range of six miles" should be clarified to "can transmit to other stations within a radius of three miles" (Andreas Eisenblaetter)
• p217 - Exr5.2.27: "m-vertex" should be "n-vertex" (Andreas Eisenblaetter)
• p222 - Thm 5.3.8: before "has" in the statement, it would be better to add "of a simple graph G"
• p224 - Exm5.3.13: "If we have colored v₁,...,v_i" should be "If we have colored v₁,...,v_i-1" (JG)
• p224 - after Remark 5.3.14: the cycles without simplicial elimination orderings are those of length at least 4, not 3 (David Piwinski)
• p229 - Exr5.3.4: "F" should be "H" (JG)
• p229 - Exr5.3.6: "graph" should be "simple graph"
• p243 - Exr6.1.5: The original statement was nonsense; one can make it a "prove or disprove"
• p265 - Exm6.3.17: In the definition of the example graph G, the number of copies of the complete graph should be n²/(2m)
• p271 - Exr6.3.15: should be restricted to simple outerplanar graphs
• p272 - Exr6.3.26: the formula for \nu(K_6,n) was wrong; the numerators should be n and n-1, not n-6 and n-7
• p272 - Exr6.3.28: "\nu(K_m,m)" should be "\nu(K_m,n)", and the condition (applied when m and n are odd) should be that m-3 and n-3 are divisible by 4, not 3
• p272 - Exr6.3.35: the edge bound applies only for simple graphs
• p280 - Thm7.1.16: "S_i,...,S₁n" should be "S₁,...,S_k", and there are unbalanced set brackets in the next line (JG)
• p283 - Exr7.1.13: The omitted "graph below" was the complement of the graph on the left in Exr7.1.1, and its line graph is that graph (L(G)=\bar{G})
• p285 - Exr7.1.30: "an k-regular graph" should be "a k-regular simple graph"
• p297 - Exr7.2.32: n must be greater than 2, and it is G' whose induced subgraph is K_n/2, not G (Jason Tedor)
• p305 - Lem7.3.10: The last paragraph shows that G contains subdivisions of the graphs obtained by contracting either side of the cut to a single vertex (JG)
• p315 - Exr7.3.9: "5" should be "3"; the icosahedron has only 12 vertices

Corrections for Chapter 8 IMPLEMENTED for the second printing

• p331 - top: the statement about Meyniel graphs was in the wrong place and therefore false. Delete "all Meyniel graphs or" from the first line of the second paragraph (Meyniel graphs *are* strongly perfect, as stated on p330). Add "does not contain all Meyniel graphs" to the first line of the third paragraph. (Andreas Eisenblaetter)
• p332 - Thm8.1.26: after "f(w_j)=j", append "for j\in{i+1,...,k}" (JG)
• p339 - Thm8.1.41: "\Chi(G-x) consisting" should be "(denoted \Theta(G-x)) consisting" (JG)
• p339 - Thm8.1.42: "S₂" should be "S'" (JG)
• p339 - Def8.1.43: "adding it" should be "adding an edge joining them" (JG)
• p341 - Thm8.1.48: at the end of the proof, "replace {v_(a-1)w,v_aw,v₁,v_w} with {v_(a-1)w+1,v₀,v_w-1}" should be "replace {v_(a-1)w+1,v_aw,v₁,v_w} with {v_(a-1)w+2,v₀,v_w-1}"
• p341 - Thm8.1.49: "exactly one of its endpoints" should be "at least one endpoint of A_x", and "Equality holds" should be "Equality holds (and no other arc contains both endpoints of A_x)" (Yaokun Wu)
• p343 - Thm8.1.51: "have the form v_i,v_i+w,...,v_i+aw" should be "have the form {v_i+jw: 1\le j\le a} (indices modulo aw+1)". Later, "v_(a-1)w+" should be "v_(a-1)w+1" (JG)
• p362 - Thm8.2.39: "B or B^*" should be "B or \overline B"; in next line, "I*" should be "I^*" (JG)
• p363 - before Def8.2.40: the characterization given for the acyclic subsets of E(G.e) requires that e not be a loop. The dual description should be phrased by saying that the spanning sets of G.e are those whose union with e is spanning in G
• p367 - Thm8.2.48: in the display in the center of the page, "\overline{X}+e" should be "\overline{X+e}" (JG)
• p373 - Exr8.2.10: The intersection and union symbols should be exchanged (Manish Sharma)
• p375 - Exr8.2.42: on the right side of the rank formula, "F" should be "\bar F" in both places
• p375 - Exr8.2.44: insert "is binary" between "matroid" and "if"
• p381 - middle: in "at least N incident red edges", "N" should be "s" (JG)
• p396 - Exr8.3.41: The reference to Exr2.1.37 should be to Exr2.1.40 (JG)
• p415 - Thm8.4.34, last paragraph: "F-decomposition of G" should be "F-decomposition of H" (JG)
• p416 - Thm8.4.35: In the third line of the proof, "e(G-x)≥m(n-2)/2" should be "e(G-x)>m(n-2)/2" (Linda Lesniak)
• p416 - Thm8.4.35: "would yield a longer cycle" should be "would yield a longer path", and "also has length l" should be "also has length l-1" (JG)
• p417 - Lem8.4.36, next-to-last paragraph on page: "G-v_t-1" should be "G-v_ti-1" (JG)
• p418 - Thm8.4.38: conclusion should end with "c(G) >= min{n(G),c}" (JG)
• p421 - Thm8.4.42: in the paragraph before the figure, each "v" with a subscript should be an "x", Also, "S-v_a+1" should be "S-{x_a+1}". In the left figure "x_a+c" should be "x_a+1". At the end of the next paragraph, "x_c-1" should be "x_a+c-1". Three lines before the end, "v_a+b belongs to at most m-c+b+2" should be "x_a+b belongs to at most m-c+b+1". (JG)
• p429 - Thm8.5.11: "n--X" should be "n-X" (JG)
• p432 - Thm8.5.18: the three instances of "G_p" should be "G^p"
• p446-7 - Lem8.5.36 statement, Exm8.5.37 display, and Exm8.5.38 two lines before display: the description of the event has an extra right parenthesis before the inequality(JG)
• p450 - Exr8.5.15: the upper bound in the comment applies only when k is even (Weiting Cao); the date for the reference is 1974
• p453 - first line: the reference to Corollary 8.2.42 should be to Corollary 8.2.37
• p453 - Rem8.6.2: "is the coefficient" should be "is the negative of the coefficient"; "that coefficient is also" should be "that also equals"
• p455 - Lem8.6.8: in the value of Av, "B_y" should be "By" (JG)
• p458 - Lem8.6.17: "R_n" should be "Rⁿ" (JG)
• p464 - Cor8.6.31: second line of proof was missing "(" (JG)
• p464 - before new section: "2\sqrt k-1(1-O(1/d))" should be "(2\sqrt{k-1}(1-O(1/d))", and "2{\sqrt k}-1" should be "2\sqrt{k-1}"
• p467 - in the figure on the right, the label "a" should be "x" (JG)
• p469 - Exr8.6.17: the reference to Exercise 2.2.11 should be to Exercise 2.2.13

The corrections below for Section 8.6 were noted in the first edition but were overlooked during revision.

• p455 - Thm8.6.9: In B, the statement applies to the nonzero eigenvalues. In C, there may also be an overall factor of \lambda (Gunnar Brinkman)
• p461 - Thm8.6.25: the last statement should be for nonconstant eigenvectors (Dan Pritikin)
• p468 - Exr8.6.12: "s" should be "x"
• p469 - Exr8.6.16: The eigenvalue lower bound on the chromatic number is due to Alan Hoffman, not Herb Wilf, in "On eigenvalues and colorings of graphs, in Graph Theory and Its Applications (B. Harries, ed.), Academic Press (1970), 79-91" (Joan Hutchinson)

Corrections for the Appendices IMPLEMENTED for the second printing

• p474 - RemA.12: in the diagram, the superscript "c" should be an overbar for complementation (JG)
• p483 - Functions, next line: It would be better to write "A function transforms elements of a set into elements of a possibly different set" (Chris Gordon-Smith)
• p494 - footnote: the last sentence should say that a function is bounded by a polynomial in n if and only if it is bounded by a polynomial in n² or n³ (JG). The word that precedes the footnote should be "input", not "problem"
• p497 - ExmB.2: the example given does not work. The correct example: Distinguish two vertices x and y. Put weight 0 on all edges not incident to these, weight 1 on all edges incident to exactly one of these, and weight n on the edge xy. For n\ge4, every cycle found by the nearest-neighbor heuristic has weight n+2, while the optimal cycles have weight 4.