``Extremal Graph Theory (TAC: Vol. I)'' - Typos

This page lists the typographical errors that have been discovered in the Spring 2004 pre-publication version of Extremal Graph Theory, by Douglas B. West (Volume I of The Art of Combinatorics). This page is of interest only to the few persons having a copy of this draft, such as the students in my course and possibly reviewers. Please send any additional contributions to west@math.uiuc.edu. Contributors noted in parentheses, with "RZ" denoting "Reza Zamani".

Mathematical Errors and/or Typos

p2 - top: Since our initial model has the edge set being a subset of the unordered pairs of vertices, making the vertex set finite also forces the edge set to be finite (RZ)
p72 - Thm1.2.30 (second parg of page): "w_i" should be "w'" twice (RZ)
p74 - Thm1.2.30 (last parg of proof): missing "}" after "d(u,z)=s" (RZ)
p75 - second line: missing ")" after "(G(n; s₁,...,s_k)" (RZ)
p80 - Exr1.2.48: this exercise is nonsense; the correct exercise is at 1.2.43
p81 - intro: "u,v\in V(H)" should be "u,v\in V(G)" (RZ)
p82 - Exm1.3.3: since i < j is specified, we can simplify min{i,j} to i and max{i,j} to j (RZ). Note also that the uses of i and j in the final line should be r and s
p86 - Thm1.3.11: at the beginning of the case i\notin P_j, "f_i(k),f_j(k)" should be "f_k(i),f_k(j)" (RZ)
p109 - Thm2.1.5: "s" is used before being defined; replace with "|S|" (RZ)
p115 - Thm2.1.17: "N(x),N(y)-bipartite graph" should be "N(x),N(y)-bigraph"
p117 - Thm2.1.22: the universes for i and j at the end of the first sentence of the proof should be "[m]", not "m" (RZ)
p135 - Exr2.1.31: "X,Y-bipartite graph" should be "X,Y-bigraph"
p137 - Exr2.1.50: "X,Y-bipartite graph" should be "X,Y-bigraph"
p176 - Lem2.3.9: in the first line after the display in the proof, "f(T)" should be "f(Q)" under the summation (RZ)
p181 - Thm2.3.13: in the last paragraph, "nonadjacent to u" should be "nonadjacent to x", "uv,xw" should be "xy,zw", and "uw,xv" should be "xw,zy" (RZ)
p187 - beforeThm2.3.23: "S(V) that is bounded" should be "S(v) that is surrounded"
p188 - Exr2.3.4-6: "graph" should be "multigraph"
p197 - Thm2.4.17: "l+(p+m)2" should be "l+(p+m)/2" (RZ)
p198 - before Def2.4.18: "\Delta\le 3" should be "\Delta=3", and the paragraph should en with "for 3-regular graphs" (RZ)
p201 - Claim 4, 3rd paragraph: "N(X)" should be "N(x)", and "u,v,w,z,y" should be "[u,v,x,z,y]" (RZ)
p205 - Thm2.4.27: "S\cup{x,y}" should be "(S-N(y))\cup{x,y}"
p207 - Prop2.4.33+: the proposition that digraphs with no even cycle have at most one kernel is being added
p209 - Thm2.4.37: Statement should be "The vertex set of any multigraph can be expressed as the union of two disjoint sets that each induce an even subgraph." In the last paragraph of the proof, the copies of "G'[V₁]" should be "G'[V'₁]" and "G'[V'₂]", and the last "|V₁\cap S-v|" should be "|V₂\cap S-v|" (RZ)
p205 - Thm2.4.27: "S\cup{x,y}" should be
p212 - Exr2.4.33: the dominator of the last formula should be the floor of k/2
p224 - Prop3.1.18: "(" missing in first formula of proof
p225 - Thm3.2.10: some instances of "S_k-1" and "C_k-1" should be "D_k-1" and "C_k-1"
p227 - Thm3.1.24: "(r-1)t+1" should be "(r-1)t" (RZ), and "\Delta_i" should be "D_i"
p239 - Exr3.1.58: "s. Prove" should be "s}. Prove"
p239 - Exr3.1.60: "monotone family" should be "monotone additive family" (Kevin Milans)
p244 - Exm3.2.5: the binomial coefficient "kn\choose n" in the figure should be "N\choose r"
p250 - Lem3.2.17: "on its neighborhood" should be "on N(w)", and the second circle in the figure should be labeled "G₁", not "G₂" (RZ)
p266 - before display: "\mu(x,v)}" has excess brace (RZ)
p268 - Thm3.3.13: end: "d(z)+\mu(y,z))" has excess parenthesis (RZ)
p269 - Thm3.3.15: "Kierstead [1984)" should be "Kierstead [1984])" (RZ)
p270 - Thm3.3.15: following the nonmembership sign, the "x_i+1" or "x_m" should be enclosed by "D( )" (three times). Also, a parenthesis ")" is missing in the penultimate line of the proof (RZ)
p276 - Exr3.3.22: "K₂m" should be "K_2m"
p282 - Thm3.4.9: "connected" should be drop from the hypothesis, and the proof of sufficiency, which was described in class, seems to have been omitted from the text
p286 - Thm3.4.13: two instances of "bounded by" in the last paragraph of the proof should be "less than"
p320 - Rem3.5.31: "2+1/t-colorable" should be "(2+1/t)-colorable"
p340 - Lem4.1.16: "If and S" should be "If S"
p341 - Thm4.1.17: "B_j" should be "Q_j" in six places
p380 - Thm4.3.12: "contributes one" should be "contributes 1" twice
p389,390 - Thm4.3.34: "Lemma `treed'" should be "Lemma 4.3.25"
p424 - Thm4.3.87: "orientation with no P₄-obstruction" should be "ordering whose associated orientation has no P₄-obstruction"
p425 - Thm4.3.89: "argument to the endpoints" should be "argument to point separated on C by the endpoints"
p436 - Exr4.3.43: "VECv1n" should be "v₁,...,v_n"
p437 - Exr4.3.51: "unit interval graph" should be "interval graph"
p437 - Exr4.3.56: "refsTthresh" should be "Theorem 4.3.75"
p498 - Exm5.2.4: near the end of the proof, numerous instances of "a" should be "x"
p559 - Exr5.4.17: the superscript "al" should be "\alpha"

