# ``Structure of Graphs (TAC: Vol. II)'' - Typos

This page lists the errors that have been discovered in the Spring 2008
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

- p76, Lemma 6.2.11: There are some mixups between
*q* and *t*
- p82, Example 6.2.23: "
*G*" should be "*H*"
- p158, Remark 7.1.57: In the last paragraph, the join should be with
*K*_{2}, not *2K*_{1} (also in Exercise 70)
- p184, Lemma 7.2.15: at the end of the first paragraph, "y,N(z)-fan" is
wrong. It should be a "w,{x,y,z}-fan", where w is chosen outside {x,y,z}
(Kyle Jao)
- p184, Theorem 7.2.16: x1 and x2 should be switched beginning with
"when e=x2x3" (Kyle Jao)
- p187, Lemma 7.2.18: "neighors" should be "neighbors", and there cardinality
signs missing in an inequality near the end of the proof
- p194-5: "minimal 2k-edge-connected" should be "minimally 2k-edge-connected"
throughout this discussion (Kyle Jao)
- p261, Theorem 8.1.41: In the discussion of
*J*, the appearances of
*G* should be *J*
- p310, Lemma 8.2.32: "components" should be "blocks"
- p335, Theorem 8.3.11: It is simpler to apply the argument to all the
cycles in the symmetric difference of
*M* with any arbitrary matching.
The description of *C* needs to be clarified
- p327, Definition 8.3.1: parenthesis missing at end
- p329, Lemma 8.3.3: "
*x,y*-path" should be "*x,z*-path"
- p330, Theorem 8.3.5: "
*3n*" should be "*8n*"
- p336, Theorem 8.3.12: There are various words missing in the proof.
- p337, Theorem 8.3.13: "Also traverse" should be "Also
*C* traverses".
- p375, Corollary 8.5.8: "
*e-2n*" should be "*m-2n*"
- p381, Theorem 8.5.19: "
*2e/n*" should be "*2m/n*"
- p418, Exercise 9.1.6: The upper bound must be larger by 1

## Category 2: Other Changes, Comments and Corrections of Note

- p330-332: The discussion of the Separator Theorem and its applications
looks less formidable with 2\sqrt{2
*n*} changed to \sqrt{8*n*}.

## Category 3: Minor Changes, Typos, and Clarifications

- p61, Exercise 6.1.15: space missing before first
*e*_{1}
- p61, Exercise 6.1.17: first letter of "threshold" missing
- p297, Theorem 8.2.17: for 6-vertices, "not charge" should be "no
charge"
- p312, Lemma 8.2.37: "illustrate beloe" should be "illustrated below"
- p347, Exercise 8.3.9: "perfact" should be "perfect"
- p355, Remark 8.4.11: "Pelsmaje" should be "Pelsmajer"
- p358, Example 8.4.18: the vertices along the horizontal axis should be
split using the floor and ceiling of
*r/2*
- p398, above Theorem 9.1.4: "an edges" should be "an edge"
- p401, above Definition 9.1.10: "
*r-1*-colorable" should be
"*(r-1)*-colorable"