# 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"