``Structure of Graphs (TAC: Vol. II)'' - Typos
This page lists the errors that have been discovered in the Spring 2007
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 email@example.com.
Contributors noted in parentheses.
Category 1: Notational typos and other Mathematical Corrections
- p56, Proposition 6.1.56: the reference should be to Exercise 94 (Kyle
- p56, last paragraph: the reference should be to Exercise 96 (Kyle Jao)
- p75, Example 6.2.10: the description of the cover relation in the
dominance order is in fact incorrect; that condition is necessary but not
sufficient. The correct characterization is that d covers d'
if and only if they are equal except at two indices r and s, with
c_r=a_r-1 and c_s=a_s+1, where s=r+1 or c_r=c_s.
This will be proved as a lemma in the next printing. (Sasha Kostochka)
- p82, Example 6.2.21: in the first line, "G=Kk+1" should
be "H=Kk+1" (Sasha Kostochka)
- p84, Theorem 6.2.24: "the large clique have degree a1"
should be "the a1-clique have degree a2"
- p103, before Definition 6.3.29: the mentioned result by Lovasz is about
edge-reconstructibility, not reconstructibility (Kyle Jao)
- p104, Theorem 6.3.30: in the second paragraph, three instances of
"sQ" should be "s'Q". Also the proof
is unclear. The key, if G' is an alternative edge-reconstruction of
G, is to compute "s'G(G)" and
"s'G'(G)", each by the PIE computation. The terms in the sum
for proper subgraphs F are equal, and for F=G and F=G'
they are both 0. Hence there can only be one edge-reconstruction from the
edge-deck. (Sasha Kostochka)
- p104, before Theorem 6.3.32: The Nash-Williams result yields the Lovasz
result when the number of edges of G is even. Otherwise, one can
consider R with one edge, but now the argument requires G to have
at least two more edges than its complement.
- p110, Exercise 6.3.21: this exercise is incorrect and has been deleted
- p135, after Theorem 7.1.9: "\kappa(H)=\delta(G)" should be
"\kappa(H)=\delta(H)" (Kyle Jao) (In the next sentence,
"the equality can be weak" should be "the bound can be weak")
- p156, Theorem 7.1.54: with this method of proof, the basis should be
m=1, and the case mK2 needs special mention. To
incorporate it in the final case, note that when F is a forest of
stars one can delete the vertices of a component of F without reducing
the minimum degree by much. (Sasha Kostochka)
- p158, Remark 7.1.57: "average degree at least 5k" should be
"average degree at least 10k" (Sasha Kostochka)
- p201, Example 7.3.15: at the end, the phrase "for all i" should be
"for all j" (Kyle Jao)
- p318, Lemma 8.2.47: in the statement of the lemma, "f(w)" should be
"f(u)" (Seog-Jin Kim)
- p319, Theorem 8.2.48: in the display, the numerator
"(2t-1)(d(v)-3)+(t+1)" should be "(2t-1)(d(v)-3)-(t+1)"
Category 2: Other Changes, Comments and Corrections of Note
- p79, Theorem 6.2.16: Step 2 of the proof of sufficiency of the Erdos-Gallai
conditions is simplified for the next printing by moving a unit to
ds from below instead of moving a unit away from
- p153, after Theorem 7.1.48: "Exercise @" should be "Exercise 65"
- p156, Remark 7.1.55: The first "??" should be Theorem 6.1.6.
The second should be Exercise 66.
- p202, Example 7.3.18: It should be stated more clearly that Chvatal's
Condition implies Las Vergnas' Condition, and therefore Corollary 7.3.17
implies Theorem 7.3.14. This will become an exercise.
- p214, Theorem 7.3.40: When n=m, the claim holds vacuously,
since the hypothesis is impossible to satisfy (as is the conclusion).
The proof becomes slightly simpler by using n=m as the basis for the
induction instead of n=m+1. Also, it seems that the condition
\dlt(G) > m/2 is not needed for the proof of the induction step.
Category 3: Minor Changes, Typos, and Clarifications