``Structure of Graphs (TAC: Vol. II)'' - Typos
This page lists the errors that have been discovered in the Spring 2001
pre-publication version of Structure of Graphs, by Douglas B. West
(Volume II 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.
Category 1: Corrections of a Mathematical Nature
- p39 - Thm6.1.27: The several instances of "atj"
in the proof should be "at,j"
- p53 - Exr6.1.42: The explicit formula is rather messy; the problem should
ask only for a recurrence
- p57 - Exr6.1.68: "?? " refers to Theorem 6.1.41
- p57 - Exr6.1.71: 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?"
- p64-65 - Lem6.2.7 and Thm6.2.10: The summand is missing in five summations;
each "sum from k equal k to d of blank" should be the sum from i=k+1 to n
of min{k,di}
- p69 - second paragraph: before "possible to add" should be "since it may
not be"
- p75 - Exr6.2.15: "1<=i<|Y|" should be "1<=k<|Y|"
- p88 - bottom: "bi" should be "Bi"
- p90 - Cor6.3.18: "Section 10.?" should be "Section 10.2", and a close
parenthesis is missing
- p92 - Thm6.3.23: "Q- -R" should be "Q-R" (also on p93)
- p93 - Cor6.3.24: n is the number of vertices of G
- p109 - Def6.4.19: "function" should be "injective function" (Jason
Tedor)
- p112 - before Thm6.4.23: the graphs with product dimension at most 2 are the
complements of the line graphs of bipartite graphs
- p113 - Thm6.4.25: "whenever i\ne j" should be "whenever i <
j". "if and only if i=j" should be "if i=j and zero if
i < j" (in the first two paragraphs).
- p115 - Exr6.4.7: same as previous correction
- p128 - Thm7.1.21: "prime" in theorem statement should be on first kappa
- p136 - after Exm7.1.34: "Corollary 7.1.19" should be "Conjecture
7.1.33"
- p142 - Exr7.1.19: should be restricted to simple graphs
- p143 - Exr7.1.35: "bB" should be "B", twice
- p149 - Lem7.2.9: "G-uv- -S" should be "G-uv-S"
- p153 - Thm7.2.12: "|G|" should be "n(G)"; also "G-S-C"
should be "G-S-V(C)"; also the fans should be specifed to have size
k; also "x,S fan" should be "x,S-fan" (twice); also
"G-xy-D" should be "G-xy-V(D)"
- p154 - Lem7.2.13: "G-ax- -S" should be "G-ax-S"
- p154-5 - Thm7.2.14: It is clearer to let Si be a
separating k-1-set of G-ai-1ai, with
ni the order of the component of
G-ai-1ai-Si containing
ai; one then obtains ni > ni+1
directly from the lemma and sees easily that the inequalities written
originally in the contradiction were reversed
- p157 - Thm7.2.17: "Ejt- -V(Cjt)"
should be "Ejt-V(Cjt)"
- p162 - Lem7.2.22: "submodularity of d" should be
"submodularity of \delta"
- p166 - Exr7.2.29: should be restricted to nonadjacent x,y
- p173 - Thm7.3.5: "Hi- -Si" should be
"Hi-Si"
- p177 - Exm7.3.13: In the figure, "K" should be "\bar K"
- p177 - Thm7.3.14: "H=Cn+s" should be
"H=Cn+s(G)"
- p178 - after Thm7.3.16: the definition of \deltak
is missing; it should me the minimum sum of the degrees of the vertices
in an independent set of size k. Unfortunately, the common notation
for this in the literature is \sigmak
- p182 - Thm7.3.22: "t-clear" should be "l-clear".
After defining b, the first lower bound for |C| should be
(l+1)|R-T|+(l+1)(p-r-b)+pb, and the second should be
(l+1)[\theta(G)(n-r)-b]+pb. In each displayed equation, "+(r-b)"
should be "-b". In the first, "pr+r-b" should be "-b";
in the second, "(p/2)(r-b)+pb" should be "(p-4)b/2". Since
the terms involving \theta(G) are strictly positive, the final
argument in the first case is "|C| > n-r-b\ge n-p", and in the second
case it is that p\ge 4 since Gk is a non-Hamiltonian
non-complete graph, so |C| > n-r \ge n-p
- p183 - Thm7.3.23: the inequality "e(G-x)\ge m(n-2)/2" should be
strict; "also has length l" should be "also has length l-1"
- p184 - Lem7.3.24, next-to-last paragraph on page: "G-vt-1"
should be "G-vti-1"
- p186 - Thm7.3.28: the conclusion should be
"c(G) \ge min{n(G),c}"
- p193-4 - Exr7.3.24: n must be restricted to at least 3, and it is
G' whose induced subgraph is Kn/2, not G (Jason
Tedor)
- p218 - Prop8.1.18: induction step should be n > 4
- p235 - Lem8.1.51: The induction is unnecessarily formal; extremality
says it more directly: "Because G is a triangulation, these are the
vertices of a path P. Among the chords of P, choose
xixj to minimize j-i; such a chord exists
because x0 and xt are adjacent.
Since j-i\ge2, we may choose as x any xk with
i < k < j ."
- p238 - Lem8.1.58: "barycentric" should be "weak barycentric"
- p238 - Lem8.1.59: "i+" should be
"i+1" (twice)
- p241 - Exr8.1.2: This statement is nonsense; the best fix is to make it a
"prove or disprove"
- p245 - Exr8.1.45-46: "C-bridge" should be "C-fragment"
- p260 - Thm8.2.17: in the last paragraph, "x,y=\dlt,\alpha"
should be "(x,y)=(\dlt,\alpha)"
- p268 - before Thm8.2.29: "(?? )" refers to Exr8.2.16
- p300 - Exm8.3.16: the outerplanar thickness of Kn
should be the ceiling of (n+1)/4. Delete the missing reference
about achieving the bound
- p308 - Exm8.3.27: definition of G needs n2
in the numerator
- p308 - after Exm8.3.27: the leading term in the number of edges should
be 2n, not n
- p314 - Exr8.3.25: "\nu(Km,m)" should be
"\nu(Km,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
- p312 - Exr8.3.4: "ga" should be "\gamma"
- p324 - Lem8.4.12: in the figure, the up arrow should be
"ua"
- p325 - Exm8.4.15: "larger voltage graph" should be "larger base graph",
and the missing voltages in the figure are 1 on the top edge and 0 on the
bottom edge
- p341 - Thm9.1.8: "Xs- -Xt" should be
"Xs-Xt"
- p344 - Thm9.1.12: In the proof of D => E, the edges should be added from
vn to all vertices of the k-clique in G'
containing U
- p352 - after Thm9.2.4: face-width is the minimum, over all
noncontractible curves on the surface, of the number of times the curve
intersects the graph
- p353 - after Thm9.2.6: insert "and G1 is not a minor
of any subsequent Gi" before "then Theorem 4"
- p354 - Prop9.2.8: "is the set" should be "be the set"
- p372 - Thm9.3.38: "Zk- -S" should be
"Zk-R"
- p451 - middle: "(refsXsubsp," should be "(Exercise 1),"
- p452 - Rem10.1.2: "is the coefficient" should be "is the negative of the
coefficient"; "that coefficient is also" should be "that also equals"
- p454 - Thm10.1.9: in C, "\phi(G;\lmb)" should be
"\phi(G;\lmb) or \lmb\phi(G;\lmb)". in D, "any" should be
"every"
- p459 - Thm10.1.20: the definition of vj also needs a
\sqrt2
- p460 - Thm10.1.22: the first part of the proof needs to be rewritten
to allow for multiple components
- p462 - Thm10.1.28: the superscript "mj" should be
"mj"
- p468 - Rem10.1.40: near the end,
"mod p" should be "1 mod p"
- Revised p472 - Lem10.1.50: several "eigenvector"s should be
"eigenvalue"s
- Revised p472 - Lem10.1.51: in the subscripts of the numerators in the
display, delete the membership sign and shift the remaining character to
the summand
- p482 - top: "??" refers to Exercise 10.2.24
- p486 - after Prop10.2.28: "Tutte polynomials of its graphs" should be
"Tutte polynomials of its blocks"
- p493 - Exr10.2.21: the last "k" should be "-k"
Category 2: Other Changes, Comments and Corrections of Note
- p38-40 - Thm6.1.27-Exm6.1.28: For consistency of usage in these texts, the
occurrences of "arc" should be changed to "edge"
- p40-42 - Lem6.1.29-Thm6.1.34: This material is being made more concise and
clear, along the lines of the treatment in class
- p45-48 - this old exposition is being cleaned up and clarified
- p149-156 - the exposition of the proofs of the theorems of Tutte, Halin, and
Mader has been simplified slightly. The proof of the Gyori-Lovasz Theorem has
been totally rewritten with a more explicit algorithm
- p160 - Prop7.2.20: a figure and explicit computation have been added to
make this transparent
- p161-2 - Lem7.2.22: the proof has been clarified
- p171 - after Def7.3.3: proof of the toughness and non-Hamiltonicity of the
Petersen graph have been added
- p172 - comment: recognizing t-tough graphs is NP-hard for any
positive rational number t
- p172 - Thm7.3.5: "1999" should be "2000"
- p181 - Thm7.3.22: in the displayed equation at the end of Case 1, we
can use \dlt(G)=(n-1)/2
- p183 - Thm7.3.23: the explanation of the bound in the last paragraph
has been simplified slightly; no need to "further maximize": Let w be the
number of edges incident to W; by limiting w, we force many edges
into G-W. Let Z={v1,...,vr}, where
r=min {l,m}. For each vk\in W, we have shown that
N(vk)\esub Z. Thus the sum \sumv\in Wd(v)
counts edges within W twice and edges from W to Z-W once.
Hence w\le (1/2)(|[W,Z-W]|+\sumv\in Wd(v)).
Since |[W,Z-W]|\le|W| |Z-W| and d(v)\le d=|W|, we have
w\le (1/2)(d(r-d)+d^2) edges incident to W. Since r\le m,
this becomes w\le dm/2.
- p196 - Exr7.3.38-39: the citations are to Theorem 7.3.22.
- p232 - Lem8.1.47: the inequalities in the middle of the proof should be
displayed
- p237 - afterThm8.1.56: a comment has been added that Thm 8.1.56 completes
the proof that every planar graph with n vertices has a straight-line
embedding with the vertices at grid points in the triangle with corners
(2n-5,0), (0,2n-5), and (0,0)
- p284 - Exr8.2.12: For a better problem, require at least two internal
vertices
- p290 - Thm8.3.1: the date for Brahana should be 1923
- p295 - before Thm8.3.7: the date for Kagno should be 1936
- p301-2 - after Exm8.3.18, Lem8.3.19: I think the date for Whitney should be
1931
- p319 - Thm8.4.4: The reference to Kagno should be to Brahana
- p344 - Thm9.1.12: the two instances of "perfect elimination ordering"
should be "simplicial elimination ordering" (also in Thm9.1.13)
- p353 - last paragraph: this should have an explicit definition of
"bad sequence", a sequence lacking a pair i,j such that i < j
and qi < qj
- p451 - The orphaned discussion of the cycle space and bond space is moving
to Section 8.1, where Maclane's characterization of planar graphs will be
proved and applied to proved Whitney's characterization. Hence Exercises
10.1.1-5 will leave this section, and the focus on eigenvalues will be
consistent.
Category 3: Minor Changes, Typos, and Clarifications
- p42 - Thm6.1.34: "alond" should be "along"
- p44 - after Thm6.1.41: the discussion here repeats Def6.1.36
- p47 - after Thm6.1.44: "We introduction" should be "We introduce"
- p48 - after Thm6.1.46: "Haggkvist" missing umlaut on "a" (Jason Tedor)
- p54 - Exr6.1.51: "1byn" should be "1 by n"
- p58 - Exr6.1.75: "etal" should be "et al"
- p134 - Thm7.1.31: first sentence of third paragraph needs period
- p154 - Thm7.2.13: "has also has" should be "has"
- p160 - Matroids are discussed in Section 9.4, not 6.3
- p161 - before Lem7.2.22: "shortcut that preserve" should be "shortcut of
z that preserves"; earlier "digraph version" should be "version"
- p172 - top paragraph: ">=" should be "\ge"
- p172 - Thm7.3.4: the errant "Kl" in the figure has
been deleted
- p173 - Thm7.3.5: "minized" should be "minimized"
- p177 - Thm7.3.14: "Let t < n be positive integers" should be
"Let t be a positive integer less than n"; "inonadjacent"
has an extra letter
- p203 - Thm7.4.5: in the last line on the page, "minimum" should be
"minimizes
- p221 - App8.1.26 bottom: "that satisfying" should be "that satisfies"
- p234 - Lem8.1.49: "By the observation that" should be "Since"
- p305 - Thm8.3.24: third line missing ")" after "Kn-1
- p312 - Thm8.3.30: second line of proof is missing "from"
- p323 - Exm8.4.9: "provide the" should be "provides the"
- p326 - Lem8.4.17: delete first comma in proof
- p338 - bottom parg: "match leaves vertices" should be "match leaves";
in the next sentence, there are too many of "for each uv"
- p344 - Thm9.1.12: "a single sets" should be "a single set"
- p351 - Def9.2.1: "i < j" should be "i,j with i <
j"
- p355 - Thm9.2.9: "no repeated element." should be "no repeated
elements)."
- p359 - before Prop9.3.8: notation for net outflow should be a definition
item
- p372 - Lem9.3.40: in the statement, "graph" should be "graph G"
- p381 - Def9.3.58: "1,2-weight" should be in bold
- p468 - Rem10.1.40: "vertexgraph" needs a space
- Revised p472 - before Rem10.1.48: "satsify" should be "satisfy"
- p472 - Exr10.1.29: "A realization" should be "(A realization"
- p493 - Exr10.2.25: "that the for" should be "that for"