Introduction to Graph Theory - Second Edition

by Douglas B. West

Typos Page

This page lists minor typographical errors in the text. Items in this list include misspellings, errors in punctuation, clarification of wording, etc. These errors are very minor and don't interfere with understanding of the text; they are listed here so that further readers need not duplicate effort by sending them in.

Contributors names appear in parenthesis. In particular, "JG" denotes John Ganci, who has read the book amazingly carefully. Please send contributions for this page to west@math.uiuc.edu.

Related pages

• Corrections (typos in notation, omissions from mathematical statements, etc.)
• Comments and updates (corrections to references, comments on proofs or exercises, etc.)
• Supplementary Exercises (to be added in later editions)
• Index page for Introduction to Graph Theory
• Index page for Math 412

Minor corrections being IMPLEMENTED for the fourth printing

• p94 - Exr2.2.31: delete hyphen in last word
• p96 - Thm2.3.3: "It T=T^*" should be "If T=T^*" (Gerard Chang)
• p104 - Exr2.3.8: "minimum spanning" should be "minimum-weight spanning"
• p109 - Def3.1.6: "enpoints" should be "endpoints" (JG)
• p160 - Exr4.1.29: clarification - "Prove that a spanning subgraph H of a connected graph G is a spanning tree of G if and only if G-E(H) contains no bond of G and adding any edge of H to it creates a subgraph of G containing a bond of G."
• p160 - Exr4.1.34, 36, 37: these are related to material marked optional and hence should be marked with (*) (JG)
• p163 - Cor4.2.6: near the end, '"' should be a closing double quote mark (JG)
• p173 - Exr4.2.8: "triple" should be "ordered triple" for clarity
• p173 - Exr4.2.13: "(!)" deleted!-->
• p270 - Exr6.3.5: "Prove" should be "Use the Four Color Theorem to prove"
• p270 - Exr6.3.12: add "for all" quantifier on n in construction
• p296 - Exr7.2.13: ", matching" should be "and then matching"
• p551 - Hall: "representation" should be "representatives" (Robert Jamison)

Typos found since the second printing (or postponed)

• p505 - ExrB.6b: "Prove the" should be "Prove that"

Subsequent items on this page were corrected in the second printing of the second edition EXCEPT for those in this section. Corrections listed in this section have not yet been made.

• p.xviii - contents: the section on Euler's Formula starts on 241, not 241 255 (Will Mitchell)
• p.x - contents: Appendix F starts on page 537, not 567 (Greg Morris)
• p19 - top: "We also we" should be "We also" (Vitaly Voloshin)
• p48 - Exr1.3.6: "the those" should be "those"
• p52 - Exr1.3.54a: delete "triangles"
• p65 - Exr1.4.27: "DeBruijn" should be "De Bruijn" (Yaokun Wu). (Should "de Bruijn" be "De Bruijn" everywhere it appears? When it appears without a first name, yes.)
• p81 - below figure: "Renyi" should be "Rényi", which may be the reason why this mention of Rényi is not in the author index (Fred Galvin)
• p116 - Exr3.1.25: "transitter" should be "transmitter" (JG)
• p119 - Exr3.1.12: the reference (missing from the bibliography) is Tao Jiang, "Short even cycles in cages with odd girth" Ars Combinatoria 59 (2001), 165--169.
• p119 - Exr3.1.13: the bold and solid edges should be switched (JG)
• p119 - Exr3.1.17: "words" would be better as "vertices" (JG)
• p119 - Exr3.1.19: The union symbol should be \bigcup (Jerry Grossman)
• p120 - Exr3.1.26: the date should be 1994, not 1997 (Fred Galvin)
• p131 - before Alg3.2.17: "this importance" should be "the importance"
• p132 - first line: "whomever proposed" should be "whoever proposed" (Jerry Grossman)
• p148 - Exr3.3.29: "For are" should be "For", and S,T\subset V should be S,T\subseteq V(G)
• p153 - Exm4.1.10: "arbitarily" should be "arbitrarily" (Richard Callahan)
• p157 - top: "breath-first" should be "breadth-first" (Fred Galvin)
• p157 - Alg4.1.23: "V(H)" should be "V(G)" in the initialization (JG)
• p170 - Thm4.2.23: "Given k-connected graph" should be "Given a k-connected graph"
• p254 - Thm6.2.19: "extendable" should be "extendible" (here and elsewhere)
• p279 - Rmk7.1.12: final ")" missing; "large enough" should be "a large enough fraction of n(G)"
• p284 - Exr7.1.22: "Use" should be "Apply"
• p294 - before Def7.2.21: "subtantially" should be "substantially" (Candida Nunes da Silva)
• p303 - Exm7.3.6: "having having" should be "having" (Candida Nunes da Silva)
• p326 - bottom: the date on Corneil-Olariu-Stewart needs updating (JG)
• p379 - top line: "that assume" should be "assume that" (Candida Nunes da Silva)
• p449 - Exr8.5.12: "the probably" should be "the probability"
• p469 - Exr8.6.18: "times the matrix" should be "times the determinant of the matrix"
• p500 - middle: "many, NP-completeness" should be "many NP-completeness" (David Norris)
• p510 - hint2.1.27: "sufficiency" should be "sufficient"
• p534 - Tutte: title should be italicized (Jerry Grossman)
• p548 - Gardner: missing end parenthesis (JG)
• p577 - connected graph: "5" should be "6" (Fred Galvin)
• p577 - connection relation: "59, 63" should be "60"
• p580 - group: item ends with a comma (JG)