Minor Typos

p12 - Thm0.40: "Proceding" should be "Proceeding" (RZ)
p21-2: The first of the two paragraphs beginning "Complexity classes" should be deleted (Jennifer Vandenbussche)
p29 - before Thm1.1.3: "Verify any one" should be "Verifying any one" (Jennifer Vandenbussche)
p100 - Lem1.3.34: "same same of" should be "same set of" (RZ)
p111 - Exm2.1.9: "each composes" should be "each composed" (Jennifer Vandenbussche)
p125 - top: "guarantees least" should be "guarantees at least" (RZ)
p128 - Thm2.1.48: "it it achieves" should be "it achieves" (RZ)
p162 - Exm2.2.34: "can only matched" should be "can only be matched"
p191 - first line: "nonadjacent of vertices" should be "nonadjacent vertices" (RZ)
p210 - Cor2.4.38: "therfore" should be "therefore"
p227 - Thm3.1.23: "Let G be a graph G" should be "Let G be a graph" (RZ)
p244 - top: "it appeared" should be "appeared" (RZ)
p244 - Exm3.2.5: period missing after "k=2" (RZ)
p245 - bottom line: extra comma
p248 - top line: "monchromatic" should be "monochromatic"
p249 - Def3.2.15 "let contracting it" should be "then contracting it" (Gexin Yu)
p250 - Lem3.2.17figure: second "G₂" should be "G₁" (Gexin Yu)
p266 - before first display: extra "}" (Gexin Yu)
p282 - Lem3.4.8: "adding uv" should be "adding uv"
p297 - Lem3.4.35: "Let d=d₁,...,d_n be a vector" should be "Let d denote a vector d₁,...,d_n (Gexin Yu)
p301 - Rem3.4.40: "??s-31" should be "Exercises 30-31"
p318 - Thm3.5.26: "The equivalent follows" should be "The equivalent form follows"
p319 - after Cor3.5.28: "the the" should be "the"
p481 - Thm5.1.31: "isa" should be "is a"
p513 - Lem5.2.36: put "k-2" in parentheses (twice)
p522 - top: "cliques is more widely" should be "is more widely"