``Introduction to Graph Theory'' - Updates

This page contains corrections and comments on the second printing of the first edition of Introduction to Graph Theory, by Douglas B. West. This page is no longer being fully maintained, since the second edition has appeared. Some errors in the first edition were not found and persisted in the second edition. Most of these have since been found and have been corrected in the second printing of the second edition; these are listed on the pages for the second edition. Any additional corrections found in the first edition that persist in the second edition will be posted on the web pages for the second edition. This page remains posted because it may be useful to readers who still have the first edition. Errors in the first edition that are submitted to west@math.uiuc.edu will be posted here, but errors found in the second edition will not automatically propagate back to this page if they were also errors in the first edition.

This page lists errors found in the second printing of the first edition. The list of changes made between the first printing and the second printing has moved to an auxiliary page. No changes were made between the second printing and the third printing. A few corrections were made for the fourth printing (I hope they were implemented).

Comment for students: This and auxiliary pages list many changes that are refinements rather than corrections. A student learning graph theory should consult this list only when some item in the book seems incorrect, to see whether there is a correction listed here. The discussion of refinements is intended for instructors and researchers.

Comment for instructors: I apologize profusely for making changes from first to second printing that were more than direct corrections of errors. Because the first printing persisted in the used book market, this caused classroom difficulties that I did not anticipate. Improvements should have waited for the second edition; I have learned my lesson! The second edition appeared in the Fall of 2000 and eliminated this difficulty. Future changes between printings of the same edition will not change content.

Other sections on this page include: Requests (for feedback), Changes not yet made, General changes made (in the second printing),

As always, I welcome all suggestions about how the book can be improved.

Changes Yet to be Made

Among this list, a few of the most pressing corrections were made for the fourth printing of the first edition; these are marked by *. The other items will be addressed in the second edition. Names in parentheses are the individuals who communicated the corrections. Chapter 1, Chapter 2, Chapter 3, Chapter 4, Chapter 5, Chapter 6, Chapter 7, Chapter 8, Backmatter.

Chapter 1

p5 - Students have difficulty understanding isomorphism-invariant properties defined using fixed vertex labelings. The first definition of path and cycle, occurring before the notion of isomorphism, will be changed to address this. In particular, a path is a graph whose vertices can be arranged linearly so that two vertices are adjacent if and only if they are consecutive in the list. Similarly define cycle using "arranged circularly".

p6 - 1.1.7: definition of adjacency matrix, like that of incidence matrix, should be restricted to loopless graphs to avoid distractions (communicated by Charles Delzell)

p7 - 1.1.10: this definition works only for simple graphs (communicated by Fred Galvin). Generalizing to all graphs by requiring preservation of edge multiplicity conflicts with the incidence definition of graph. If a graph is defined by its adjacency relation, then a 2-cycle has two automorphisms; if by its incidence relation, then a 2-cycle has four automorphisms (the latter seems to be the proper choice). We seldom discuss automorphisms of graphs with multiple edges, but in any case this annoyance will be clarified in the second edition

*p7 - 1.1.12: the second isomorphism is wrong; the two should be w,x,y,z to a,d,b,c and w,x,y,z to c,b,d,a

p8 - first line: notation for P_3 used before its definition (Charles Delzell)

p13 - Ex1.1.22: note comment about 2-cycles for 1.1.10 on p7 (communicated by Fred Galvin)

p14 - Ex1.1.27a: the claim requires n greater than 3 (communicated by Fred Galvin)

p14 - When we accept the intuitive and precise definition of path and cycle in Section 1.1, we can eliminate the mention of path and cycle in Def 1.2.1. Of the contexts in which we use the word "path", treating it as a special case of "walk" is the informal one, which becomes precise when we say "u,v-path".

p19 - 1.2.13: in the last line of the proof, V(G) should be V(H)

p20 - 1.2.17: The characterization of bipartite graphs first appears in K\"onig [1936]

p22 - 1.2.19: in the last sentence, "v" should be "u" (Alan Mehlenbacher)