Minor corrections for Chapters 1-7 IMPLEMENTED for the second printing

• xviii - top: "increased emphasize" should be "increased emphasis" (JG)
• p1 - Exm1.1.1: there was only one island, called Kneiphopf
• p8 - Rem1.1.23: "such each edge" should be "such that each edge" (JG)
• p31 - Exr1.2.12: "an procedure" should be "a procedure"
• p40 - before Thm1.3.19: spaces are needed in "induction,contradiction", "bipartitesubgraph", and "ar-erelated" (JG)
• p49 - Exr1.3.16: both "an k" should be "a k" (JG)
• p49 - Exr1.3.22: "G" should be "G"
• p65 - Exr1.4.36: the "n" in part (c) refers to the number of vertices
• p73 - Thm2.1.14: "among n-vertex tree" should be "among n-vertex trees" (JG)
• p74 - before figure: spaces needed in "followthe", "egythat", and "contextof" (JG)
• p77 - Exr2.1.41: "Chen-Jacobson-Lehel-Shreve [1999]" should be "Chen-Lehel-Jacobson-Shreve [1998]" (JG)
• p82 - Thm2.2.3: "There is tree" should be "There is one tree (JG)
• p87 - Thm2.2.12, Step 3: "summ" should be "sum" (JG)
• p91 - Thm2.2.28: "alond e" should be "along an edge e" (JG)
• p108 - Exm3.1.3: "change the order" should be "changing the order" (JG)
• p119 - Exr3.1.18: "Player 1 start" should be "Player 1 starts"
• p129 - Thm3.2.11: delete ending ")"
• p138 - Rem3.3.4: "has a 1-factor exists" should be "has a 1-factor" (JG)
• p138 - before Def3.3.6: "\alpha'(T)" should be "\alpha'(G)" (JG)
• p147 - Exr3.3.21: period missing at the end of the first sentence
• p150 - before Exm4.1.3: "cutvertex" should be "cut-vertex" (Jason Tedor)
• p150 - Exm4.1.3: "2)." should be "2." (Jason Tedor)
• p155 - Prop4.1.15: "minimal disconnecting set" should be "minimal edge cut"
• p165 - Rem4.2.12: "set of edge" should be "set of edges" (JG)
• p169 - Thm4.2.19: For consistency, "ty" should be "yt" (JG)
• p176 - Exm4.3.3: "Each capacities are" should be "Capacities are"
• p182 - after Rem4.3.14: "??" is a reference to the proof of the Ford-Fulkerson CSDR Theorem via network flow; this had been an exercise but was removed for lack of space and may return in a later edition (JG)
• p184 - before SUPPLIES: The exercise range beginning with 5 was to end with the CSDR exercise mentioned above, between 7 and 8 (JG)
• p185 - before Thm 4.3.18: after "bigraphic", the reference should be to Exr1.4.32; also the reference to Exr3.3.28 should be to Exr3.3.29 (JG)
• p195 - Exm5.1.15: "we we" should be "we" (Andreas Eisenblaetter)
• p204 - Exr5.1.51: "an k-colorable" should be "a k-colorable"
• p206 - Rem5.2.4: "[1981])" should be "[1981]" (Jason Tedor)
• p212 - Def5.2.19: the reference to 5.2.19 should be to 4.2.5 (JG)
• p214 - Rem5.2.24: in the next to last line, "has with" should be "has" (JG)
• p217 - Exr5.2.23: "acheiving" should be "achieving"
• p217 - Exr5.2.26: missing ".)" at the end
• p219 - Exm5.3.2: there are two extra right parentheses in the first line (JG)
• p225 - Lem5.3.16: statement of lemma lacks a period at the end
• p230 - Exr5.3.19: "Compute" should be "compute"
• p231 - Exr5.3.24: "a edge" should be "an edge"
• p240 - Prop6.1.18: add "of" between "face" and "a" (JG)
• p240 - Prop6.1.20: induction step should be n > 4
• p242 - App6.1.28 bottom: "that satisfying" should be "that satisfies" (JG)
• p263 - Thm6.3.14: third line missing ")" after "K_n-1 (JG)
• p264 - before Thm6.3.16: missing space in "11and" (JG)
• p271 - Exr6.3.15: Akiyama-Era-Gervacio should also include Watanabe
• p294 - Thm7.2.22: near the end, space missing in "withthe" (JG)
• p308 - Prop7.3.20: "The X" should be "Let X" (JG)
• p309 - Thm7.3.22: "look and face" should be "look at face" (JG)
• p311 - before Conj7.3.28: "describing of" should be "discussing" (JG)

