Structure of Graphs (TAC: Vol. II) - Typos
This page lists the errors that have been discovered in the Spring 2012
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 Math 582 and possibly reviewers.
Please send any additional contributions to firstname.lastname@example.org.
Contributors noted in parentheses.
Category 1: Notational typos and other Mathematical Corrections
- p50 - after Definition 6.1.38: every T in this paragraph should be
H (Tom Mahoney)
- p60 - Case 1: The statement about numbering the accessible non-free classes
is not true. Fortunately, only a weaker statement is needed; that we can let
Vi be such a class that blocks only free classes.
- p131 - before Lemma 6.4.25: "edge-colorings number" should be "the
- p140 - Example 7.1.3: The labeling of the figure doesn't agree with the
text. Vertex i should be made adjacent to i+(n-1)/2; we don't
want edges to have "length" exceeding n/2 (Greg Puleo)
- p143 - Theorem 7.1.8 (revised version in handout):
"G'y⊆V(C)" should be "G'x⊆V(C)"
- p166 - Theorem 7.1.58: Before considering the interference by w along
the ci,di-path, care should be taken to reduce
to the case where ci, xi, yi, zi,
di appear in order along the path (Michael Santana)
- p182 - Exercise 7.1.67: In the conclusion of part (b), "2k" should
- p213 - Theorem 7.3.6: "each μ" should be
"each μi" (Mike Santana)
- p216 - Definition 7.3.14: The notation Ck(G) for the
k-closure should be introduced here (and added to page 580) (Greg
- p221 - Example 7.3.25: "spanning clique" should be "spanning cycle"
- p222 - Lemma 7.3.29: S was not specified; it is the vertex set of
- p224 - Theorem 7.3.31: W is contained in
- p225 - Lemma 7.3.32: There is a missing "}" in the second paragraph of the
proof. Also a "j-i-i should be j-i-1. On the next page, there
is one chance for Pi and Pj to share a
vertex: when si+2=ti. (Michael Santana)
- p228 - Theorem 7.3.36: Three instances of "v1" in the las
two paragraphs of the proof should be "v0" (Greg Puleo)
- p258 - Exercise 7.3.82b: In part b, the square root should be taken on
the entire expression m-n+1, not just m
- p289 - Definition 8.1.67: Add the definition of P(G):
"For a graph G, let P(G) denote the containment poset whose
elements are the vertices and edges (as pairs of adjacent vertices) in
G." (Michael Santana
- p316 - Lemma 8.2.22: "a, b, and y" should be
"a, b, and v". (Later a parenthesis is missing)
- p317-8 - Lemma 8.2.26: For k=4, the forbidden configuration should
be a 2-vertex neighboring a vertex with degree at most 3. Also, it is simpler
to make the amount of charge moved equal to 1/3, but the argument is correct as
is except for the typo where the first d(v) should be in the
- p323 - Example 8.2.33: "pm" should be "+-", twice
- p394-412: There are vestigial instances of "e-n-f that have
now been changed to "m-n-f" (Bill Kinnersley)
Category 2: Other Changes, Comments, and Corrections of Note
- p53 - Examples 6.1.47-48: This material has been replaced by the
construction by Maheo in order to give a complete proof that hypercubes have
- p57 - Example 6.1.58: It should be noted that the case d1
is the sharpness example of Theorem 6.1.57
- p58 - after Conjecture 6.1.59: The statement about ε=.1168 is
obsolete; it came from an early draft of the Kaul-Kostochka paper and was
never published. What was published was ε=.2 in the Kaul-Kostochka-Yu
- p93 - Exercise 6.2.43: The reference to Dirac's Theorem should be to
- p179 - Exercise 7.1.42: The reference to Exercise 7.1.42 should be to
- p180 - Exercises 7.1.56-57 repeat Exercises 6.2.49-50 and have been
- p180 - Exercises 7.2.23-24 repeat Exercises 6.2.14 and 16 and have been
- p219 - Example 7.3.21: The reference to Exercise 44 should be to
Exercise 46 (Mike Santana)
Category 3: Minor Changes, Typos, and Clarifications
- p42 - Proof of Corollary 6.1.19: "called called" should be "called" (Ali
- p55 - Theorem 6.1.52: "a 2-factors" should be "a 2-factor" (Mike Santana).
Also, "because if it did" should be "because if so"
- p59 - After Example 6.1.59: "divides the |V(G)|" should be
- p93 - Exercises 6.2.40: "that then the" should be "that the"
- p112 - near bottom: "finite many trees" should be "finitely many trees"
- p224 - before Example 7.3.30: "nusber" should be "number"
- p233 - Remark 7.3.46: the references to Exercises 73, 74, 76 should be to
Exercises 75, 76, 78 (Mike Santana)
- p253 - Exercise 7.3.49: "Erdő" should be "Erdős"
- p275 - Theorem 8.1.34: "suitableconvex" should be "suitable convex" (Michael
- p277 - Theorem 8.1.41: "delet it" should be "delete it"
- p289 - after Example 8.1.66: "graph. the poset" should be "graph, the poset"
- p316 - Lemma 8.2.22: "a a" should be "a"
- p317 - Lemma 8.2.23: This lemma has a simpler proof via face charging
- p403 - Definition 8.5.25: "and edge set is" should be "and edge set" (Bill
- p451 - Remark 9.3.12: "slowing" should be "slowly" (Michael Santana)
- p508 - bottom: "a a" should be "a" (Michael Santana)