p23 - top: the membership symbol in the first line should be containment (Alfio Giarlotta)

p23 - Ex1.2.10: for clarity, change to "exactly two places"

p24 - Ex1.2.17: for clarity, change to "exactly one place"

p25 - Ex1.2.26: this can be strengthened as follows - "Let P and Q be paths in a connected graph G in which the maximum length of a path is l. Prove that P and Q must have a common vertex if their lengths sum to at least 2l-1, of it they sum to 2l-2 and are odd." (Fred Galvin)

p25 - 1.2.28: the hypothesis can be weakened from k-regularity to minimum degree at least k (Fred Galvin)

p25 - the new exercise 1.2.29 should be restricted to loopless graphs

p26 - 1.3.2: italicize size when it is defined

p29 - 1.3.12: near the end, N(y) should be N(v) (contributed by Marios Mavronicolas)

p31 - 1.3.15: parenthesis after "Theorem 1.2.13"

p33 - 1.3.17: the reference to Ex1.3.36 should be to Ex1.3.35

*p36 - Ex1.3.6: should be restricted so that H has at least two vertices and G is loopless (Fred Galvin)

*p36 - Ex1.3.7: k at least 3 suffices

p38 - Ex1.3.27: assume that the graph is simple and has no isolated vertices (Fred Galvin). The construction request should be for infinitely many connected examples

p39 - Ex1.3.37: every simple connected graph that is not a complete multipartite graph has at least four vertices, so the hypothesis of having at least four vertices is not needed in part (b) (Alfio Giarlotta)

*p39 - Ex1.3.39: part (b) should refer to part (a)

p39 - Ex1.3.39: the (!) should be removed

*p39 - Ex1.3.40: here a is the floor of n/r, as in Ex1.3.39

p40 - Ex1.3.45: "connected" can drop from the hypothesis of part (a) (Fred Galvin). A hint to show that maximum degree is at least half n(G) will be added

p41 - 1.4.2: "has more neighbors" should be "has more edges to vertices" (Alfio Giarlotta)

p47 - Ex1.4.2: Delete the (-). Construction of a local maximum that is not a global maximum is not immediately obvious. Clarify that "when(ever)" means for any initial partition

p50 - Ex1.4.31: actually, there exists an n-vertex tournament in which every vertex is a king unless n is 2 or 4 (communicated by Radhika Ramamurthi)

p50 - Ex1.4.32: this should be restricted to loopless digraphs, since in a digraph with loops at all vertices there is no induced subgraph without edges (perhaps also designate (+))

Chapter 2

p55 - 2.1.9: parenthesis after d(u,x) needed to end sentence (Alan Mehlenbacher)

p60 - Ex2.1.21: due to A. Itai and M. Rodeh, Covering a graph by circuits, in Automata, Languages and Programming, Lect. Notes in Comp. Sci 62(Springer-Verlag, 1978), 289-299

p61 - 2nd printing Ex2.1.23: (reference needed) every n-vertex graph with n+1 edges has girth at most (2n+2)/3

p61 - Ex2.1.44: It seems that the reference should be to D. Burns and S. Schuster, Embedding (p,p-1) graphs in their complements. Israel J. Math. 30 (1978), no. 4, 313--320.

*p64 - 2.2.3: At the start of the ith step, there are n-i-1 entries remaining in a, not n-i

*p64 - 2.2.3: last paragraph, "label" should be "labels"

p64 - 2.2.3: next-to-last line is missing a ")" (Joel Miller)

p64 - 2.2.4: The statement should impose the restriction that the numbers {d_i-1} sum to n-2 (communicated by Alex Strehl)

p65 - After 2.2.6: in the last paragraph, the word "edge" appears too often

*p66 - 2.2.7: add the condition that e is not a loop (communicated by Pete Johnson)

*p67 - 2.2.11: the labels a and b in the figure should be switched

p68 - 2.2.11: "obtaining" in the first line of Step 3 should be "obtained"