Minor corrections for Chapter 8 IMPLEMENTED for the second printing

• p332 - Thm8.1.26: after "f(w_j)=j", append "for i < j\le k" (JG)
• p339 - Thm8.1.42: The "illustration above" refers to the illustration below
• p341 - Def8.1.47: change "K_1,3-free graph" to "claw-free graph (Definition 1.3.22)" (JG)
• p359 - Thm8.2.27: in the definition of strong elimination, add the parentheses in "(C₁\cup C₂)-e". In the proof that T implies C', the first parenthesis in this formula is backward
• p361 - Lem8.2.32: delete end parenthesis (JG)
• p365 - Thm8.2.44: "subdivision K₅" should be "subdivision of K₅" (JG)
• p369 - end of section: "??s-" is a reference to exercises that have moved to Appendix B; the sentence should have been removed
• p428 - Thm8.5.9: "uniformaly" should be "uniformly"
• p443 - bottom-1: "a random variables" should be "a random variable" (JG)
• p445 - bottom-3: "points are list" should be "points are lists" (JG)
• p463 - after Def8.6.29: "(Pinsker [1973])" should be "(Pinsker [1973]" (JG)
• p463 - bottom-6: "expasion" should be "expansion" (JG)

Minor corrections for the Appendices IMPLEMENTED for the second printing

• p473 - RemA.10: "definining" should be "defining" (JG)
• p476 - RemA.17: "ends of sentence" should be "ends of sentences" (JG)
• p494 - display: spaces are needed around each "for", and the colon in the last line is incorrectly set (JG)
• p498 - Theorem B.4: "spanning tree. As" should be "spanning tree, as" (JG)
• p499 - before figure: "This tells use" should be "This tells us" (JG)
• p503 - after figure: "{z_r} Since" should be "{z_r}. Since" (JG)
• p503 - bottom-3: "visit traverse all sequences" should be "traverse all paths" (JG)
• p508 - third parg: remove "|-" (JG)
• p509 - Hint1.2.15: should be "What happens when a vertex repeats?"
• p509 - Hint1.3.57: "paradigm" should be "template"
• p510 - Hint1.4.23: should be "Show that if an orientation is not balanced, then a change can be made to reduce the imbalance
• p511 - Hint3.2.11: "some women" should be "some woman"
• p511 - Hint3.3.19: "Petersen's Theorem should be "Theorem 3.3.9"
• p514 - add Hint6.3.19: Show that the union of these two graphs is C5 join K6
• p533-536 - Many words in the book titles should be capitalized
• p537-568 - Some author lists were missing a comma; this has been corrected only when the page needed to be changed for another reason
• p540 - Bondy-Chvatal: also cited on page 290 (JG)
• p540 - Bondy-Murty: also cited on page 311 (JG)
• p554 - Kelmans [1983]: extra period after "Syst"
• p554 - Kierstead [1992]: "Lov/'asz" typo (Jason Tedor)
• p566 - Tutte [1961a]: add reference to page 372 (JG)
• p567 - Wagner [1937]: add reference to page 363 (JG)
• p574 - Wang J: should be Wang J 396 and Wang D.L. 52 (Yaokun Wu)
• p574 - Watanabe: should refer to p271