# 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 west@math.uiuc.edu. 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 edge-chromatic number"
• 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)" (Greg Puleo)
• 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 be "3k"
• 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 Puleo)
• 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 Gk
• p224 - Theorem 7.3.31: W is contained in v1,…vs, not v2,…vs
• 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 denominator
• 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 up/down labelings
• 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 paper.
• p93 - Exercise 6.2.43: The reference to Dirac's Theorem should be to Corollary 7.3.12
• p179 - Exercise 7.1.42: The reference to Exercise 7.1.42 should be to "part (a)".
• p180 - Exercises 7.1.56-57 repeat Exercises 6.2.49-50 and have been deleted
• p180 - Exercises 7.2.23-24 repeat Exercises 6.2.14 and 16 and have been deleted
• 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 Vakilian)
• 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 "divides |V(G)|"
• 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 Santana)
• 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" (Michael Santana)
• 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 Kinnersley)
• p451 - Remark 9.3.12: "slowing" should be "slowly" (Michael Santana)
• p508 - bottom: "a a" should be "a" (Michael Santana)