p68 - 2.2.12-14: 2.2.12 does not specify that a branching or in-tree as a subgraph is spanning. The word "spanning" should be added to the statement of 2.2.13. It could also be added to 2.2.14 and 2.4.8, but there isn't room. (contributed by Dan Pritikin)

p70 - 2.2.19: a parenthesis is missing in \Delta(G); also reference needed for the characterization

p71 - Ex2.2.4: add hint - use the Prufer correspondence

p71 - Ex2.2.8: "bipartite sets" should be "partite sets", and "n-2 pairs" should be "n-1 pairs" (Charles Parry)

p71 - Ex2.2.10: change "Determine tau(Gn)" to "Let tn=tau(Gn). Find a recurrence relation for t1,t2,..."

p72 - Ex2.2.13: "vertex set [n] vertices" should be "vertex set [n]"

p73 - Ex2.2.28: (reference needed) up/down labeling of caterpillars

p78 - before 2.3.8: the reference to Ex11 should be to Ex13

p80 top - "among n" should be "among n items"

p81 - 2.3.15: "assignemnt" should be "assignment" (contributed by Seth Van Oort)

p82 - Ex2.3.3: "mimimum" should be "minimum"

p82 - Ex2.3.4-6: add the hypothesis that G is connected

*p87 - after 2.4.3: the case of Eulerian trail is k=1, not k=2 (Jean Rubin)

*p87 - 2.4.4: The present statement of Fleury's Algorithm allows one to traverse an edge to a leaf before finishing the rest of the graph. It should be changed to traverse a non-cut-edge unless the only incident edge is a cut-edge (Charles Parry)

p92-3 - 2.4.14 and after 2.4.15: "deBruijn" should be "De Bruijn" (Yaokun Wu). (Should "de Bruijn" be "De Bruijn" everywhere it appears?)

p95 - Ex2.4.7: the trail ends with the edge paired with it first edge, not with the first return to the first vertex

p95 - Ex2.4.8: part (c) should be restricted to at least three vertices. The entire problem should be restricted to graphs without isolated vertices (Joel Miller)

*p96 - Ex2.4.14: part (b) should be restricted to simple graphs

p96 - Ex2.4.17: "DeBruijn" should be "De Bruijn" (Yaokun Wu). (Should "de Bruijn" be "De Bruijn" everywhere it appears?)

p96 - Ex2.4.21: "Use Theorem 2.4.9"

p97 - Ex2.4.22: the proof suggested in the hint is fallacious. The proper hint is to show that the process terminates in the initial room, that every reached vertex has all incident corridors followed in both directions, and that every vertex is reached.

Chapter 3

p103 - 3.1.11: T\cupX-R should be T\cup(X-R), although since T and R are disjoint the resulting sets are the same

p107 - Ex3.1.15: the references for the Birkhoff-von Neumann Theorem are G. Birkhoff, Tres observaciones sobre el algebra lineal, Rev. Univ. Nac. Tucum\'an, Series A 5(1946), 147-151, and J. von Neumann, A certain zero-sum two-person game equivalent to the optimal assignment problem, Contributions to the Theory of Games II (ed. H.W. Kuhn), Ann. Math. Studies 28, Princeton Univ. Press (1953), 5-12

p108 - Ex3.1.25: the paper cited with the date 1996 is J. Liu and H. Zhou, Maximum induced matchings in graphs, Discrete Math. 170 (1997), no. 1-3, 277--281.

*p108 - Ex3.1.28: the trivial graph must be prohibited

p110 - 3.2.2: "marks all of x" should be "marks all of S"

p112 - 3.2.4: extra ``A'' in the definition

p113 - before 3.2.6: "we find a perfect matching" should be "we find a maximum matching"

