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

Category 1: Notational typos and other Mathematical Corrections

• p56, Proposition 6.1.56: the reference should be to Exercise 94 (Kyle Jao)
• 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=K_k+1" should be "H=K_k+1" (Sasha Kostochka)
• p84, Theorem 6.2.24: "the large clique have degree a₁" should be "the a₁-clique have degree a₂" (Kyle Jao)
• 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 "s_Q" 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 (Sasha Kostochka)
• 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 mK₂ 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)" (Seog-Jin Kim)

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 d_s from below instead of moving a unit away from d_j
• p153, after Theorem 7.1.48: "Exercise @" should be "Exercise 65" (Kyle Jao)
• 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. (Sasha Kostochka)

Category 3: Minor Changes, Typos, and Clarifications