*p114 - 3.2.7: the number of iterations is at most n^2 (the size of the matching can increase n times, since the algorithm is being applied to K_{n,n} (Tibor Szabo)

*p117 - 3.2.12: in the version of the algorithm stated, every woman says maybe until the moment when all assignments are made simultaneously. During this time all men also remain unmatched, and thus the first sentence of "Iteration" should be "Each man proposes to the highest woman on his list who has not previously rejected him." (Tibor Szabo)

p120 - Ex3.2.2: distinguish the three matrices to facilitate choosing only one as a homework computation

p129 - 3.3.11: the label x is missing from the graphs in the first picture, and the mention of vertex B after the picture should be U (Tibor Szabo)

p130 - 3.3.12: in the Iteration, the instances of "x" should be "v". Also, the decisions should depend on the membership of y in S, not the membership of w

p131 - Ex3.3.6: the second part holds for all regular graphs (Joel Miller)

p132 - Ex3.3.15: in part (b), f should be defined on V(G)

p132 - Ex3.3.16c: the necessity is the easy direction discussed in Chapter 1; sufficiency is here

Chapter 4

p140 - second line: "with connectivity 1" should be "that is not a single block" (Fred Galvin)

p141 - Ex4.1.3: the claim requires at least three vertices (communicated by Jing Huang)

*p142 - Ex4.1.11: restrict to simple graphs

*p142 - Ex4.1.15: the restriction should be that j+k is between 0 and n

p143 - Ex4.1.24: should be restricted to connected graphs (Fred Galvin)

p144 - Ex4.1.32: font error on D^*

p145 - 4.2.1: in the proof, it should be observed that if v lies on P or Q, then the cycle consisting of P and Q provides the desired pair of paths

p155 - Ex4.2.5: the claim requires order at least 3 (communicated by Jing Huang)

p155 - Ex4.2.11: Menger's Theorem should be allowed in this problem to avoid the use of induction>

p157 - Ex4.2.22: Tutte's characterization still holds when the k-split is restricted so that the new vertices have disjoint neighborhoods

p157 - Ex4.2.25: "the applying" should be "applying"

p157 - Ex4.2.28-29: in the usage here, "critically 2-connected" and "minimally 2-connected" have the same meaning

p158 - Ex4.2.31: in fourth line "|[X" should be "|[X,\Xbar]|"

p159 - 4.3.2: "asssigns" should be "assigns" (Rob Pratt)

p164 - 4.3.11: the verb after "departmental node" should be "sends" (Rob Pratt)

p167 - 4.3.14: The statement should restrict attention to p and q with equal sum, as mentioned in the discussion above (Gunnar Brinkmann)

p167 - 4.3.14: last reference to X in first paragraph should be Y (Garth Isaak)

*p171 - Ex4.3.13: the last summand should be deleted

p171 - Ex4.3.13: A nice addition: Prove that if [S,Sb] and [T,Tb] are minimum source/sink cuts in a network, then no edge between S-T and T-S has positive capacity

Chapter 5

p174 - 5.1.5: r should be restricted to be at least 2 (Chip Delzell)

p180 - Ex5.1.3: the parenthesis in the subscript before "=k+2" should be raised

p181 - Ex5.1.14: (reference needed) optimality of greedy coloring of P4-free graphs

p182 - Ex5.1.15: "x_i" should be "v_i" (Dan Pritikin)

p182 - Ex5.1.16: the conclusion should be the stronger statement that every subgraph whose vertices all have the same color has a vertex of degree less than r. This is needed for it to generalize the Szekeres-Wilf Theorem, which the published statement does not (Dan Pritikin)

p182 - Ex5.1.17: the exclusion of isolated vertices is unnecessary (Dan Pritikin)

p182 - Ex5.1.18: font errors on inequality sign and Erdos, last "G" should be omitted

p186 - 5.2.3: the statement requires order at least 2 (communicated by Jing Huang)

p187 - 5.2.8: in the statement, the inequality can be changed to equality (Dan Pritikin)

*p187 - 5.2.8: the reference to subgraphs G1,...,Gt should be to H1,...,Ht; also the cardinality sign on S should be deleted

p188 - 5.2.9: the second paragraph can be shortened by using Menger's Theorem. "Hence we may assume that H is 3-connected. Let xy be an edge in H. By Menger's Theorem, there are three internally disjoint xy-paths in H. We may take xy as one of these paths; combining the other two yields a cycle C with chord xy. Since H-x-y is connected, there is a shortest path P between the two portions of C in H-x-y. Now C U xy U P is a K4-subdivision. (Dan Pritikin) [If one wishes to avoid Menger's Theorem, still it is not necessary to exclude the case when V(C) induces a clique; simply start with nonconsecutive vertices u,v on C (Tibor Szabo)]

*p192 - Ex5.2.18: "G-S" should be "G"

p196 - 5.3.8 is due to H. Whitney, A logical expansion in Mathematics, Bull. Amer. Math. Soc. 38 (1932), 572--579.

p199 - 5.3.13 is due to G.A. Dirac, On rigid circuit graphs. Abh. Math. Sem. Univ. Hamburg 25(1961), 71--76

*p204 - Ex5.3.17 is egregiously in error. It is not true that statement A implies statement B, and the exercise should be changed to request a counterexample

p205 - Ex5.3.22: add "the" before "length" (Rob Pratt)

Chapter 6

p215 - Ex6.1.5: it should be assumed that G has no isolated vertices (Tibor Szabo)

*p215 - Ex6.1.7-8: restrict to simple graphs

p216 - Ex6.1.19: the assumption that H has an edge is needed

*p217 - Ex6.1.23: in the denominators, "\Delta" should be "\Delta+1", and it should be specified that the edge-coloring is proper (Radhika Ramamurthi, Linda Lawton, Ramamoorthi Ravi, etc.)

*p217 - Ex6.1.25: in part (c), the graph G must be regular with degree at least 2

*p217 - Ex6.1.26: the 1/2 in Ore's bound applies to the degree sum

p218 - Ex6.1.28: the reference to Exercise 26 should be to Exercise 27.

p219 - 6.2.2: "set S\esub V" should be "nonempty set S\esub V(G)"

p224 - 6.2.11: in the figure, the subgraph labeled tK_1 should be labeled iK_1

p224 - after 6.2.12: Hilbig [1986] improved the results of Jackson and Zhu-Liu-Yu: Except for the Petersen graph and the graph obtained from it by expanding one vertex to a triangle, every 2-connected, d-regular graph with at most 3d+3 vertices is Hamiltonian, for d at least 3 (F. Hilbig, Kantenstrukturen in nichthamiltonischen Graphen, Dissertation, Techn. Univ., Berlin, 1986.) (contributed by Robert Pratt)

p227 - Ex6.2.4: must restrict to n greater than 1

p228 - Ex6.2.17: the reference to 6.2.2 should be to 6.2.3

p239 - middle: "SATISFIABILTY" should be "SATISFIABILITY"

p242 - 6.3.9: "G" should be "D"

p242 - 6.3.10: "z1" should be "z₁", and "tak" should be "take"

p243 - 6.3.10: closing brace missing on definition of S and at end of preceding paragraph

p243 - 6.3.11: the first "G" should be "D"

p244 - 6.3.12: the gadget shown is not correct, as it does not permit the four corners to have the same color. The correct gadget has four fewer edges and appears on p88 of Garey and Johnson, Computers and Intractibility (1979). The statement about unique colorability is nonsense for the correct gadget and would make the proof fail; the four terminals can have the same color (contributed by Dmitrii Pasechnik)

p244 - 6.3.12: "edge u,v" should be "edge uv", and the final "G" should be "G'"

Chapter 7

*p255 - 7.1.17(2): this should read "Contracting a non-loop edge of G has the effect of deleting an edge in G*. Similarly, deleting a non-cut-edge of G has ..."

*p256 - 7.1.18: the reference to 7.1.8 should be to 7.1.11

*p256 - 7.1.20: the reference to 7.1.17 should be to 7.1.18

p258 - Ex7.1.12: add the hypothesis that G is connected

p258 - Ex7.1.14: the statement makes sense only when k is at least 2 (contributed by Steve Kilner)

p261 - 7.2.4: "x,y-path H2" should be "x,y-path through H2"

*p263 - 7.2.7: in order to avoid technical difficulties, it is necessary to load the induction hypothesis to produce a convex embedding with no three vertices placed on a line (Jean-Marc Lanlignel)

*p263 - 7.2.7 bottom: "six edges" should be "seven edges", and "y has two u,v in C" should be "y has two neighbors u,v on C"

*p265 - 7.2.10: The input is a 2-connected graph, which may or may not be planar

*p268 - Ex7.2.6: Fary's Theorem is for simple planar graphs

p270 - line -8: "aspects" should be "aspect" (Jing Huang)

*p280 - 7.3.9: the bounds stated for the crossing number of K_{m,n} should be modified as follows - in the upper bound, replace n-2 with n-1; the lower bound should be [m(m-1)/5]\floor{n/2}\floor{(n-1)/2} (Scott Clark)

*p283 - Ex7.3.2: the problem should be restricted to connected plane graphs (Ramamoorthi Ravi). To avoid the technicality of graphs with no proper face-colorings, it may be worthwhile to strengthen the hypothesis to 2-edge-connected (Zevi Miller)

*p283 - Ex7.3.6: The comment "every Eulerian triangulation except K_3 has even order" is false; such graphs exist whenever the order is a multiple of 3. The hint should be "choose an appropriate pair or triple of adjacent vertices to delete and triangulate the resulting hole"

*p274 - RSST simplified the proof of the Four Color Theorem; they did not check the original proof in full by hand

*p274 - 7.3.3: statement should be for "plane graph", not "planar graph" (Jing Huang)

*p275 - 7.3.3: parenthesis missing after "color b", and "H3" should be "H2"

p276 - 7.3.5: designation "Example" missing

*p277 - 7.3.5: "f'3+f''3" should be "f'4+f''4", and "is +1" should be "is -1"

*p277 - Tutte's Conjecture on 3-edge-coloring is for 2-edge-connected graphs, not just 2-connected graphs

*p285 - Ex7.3.17: This is the smallest such graph when the omitted hypothesis of 3-connectedness is included (contributed by Frank Arnold)

p286 - Ex7.3.20: decompositions of the join of C5 and K6 into two planar graphs are hard to find; revision will present two unlabeled planar graphs and request a proof that their union is that join

*p287 - Ex7.3.27: statement of lower bound needs correction; see correction to p280.

*p287 - Ex7.3.29b: parenthesis after K_3,3,1 should be raised. In part d, the hint has an extra "one" and extra "of" (contributed by Robert Pratt)

*p287 - Ex7.3.31: "A embedding" should be "An embedding"

Chapter 8

p294 - Thm8.1.8: The meaning of the labels in the host tree in the figure should be explained in the proof (Yaokun Wu)

p295 - Exm8.1.10: "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)

*p297 - 8.1.14: In the figure, deh is not a maximal clique

p298 - 8.1.17: The chordal-cocomparability characterization is due to Gilmore and Hoffman [1964]. The clique-vertex incidence matrix characterization is due to Fulkerson and Gross [1965]

p302 - 8.1.22: Yaokun Wu has suggested an improvement to the proof that does not require the observation that mapping w to w* defines a permutation; it only needs w\ne w*. In obtaining the obstruction, start with v being the last in L among the vertices of Q. Now set a=p(v*), b=v*, c=v, d=p(b*). The simplification is that one applies only the * operation, not its inverse.

p304 - 8.1.26: the second claim is not true. Identification at star-subgraphs cannot produce a minimal imperfect graph, but it can produce an imperfect graph. For an example, identify a P_3 from C_4 with two appropriate edges in C_5+e (Tom Shermer)

p305 - intro: the discussion is for odd cycles of length at least 5 and their complements (Jing Huang

p307 - Exm8.1.33: 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

p308 - 8.1.36: all of the constant vectors of 1s in the last line of the page should have a transpose indication on them (Yaokun Wu)

p338 - 8.1.36: The proof that G has no other maximum cliques can be simplified; one does not need to compute A^-1 to show that t is a 0,1-vector with one 1. Multiplying q=tA on the right by 1_n shows that t sums to 1. Now qB^T=qA^-1(J-I)=t(J-I)=tJ-t=1_n-t. Since qB^T is a 0,1-vector, also t is a 0,1-vector. Since t sums to 1, it has a single 1, and q is a row of A. (Yaokun Wu)

p313 - 8.1.46: "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)

The suggestions by Yaokun Wu will be implemented in the third edition

p325 - 8.2.14: "Lemma 1.2.17" refers to "Proposition 1.2.18" (Garth Isaak)

p342 - 8.2.50: cardinality signs are missing on N(Y) (Stephan Brandt)

p354 - 8.3.2: delete "(" from "(In" (Rob Pratt)

p355 - 8.3.5: "accomodated" should be "accommodated" (communicated by Rob Pratt)

p358 - after 8.3.8: mentioned exercises 11-13 are not present

p359 - further improvements to bounds in the table: R(4,7)<=61, R(4,8)<=84, R(4,9)<=115, R(5,9)<=316 (Rob Pratt)

p362 - Stefan Brandt has disproved the conjecture of Burr and Erdos [1983]: for every nonbipartite graph H (such as Kn) and real number h there is a threshold d0 such that R(G,H) > h n(G) for almost every d-regular graph G if d>= d0

p365 - 8.3.17: 3rd par "avoids" should be "that avoids" (contributed by Alan Mehlenbacher)

p369 - Ex8.3.4: (reference needed) pigeonhole/key problem

p369 - Ex8.3.12: "An" should be "A" (Rob Pratt)

p371 - Ex8.3.30: "monchromatic" should be "monochromatic" (communicated by Rob Pratt)

p373 - Ex8.3.41c: second "a_n" should be "b_n" (Garth Isaak)

*p375 - 8.4.3: the statement that Q appears earlier than xy when N(y) contains V(Q) is incorrect. Nevertheless, since Q and xy are maximal when chosen, some clique Q' preceding both contains an edge vy with v in V(Q). The proof then proceeds as before. (Communicated by Troy Barcume, who with his advisor has proved that every greedy clique decomposition has order-sum at most (11/20)n(G)^2)

p382 - 8.4.18: the proof that e_W is at least k overlooks the edges between U-W and W-U. One should start with the submodularity inequality e_W+e_U \ge e_{W\cap U}+e_{W\cup U}, which yields the stated equality with equality replaced by inequality in the desired direction. From there the argument continues as stated in the text. Also the date on the Tarjan reference is actually 1974/75; I presume this means that it appeared in 1975. (Shimon Even)

p387 - near bottom: "Stivnik" should be "Slivnik" (Anthony Hilton)

p389 - before 8.4.28: A 63-vertex planar graph that is not 4-choosable appears in M. Mirzakhani, A small non-4-choosable planar graph. Bull. Inst. Combin. Appl. 17 (1996), 15--18. The proof will be requested as a guided exercise.

*p397 - 8.4.36: The conclusion for the circumference should be "min{c,n(G)}"

*p403 - Ex8.4.30: strict inequality is needed for at least one vertex in each component, so it is best to require G to be connected (communicated by Fred Galvin)

p404 - Ex8.4.35: the first claim requires simple graphs (communicated by Jing Huang)

p418 - 8.5.22 and before: accents missing on "Bollobas"

p430-431 - references needed for most exercises in Section 8.5

p433 - 8.6.2: the sum of the eigenvalues is the Trace, not the negative of the Trace (Tibor Szabo, Dan Pritikin)

p433 - 8.6.3: "\lambda²" should be "\lambdaⁿ"

p434 - second full paragraph: the sum should go to n, not n-1 (Dan Pritikin)

*p434 - 8.6.4: In the theorem statement, c(H) should be s(H)

p436 - 8.6.8: The statements of B and C need to be cleaned up somewhat to account for bipartite graphs of odd order (Gunnar Brinkman)

p437 - after 8.6.10: "fuctions" should be "functions"

p439 - 8.6.15: "Let z' be a unit eigenvector" (in case of multiple eigenvalues) (Dan Pritikin)

p442 - 8.6.20: clearer statement of theorem - "Every eigenvalue of a graph with maximum degree k lies in the interval [-k,k], and the multiplicity of k as an eigenvalue is the number of k-regular components"

p443 - 8.6.23: the statement needs a slight correction, excluding multiples of the constant eigenvector for the second case: "If a simple graph G is k-regular, then G and \Gbar have a common orthonormal basis of eigenvectors. The eigenvalue associated with 1_n is k for G and n-k-1 for \Gbar. If x is another vector in the basis, associated with eigenvalue \lambda for G, then its associated eigenvalue for \Gbar is -1-\lambda." (Dan Pritikin)"

p444 - 8.6.26: The statement should also say that G has n vertices

p445 - 8.6.27: in the third line, a closing parenthesis is missing (Stephan Brandt)

*p446 - 8.6.28: the smallest eigenvalue of kI-A is 0

*p446 - 8.6.29: open parenthesis missing

p448 - 8.6.36: the reference to 8.6.30 should be to 8.6.31

p449 - 8.6.37: "is be" should be "must be"

p450 - Ex8.6.7: "mn" should be "n(G)n(H)"

p450 - Ex8.6.9: "s^4" should be "x^4"

p451 - Ex8.6.12(b): the eigenvalue lower bound on the chromatic number is due to Alan Hoffman, not due to Herb Wilf (communicated by Joan Hutchinson)

Backmatter

p489 - McKee's paper begins on 237, not 327 (Jing Huang)

p491 - Pritikin's paper appeared in 1994

p492 - Reznick reference has an extra "t" in "Decomposition"

p492 - first Robertson et al has punctuation errors (these three corrections contributed by Robert Pratt)

p507 - the item "hypercube" was omitted from the index in this printing (Jing Huang)

General Changes made for Second Printing

In order to make the book easier to use as a text, I have displayed more equations to improve readability, eliminated duplicate terminology to reduce confusion, clarified definitions to speed learning, expanded terse explanations, corrected errors in problem statements, added missing references, etc. Numbering of pages and items remains mostly unchanged - this is a corrected printing, not a second edition. The next section lists changes such as correction of typographical errors and cross-references; here I describe larger changes.

Definitions - "Graph", "loop", and "multiple edge" are now defined before "simple graph", so that simple graph is a special case of graph. Hence the word "multigraph" is essentially banished (technically, I had given it the same definition as "graph"). This usage is consistent with Bondy/Murty, though not with most recent texts. In some contexts, it is then helpful to declare all graphs to be simple; I do this in the chapter on vertex coloring, for example. "Loopless graph" allows multiple edges but not loops.

Finiteness - The restriction of the book to finite graphs (with rare explicit exceptions) is now more prominent, in bold type on p2 and repeated in Section 1.2. The condition "finite" is thus eliminated from the statements of results and exercises where it was a distraction. This also eliminates uncertainty about results and exercises that did not state the convention.

Elimination of alternative terminology - I had used "complete matching" and "perfect matching" interchangeably. I have now changed the instances of "complete matching" to "perfect matching" to eliminate confusion with "complete matching of X into Y". I have also dropped the word "undirected" (except when making direct contrast with digraphs), since in this book "undirected graph" means "graph" (and since digraphs are less central).

Menger's Theorem (p149-152) - completely rewritten. I start with the local vertex version for graphs and digraphs simultaneously, proved from K\"onig-Egerv\'ary (as in the final pre-publication edition). The local edge versions follow using line graphs. I have deleted unnecessary terminology like "local connectivity" and "path-multiplicity". In 4.2.19, I have added proof for the statement that \kappa(G-xy)>=\kappa(G)-1.
-------Although the initial proof is slightly longer with this approach, the main idea is easier to visualize. Also, it uses the earlier min-max relation to good effect, the use of the line graph is worthwhile, and the overall presentation is more efficient, permitting the addition of an explicit example. Consequences include changing the remarks after Theorem 4.3.9 (p163) and adding details about the relationship between Menger's Theorem and the Ford-Fulkerson Theorem (p164-165).