Introduction to Graph Theory - Second Edition

by Douglas B. West

Comments Page

This page contains comments and updates on the text. These include corrections to attributions and references, comments on exercises and exposition, etc.

Contributors names appear in parenthesis. In particular, "JG" denotes John Ganci, who has read the book amazingly carefully, and "FG" denotes Fred Galvin, who has contributed many improvements for the text and exercises. Please send contributions for this page to west@math.uiuc.edu.

Related pages

• Corrections (typos in notation, omissions from mathematical statements, etc.)
• Minor typos (errors in spelling, punctuation, etc.)
• Supplementary Exercises (to be added in later editions)
• Index page for Introduction to Graph Theory
• Index page for Math 312

Planned Future Changes

The comments in this first section will mostly not be implemented in reprintings of the second edition. The content of the text should not generally be changed between printings except for corrections. These items will be implemented in the third edition.

• inside cover: the notations n! and n_(j)=n(n-1)...(n-j+1) were omitted from the list of notation (JG)
• p1 - Exm1.1.1: it seems that historically the original question was only to traverse each bridge once, not necessarily to return home; i.e., seeking an Eulerian trail, which of course still does not exist. I will do something about this in the next edition.
• p2 - Def1.1.2: Fred Galvin has convinced me that the basic definition of graph should require a nonempty vertex set to avoid awkward moments later. Rem 1.1.6 will thus mention the possibility of extending the model.
• p10 - Exm1.1.30: more interesting examples of isomorphism testing will be added
• p11 - Exm1.1.31: in the figure, the third pair from the left should be drawn to illustrate complementarity, like the others. (Jerry Grossman)
• p12 - Exm1.1.35: the notations K_1,3+e and K₄-e have not been defined at this point, so here these graphs should be specified in words (FG)
• p14 - after 1.1.40: (instructors may want to use this one in class.) Cor1.1.40 will be followed by this short proof that the Petersen graph has no 10-cycle, using girth 5: "If there is a 10-cycle C, then the graph consists of C plus five chords. If each chord joins vertices opposite on C, then there is a 4-cycle. Hence some chord e joins vertices at distance 4 along C. Now no chord incident to a vertex opposite an endpoint of e on C can be added without creating a cycle with at most four vertices." This proof avoids the case analysis of Thm7.1.9, and it proves this fact at the desired point in the text using methods available and pertinent then. (It is a simplification of a proof by John Ganci.)
• p17 - Exr1.1.22: the proof is easier by complementation, so the second clause of the problem statement will be deleted (FG)
• p17 - Exr1.1.26-27: the problems can be strengthen by adding "at least" to the constraints on girth and degree (FG)
• p17 - Exr1.1.28: the problem can be made more interesting and relevant to research topics by having two parts: one to show that the shortest even cycle has length 6, the other that the shortest odd cycle has length 2k+1 (FG)
• p20 - Def1.2.2: a path of length 0 has no vertices of degree 1, so this should be reworded.
• p21 - second sentence: the concatenation can also fail to be a path by having an internal vertex of one as an endpoint of the other. (Jerry Grossman)
• p21 - Lem1.2.5: The various technical difficulties associated with the informal definition of what it means for a walk to "contain" a path can be eliminated by defining a "subwalk" of a walk W to be a walk obtained by iteratively deleting portions of between repetitions of a vertex, and then the lemma is that a u,v-walk has a subwalk that is a traversal of a u,v-path. (FG)
• p23 - before Def1.2.12: it should be mentioned that deleting an isolated vertex decreases the number of components. (Gerard Chang)
• p25 - Def1.2.20: probably one should also define intersection analogously here; it seems that intersection of graphs is defined nowhere else in the text. (JG)
• p28 - near 1.2.27: a clarifying remark is needed to apologize that an odd cycle is an even graph (Maria Muyot). This should include the caveat that a graph that is not an even graph is not an Odd Graph. Terms that arise in different contexts sometimes do not mesh well.
• p29 - Lem1.2.31: this is now stated for non-extendible trails, a larger class than maximal trails. Making the more general statement here clarifies the distinction between maximal and non-extendible trails, which is relevant in Exercise 1.2.32
• p31 - Exr1.2.10: part (b) should specify "connected" to avoid the K₃+K₁ example
• p34 - Exr1.2.43: the result of this exercise, which is the same as that of Exr7.1.15, is attributed by Haggkvist and Johansson to A. Kotzig, From the theory of finite regular graphs of degree three and four, \v{C}asopis P\v{e}st. Mat. 82 (1957), 76-92.
• p40 - Thm1.3.19: this result was first proved by Erdos, Problems and results on finite and infinite graphs. Recent advances in graph theory (Proc. Second Czechoslovak Sympos., Prague, 1974), pp. 183--192. Academia, Prague, 1975.
• p41 - Exm1.3.20: the smallest example of a local maximum that is not a global maximum in this problem occurs using C₄ (Sebastian Cioaba)
• p41 - Def1.3.22: since "claw" is defined on p12 and "H-free" is defined here, "claw-free" is defined here. Nevertheless, for clarity in preparation for later uses of "claw-free" (such as p118), it would be worth remarking here that a complete bipartite graph is triangle-free but not claw-free, while a complete graph is claw-free but not triangle-free.
  Also, it is not clear what one would want "triangle-free" to mean in the context of multigraphs. The concept "H-free" is generally used only in the context of simple graphs.
• p47 - Thm1.3.33: Berge also included this Theorem in the original French edition, published in 1970, and it appears independently by Eggleton in 1973. It appears even earlier in a paper by Fulkerson, Hoffman, and McAndrew, Some properties of graphs with multiple edges, Canad. J. Math 17 (1965), 166-177. C.~Berge, {\it Graphes et Hypergraphes} (Dunod, 1970), Theorem 5 of Chapter 8. R.B. Eggleton, Graphic sequences and graphic polynomials: a report, Coll. Math. Soc. Janos Bolyai 10, Infinite and Finite Sets (Keszthely, Hungary, 1973). Published in 3 vols. under title Infinite and Finite Sets, ed. A. Hajnal, R. Rado & Vera T. S=F3s (North Holland, 1975) vol.1, 385-392. MR 52#5286.
• p49 - Exr1.3.19: should be (+)
• p49 - Exr1.3.29: Part (a) is not needed to do part (b); they can be done separately by essentially the same short induction, and they will be separated into two problems. (FG)
• p50 - Exr1.3.37: an optional part (b) should be added to "Use Proposition 1.3.11 and part (a) to show that regular graphs are reconstructible" (JG)
• p52 - Exr1.3.60: this exercise is quite difficult, since several different constructions are needed to show that the necessary conditions are sufficient, depending on the values of a, b, and k. Such a list is graphic if and only if ka+(n-k)b is even and ka\le k(k-1)+(n-k)\min{k,b}
• p56 - Def1.4.10: both "subgraph" and "subdigraph" are used for structures contained in digraphs; a comment should be added about this (Gerard Chang)
• p66 - Exr1.4.42: Feedback sum is minimized by an ordering if and only if the vertices are in nonincreasing order of outdegree (FG)
• p72 - 2.1.12-13: An edge by itself is not a graph. For this and other reasons, the third edition will return to defining the center as the set of vertices of minimum eccentricity, not as an induced subgraph
• p72 - Thm2.1.14 and before: although technically inaccurate, it is fairly common convention to use "\sum_{u,v\in V(G)}" to denote a sum over unordered pairs of vertices. This issue will be addressed more explicitly in the third edition. (JG)
• p75 - Exr2.1.1: instead of asking the students to draw the trees twice, this should say "Determine all isomorphism classes of trees with six vertices. Find the maximum degree, the diameter, and the center of each." (FG)
• p76/94 - Exr2.2.22 repeats Exr2.1.21; will be eliminated
• p77 - Exr2.1.34: the exercise can be strengthened by changing "more than" to "at least". The example of T=K_1,3 and G=C₄ shows that the result is then best possible when k=3 (JG).
  The weaker threshold n(k-1) follows immediately from Exr1.3.44b and Prop2.1.8; this will be added as an easy part (a).
  To obtain a result that is best possible for all k, one can lower the threshold to n(k-1)-k²/2+1. The weaker threshold yields a harder problem, as it requires showing that the complement of an n-vertex simple graph with fewer than n/2 edges contains a copy of every n-vertex tree. That statement follows from the packing result of Sauer and Spencer (JCTB 25 (1978), 295-302) that e(G)e(G)<{n\choose2} implies that n-vertex graphs G and H pack (edge-disjointly) into K_n, and it was also proved independently by Bing Zhou in "A note on the Erdos-Sos conjecture", Acta Math. Sci. (English Ed.) 4 (1984), 287-289.
• p77 - Exr2.1.39: There is a short proof using Theorem 1.2.33 (Tao Jiang)
• p78 - Exr2.1.49: The conclusion can be strengthened to diam(Gbar)\le2 (FG)
• p78 - Exr2.1.50b: The definition of distance from a vertex v to a set or subgraph was omitted; this is the minimum distance from v to any vertex of that set or subgraph. This will be added in the next edition
• p78 - Exr2.1.52b: There is a simple general construction that works whenever r is at least 3, even or not. Furthermore, the result generalizes using a single family of constructions with one cycle: For all r and k with 2\le r\le k< 2r, there is a graph having a vertex with eccentricity k whose neighbors all also have eccentricity k (FG)
• p79 - Exr2.1.62: The meaning of "Determine the diameter of G" is a bit unclear. It should be "For n\ge4, determine the maximum possible value of \diam(G) as a function of n
• p80 - Exr2.1.75: Fred Galvin has provided an elegant short proof of this by handling caterpillars in the basis step and using an induction step that deletes the two endpoints of a longest path. In the next edition, the exercise will move to Section 2.2 to take advantage of the caterpillar concept and provide an application of it.
• p81 - Exm2.2.2: To reduce misconceptions, the Prüfer example will be rewritten so that the last edge is not a pendant edge of the original tree
• p86 - Thm2.2.12: The third edition will have an inductive proof (ps pdf) of the Matrix Tree Theorem (which should more directly cite Kirchhoff [1847]) instead of the proof using the Binet-Cauchy Formula. The inductive proof needs only the deletion-contraction recurrence and the expansion formula for the determinant, which is familiar to more students than the Binet-Cauchy Formula is. Yaokun Wu notes that there is also a bijective proof in H.N.V. Temperley, Graph Theory And Applications, John Wiley, 1981, pp. 24--25.
• p91 - Thm2.2.28: This is commonly known as the "BEST Theorem", citing also C.A.B. Smith and W.T. Tutte [1948] (American Mathematical Monthly)
• p100 - Def2.3.11: To illustrate the effectiveness of rooted trees as a proof technique, I will add the short proof using this notion that pairwise interesting subtrees of a tree have a common vertex (suggested by Sundar Vishwanathan)
• p105 - Exr2.3.19: Phrased as follows, the (+) can perhaps be deleted: "Let w be a vertex in a tree T, and let u be a vertex at maximum distance from w. Prove that the eccentricity of u is the diameter of T. Conclude that the diameter of T can be computed by running BFS twice." The C-R-L reference was omitted from the bibliography.
• p111 - Cor3.1.13: We may assume by symmetry that |X|\ge |Y|. Now verifying Hall's Condition in the second paragraph completes the proof without arguing separately that |X| = |Y|. (Gerard Chang)
• p113 - Thm3.1.16: the sentence in line 4 of page 113 is unnecessary. (Gerard Chang)
• p118 - Thm3.1.34: after choosing S and S', the proof can be simplified by enlarging S' to a maximal independent set U in G (hence an independent dominating set), and then showing that |U-S'|\le|S-S'| using the arguments of the last paragraph (FG)
• p119 - Exr3.1.16: I once thought it was easy to improve this to a lower bound of 2^(2k-1-1) for k\ge1 by using symmetry, but now I can't remember how. Nevertheless, the leading order behavior of the number of perfect matchings is (k/e)^2k-1, where e=2.71828..., as determined by Clark-George-Porter Congr. Numer. 127 (1997), 67-69.
• p120 - Exr3.1.26: The hypothesis can be weakened a bit: it's enough to assume that |W| >= 2*|{i: x is in W_i} whenever W is a winning set and x is in W. To avoid possible degeneracy, "winning sets of positions" should be "winning subsets of X, all nonempty". Finally, to avoid conflict with other uses of "position" in games, the locations should perhaps be called "points", players must choose distinct positions, a winner is the first to collect a winning set, and "force a draw" should be "prevent Player 1 from winning". (FG)
• p121 - Exr3.1.37: part (a) is not needed to solve part (b), although it has independent interest. Part (b) can be done by the technique of Exr3.1.23.
• p122 - Exr3.1.42: stating a stronger result makes the proof a bit easier. Let f(G) be the sum stated in the problem. Prove that if G is a non-trivial graph and x is a vertex of maximum degree in G, then f(G-x)\ge f(G). Conclude that iteratively deleting a vertex of maximum degree from G until no edges remain leaves an independent subset of size at least f(G).
• p122 - Exr3.1.43: this exercise and Gallai's Theorem can be proved more efficiently using the following lemma, which will be added here: Let M be a matching and L be an edge cover in a graph G with no isolated vertices. If the three properties below hold, then |M|+|L|=n(G).
  (1) M\subseteq L,
  (2) L is minimal among all edge covers containing M, and
  (3) M is maximal among all matchings contained in L. (FG)
• p122 - Exr3.1.47: to avoid the trivial answer K₁, this should ask for the smallest tree G with \beta(G)>\gamma(G) (FG)
• p121 - Exr3.1.39: does not need restriction to simple graphs (FG)
• p122 - Exr3.1.52: This result is due to Brigham-Chinn-Dutton [1988]. It would perhaps be better stated as a sufficient condition for \gamma(G)\le2
• p123 - Alg3.2.1: To explore x, we should consider y in N(x)-T. Then we don't need the requirement that xy\notin M, and the comment after the algorithm becomes superfluous, since the paths reaching vertices don't change. (Gerard Chang)
• p124 - Thm3.2.2: The last paragraph can be shortened by observing that |T|+|X-S| remains unchanged as the algorithm proceeds. (Fu, student of Gerard Chang)
• p140 - Thm3.3.9: if G is disconnected, then each component has fewer than n vertices; better to reduce to the connected case
• p147 - Exr3.3.18: it is better to require simple graph and remaining connected after the deletion of any k-3 vertices; perhaps also move to Section 4.1
• p149 - Def4.1.1: the difficulty with the connectivity of the complete graph is best handled by defining a graph to be k-connected if it has more than k vertices and no separating set of size less than k
• p151 - Thm4.1.5: the current version of Exr4.1.12 omits the case where k and n are both odd. However, a careful treatment of the argument where k is odd and n is even will also handle that without additional effort, so the case of k odd will be requested in the exercise in the next edition, without distinguishing by the parity of n
• p152 - Rem4.1.8: the restriction "when n(G) > 1" is unnecessary (FG)
• p152-3 - Thm4.1.9: the restriction to simple graphs is unnecessary (FG). Also, the second case in the proof can be simplified slightly by choosing T as follows. Each edge of the cut has an endpoint not in {x,y}, since xy is not an edge. Choose one such endpoint from each edge of the cut to form T. (Gerard Chang)
• p155 - Prop4.1.15: an alternative proof of the converse is that if F is an edge cut, then G-(F-e) is connected. Since deletion of a cut-edge increases the number of components by at most 1, G-F has only two components.
• p158 - Exr4.1.3: the phrase "that is not a complete graph" is unnecessary (FG)
• p158 - Exr4.1.8: the hint should also suggest using Corollary 4.1.13 (FG)
• p159 - Exr4.1.18: the restriction to simple graphs is unnecessary (FG)
• p159 - Exr4.1.24: this follows from Exr4.1.25, since the hypothesis force diameter 2 (Tao Jiang). In the third edition, Exr4.1.25 may move into the main text as an application of Cor4.1.13, and then it is natural to use it to do Exr4.1.24. Exr4.1.25a is due to G. Chartrand, SIAM J. Appl. Math. 14 (1966), 778--781.
• p164 - Def4.2.9: the term "closed-ear decomposition" confuses students, since it sounds like only closed ears can be used. The next edition will switch this to "weak ear decomposition", emphasizing that the condition is less restrictive than for "ear decomposition"
• p169 - Lem4.2.20: this lemma can be proved very simply as follows: Since G is k-connected, G-x is (k-1)-connected. Replacing x without the edge xy is adding a vertex with at least k-1 neighbors, so G-xy is (k-1)-connected.
• p170 - Thm4.2.23: Sufficiency is more simply proved by showing that the existence of fans prohibits a separating set of size less then k
• p173 - Exr4.2.10: The proof of this takes a number of steps and several pages. It is too difficult for inclusion in this text and will be deleted in the next edition. The reference is J. Graph Theory 36 (2001), 175-197.
• p174 - Exr4.2.16: This is not so hard with the right approach, so the following hint will be added to the back: "Let T be a largest common subtree of T₁ and T₂, and use induction on the number of vertices of G omitted by T." Since 2-connectedness is used only for the absence of a cut-vertex, this problem will move to Chapter 2. The proof appears in Lovász's problem book, on page 305 in the second edition.
• p174 - Exr4.2.22: The first inequality and its sharpness are due to Watkins, M. E, A lower bound for the number of vertices of a graph. Amer. Math. Monthly 74 (1967), 297.
• p194 - Prop5.1.11: This result appeared earlier as Lemma 2.6 in G. Sabidussi, Graphs with given group and given graph-theoretical properties, Canad. J. Math. 9 (1957) 515-525 (Sandi Klavzar)
• p196 - Thm5.1.21: In addition to the independent proofs by Gallai [1968], Roy [1967], and Vitaver [1962], there was yet another proof by Hasse [1964/5] (Zur algebraischen Begr\"undung der Graphentheorie. I., Math Nachr. 28 (1964/1965), 275 - 290). The four proofs were in four different languages, respectively English, French, Russian, and German in the order listed here. (Claude Tardif)
• p200-1 - Exr5.1.22: There is a 4-chromatic example with seven lines in which four lines meet at a point and a 4-chromatic example with eight lines in which no four lines meet at a point
• p202 - Exr5.1.39: This exercise is attributed to Horák and Tuza [1990].
• p203 - Exr5.1.47: a hint should be added: "When proving Brooks' Theorem from this statement, consider a k-critical subgraph of a given k-chromatic graph G."
• p203 - Exr5.1.48: For a 3-regular graph, m=3n/2. In this case, this exercise guarantees a bipartite subgraph with at least 7/9 of the edges, whereas Theorem 1.3.19 only guarantees a bipartite subgraph with at least 1/2 the edges.
• p204 - Exr5.1.53: This (+) problem is actually trivial, because it was misstated. The restriction should be "maximum degree less than k", not "at most". The next edition will correct the statement and give the answer. Part (a) will be to show that if n is congruent to 0 modulo 2j and k is congruent modulo 2j to a number in {j,...,2j-1}, then n is a suitable value. Part (b) will be to show that when k is at most 4, these are the only such values (this statement is not true for larger k)
• p205 - Def5.2.1: Mycielski actually considered only the sequence generated from K₂ by iterating this construction (C. Tardif)
• p205-6 - Thm5.2.3: It is worth observing (and students find it interesting) that the iteration of Mycielski's construction produces graphs that show that the other easy lower bound n(G)/\alpha(G) can be bad at the same time; for these graphs the ceiling of n(G)/\alpha(G) is always three (A. Kostochka)
• p211 - Lem5.2.15: This lemma was proved in the Dirac [1953] paper containing Theorem 5.2.16, but with a longer proof. The idea of the proof here also appears in Dirac-Sorensen-Toft, J. Reine Angew. Math. 268/269 [1974]. The k-critical graphs having edge cuts of size k-1 were characterized in the thesis of Toft [1970]. Gerard Chang observed that the lemma does not need the Konig-Egervary result, since the pairing of X's and Y's can be found easily by induction on k
• p213 - Rem5.2.21: The conjecture of Hajós was made in the 1940s; it is explicitly mentioned in the PhD thesis of G.A. Dirac. This seems to be the earliest known reference (G.A. Dirac, On the colouring of graphs: Combinatorial topology of linear complexes Univ. of London (1951). (Bjarne Toft)
• p214 - Thm5.2.23: completion of the case where F is a forest of stars does not require as difficult a result as Exercise 5.2.42. A forest of stars with m total edges is a subgraph of a tree with at most 2m-1 edges, and such a tree is a subgraph of every graph with minimum degree at least 2m-1 (Prop2.1.8). Gerard Chang provided a still simpler proof; in this case, one can augment a subdivision of F-e in G' by an edge to a neighbor in H.
• p215 - Exr5.2.6: add "For 2\le k\le n".
• p217 - Exr5.2.31: this exercise is best done using Brooks' Theorem and will move to section 5.1
• p222 - Thm5.3.10: This proof avoiding inclusion-exclusion was included when it seemed unreasonable to expect students in the course to have seen inclusion-exclusion. However, this seems to have changed, and inclusion-exclusion is really the best proof here, so the inclusion-exclusion proof will return in the third edition
• p225 - Lem5.3.16-Thm5.3.17: Although the stronger property is nice, the characterization of chordal graphs by simplicial elimination orderings can be proved without using either it or the characterization by minimal vertex separators. The third edition will use this simpler proof. It requires only loading the induction hypothesis to prove that a non-clique chordal graph that is not a complete graph has nonadjacent simplicial vertices.
• p227 - Thm3.1.30: Yet another appearance of this result was by Lovász, On the ratio of optimal and integral fractional covers, Discr. Math. 13 (1975), 383-390.
• p231 - Exr5.3.20: part (b) asks the same question as Exr5.3.25 and hence will be deleted
• p239 - Thm6.1.16: apparently this is due to Euler
• p240 - Prop6.1.19: can be proved more simply from Prop 6.1.2, and it will be helpful to students to see this transformation. (FG)
• p244 - Exr6.1.16: This appears in Jaromi'r Abrham and Anton Kotzig, Construction of planar Eulerian multigraphs. Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1979), pp. 123--130, Congress. Numer., XXIII--XXIV, Utilitas Math., Winnipeg, Man., 1979. It was also Problem E2897 in the American Mathematical Monthly (1981, p537), proposed by David Singmaster.
• p244 - Exr6.1.19: It is difficult to write a precise inductive proof of this. Since also the exercise obtains nothing additional, it will be deleted
• p249 - Lem6.2.9: This lemma is originally due to Tutte [1961]
• p252 - Def6.2.15: Arthur Hobbs points out that he long ago introduced and advocated the use of the term "H-fragment" in this way, in J-Components, Bridges, and J-Fragments, in Graph Theory and Related Topics (Proc. Waterloo 1977, J.A. Bondy & U.S.R. Murty, eds.), (Academic Press, 1979), 253-260
• p256 - Exr6.2.7: The result appears in G. Chartrand and F. Harary, Ann. Inst. H. Poincaré Sect. B. (N.S.) 3 (1967), 433--438
• p256 - Exr6.2.14: this exercise should be phrased as "if and only if"
• p264 - Thm6.3.16: the text does not make clear why m <= 5n is included in the basis. the point is that deleting a vertex may lose up to n-1 edges, so starting with m > 5n makes it possible to apply the induction hypothesis after a vertex is deleted
• p272 - Exr6.3.30: The construction for K₄\cart C_n is not easy to find, and it differs depending on the parity of n, so this should be a (+) and a hint should be added about the parity (reference Beineke, Lowell W.; Ringeisen, Richard D. On the crossing numbers of products of cycles and graphs of order four, J. Graph Theory 4 (1980), 145--155.
• p273 - Def7.1.1, Thm 7.1.16: There is some ambiguity in the usage of line graph. Perhaps the domain should be restricted to simple graphs in Def7.1.1. In Thm7.1.16, we are considering solutions only among simple graphs. In taking line graphs, a loop should yield a loop, and perhaps parallel edges should yield parallel edges to allow the counting formula of Exr7.1.11 to extend. Fortunately, chromatic number is not affected by this ambiguity. (FG)
• p277 - Thm7.1.10: It is worth noting that the case where u runs out of neighbors before there is a repetition in the list of missing colors is covered. If there is no additional neighbor, then the color just chosen as missing at the last neighbor is also missing at u, and downshifting applies.
• p285 - Exr7.1.32: The minimum degree restriction in the first sentence is unnecessary (Dmitry Fon-Der-Flaass)
• p296 - Exr7.2.21: This problem is poorly stated. More to the point and equally easy would be "Let k,m,n be positive integers with k-1 \le m < n/2. Construct a non-Hamiltonian k-chromatic n-vertex graph with minimum degree m."
• p298 - Exr7.2.41: Concerning the conjecture of Scott Smith, Burr showed later that any two longest cycles have at least (\sqrt k)-1 common vertices. Still later, Chen, Faudree, and Gould proved a constant times k^3/5 as a lower bound (Intersections of longest cycles in k-connected graphs, J. Combin. Theory Ser. B 72 (1998), 143--149.
• p316 - Exr7.3.17: The graph with 38 vertices is the smallest example, shown by D.A. Holton and B.D. McKay in "The smallest non-hamiltonian 3-connected cubic planar graphs have 38 vertices," Journal of Combinatorial Theory Series B (Vol. 45 (1988), Number 3, pp. 305-319). (Eric Harley)
• p317 - Exr7.3.20: This should be changed to "(!) A 3-regular graph G is 3-edge-colorable if and only if it is the union of two even graphs"
• p317 - Exr7.3.31: The short proof of this exercise uses group-valued flows and the flow polynomial of a graph. The arguments are not long, but the concepts are beyond the scope of the brief treatment here, so this exercise will be deleted.
• p317 - Exr7.3.32: Both properties forbid cut-edges, so the condition "bridgeless" can be dropped.
• p320-322: There is a much shorter proof due to Gasparyan that proves Lovasz's stronger version of the PGT: a graph is perfect if and only if \alpha(H)\omega(H)\ge n(H) for each induced subgraph H (G.S. Gasparyan, Minimal imperfect graphs: A simple approach, Combinatorica 16 (1996), 209-212.) It needs a bit of linear algebra (rank of matrices), so we may stick with the older proof.
• p325 - Thm8.1.11: The meaning of the labels in the host tree in the figure should be explained in the proof (Yaokun Wu)
• p332 - Lem8.1.25: The proof can be simplified slightly by avoiding the observation that mapping w to w* defines a permutation; it only needs w\ne w*. In obtaining the obstruction, start with v being the last in L among the vertices of Q. Now set a=p(v*), b=v*, c=v, d=p(b*). The simplification is that one applies only the * operation, not its inverse. (Yaokun Wu)
• p338 - Thm8.1.39: The proof that G has no other maximum cliques can be simplified; one does not need to compute A^-1 to show that t is a 0,1-vector with one 1. Multiplying q=tA on the right by 1_n shows that t sums to 1. Now qB^T=qA^-1(J-I)=t(J-I)=tJ-t=1_n-t. Since qB^T is a 0,1-vector, also t is a 0,1-vector. Since t sums to 1, it has a single 1, and q is a row of A. (Yaokun Wu)
• p350 - Exm8.2.3: It should be mentioned that Q_n is the cover graph of the lattice of subsets of [n] ordered by inclusion. The graph in the "example on the right" should be described more explicitly.
• p366 - Lem8.3.21: The notation \partial S is more commonly used for the boundary of S, defined to be the set of vertices outside S having neighbors in S. The notation will be changed to agree with this common usage, and then the quantity in the lower bound becomes the size of the boundary of \bar S. (Eduardo Canale)
• p377 - Exr8.2.51: The statement needs to be clarified, since the expression of the transversal matroid using a set system does not have a "neighborhood" defined
• p378 - Exr8.2.61: This should perhaps be restricted to unweighted graphs, since such spanning trees need not exist, and in the unweighted case the existence question can be answered using Matroid Intersection
• p378 - Exr8.2.62: This can be strengthened to guarantee that k pairwise edge-disjoint spanning trees remain after any set of at most k edges are deleted
• p396 - Exr8.3.43: There is a very natural and much shorter derivation of the bandwidth of the grid than is developed here; the exercise will be revised appropriately
• p446 - Exm8.5.37: the sharp concentration statement for the chromatic number is due to Shamir and Spencer, Combinatorica 7 (1987), 121-130
• p466 - Thm8.6.39 (Friendship Theorem): This theorem was proved first by Erdös, Rényi, and Sós in Studia Sci. Math. Hungar. 1 (1966), 215-235, which is a paper about the minimum number of edges in an n-vertex graph of maximum degree k that forces diameter at most d. This predates the proof by Wilf. The elementary proof by Huneke using counting and modular arithmetic appeared earlier in J.Q. Longyear and T.D. Parsons, The friendship theorem, Nederl. Akad. Wetensch. Proc. Ser. A 75 = Indag. Math. 34 (1972), 257--262. (FG)
• p468 - Exr8.6.8: with the proper hint, which is to look at Exr8.6.7 rather than Thm8.6.20, this becomes easy, not "+".
• p469 - Exr8.6.22: the application in part (c) is easy when c < 1, but there seems to be difficulty when c\ge 1. The problems will be restricted to the easy case.
• p494 - Big Oh notation: Derbyshire [2003] (in "Prime Obsession") attributes ``Big Oh notation'' to Landau [1909], but Landau [1909, p.~883] states that he borrowed it from Bachmann [1884].
• p587 - tensor product: the index points to page 201, but tensor product is not explicitly mentioned there. The graph in Exercise 5.1.26 on page 201 is a tensor product of complete graphs. The discrepancy will be corrected in the next edition. (Charles Vanden Eynden)

All subsequent comments and updates on this page were implemented for the second printing of the second edition.

Comments and Updates for Chapters 1-7

• p21 - before 1.2.5: in the statement of what it means for a walk in a graph to contain a path, it would be better to replace "in order" with "with the same order as in P," (Mark Ellingham)
• p48 - Exr1.3.13: some students are confused by the presence of two mountain ranges in the illustration; they are being combined
• p65 - Exr 1.4.30: this is due earlier to V. Vizing and M. Goldberg [1969]
• p113 - "Rizzo" should be "Rizzi" (Greg Bachelis)
• p113 - "dual pair of optimization problems" would be better as "pair of dual optimization problems"
• p117 - Thm3.1.30 between "Each vertex of G" and "is counted", it would be clearer to insert "has at most n neighbors and thus". For the displayed equation, the inequality 1-p < e^-p should be mentioned (JG)
• p118 - Thm3.1.34: This theorem was misattributed; it is due to R.B. Allan and R.C. Laskar [1978]. The paper by Bollobas and Cockayne has a later generalization of this bound, showing that a K_1,k+1-free graph has an independent dominating set of size at most (k-1)\gamma(G)-(k-2).
• p122 - Exr3.1.51: in part (b), the upper bound has been improved to n-(diamG)/2, but it can be improved further to n-\ceiling{2(diamG)/3} (JG)
• p124 - Thm3.2.2: For consistency with the other proofs, R should be changed to Q in this one
• p126 - Lem3.2.7: The preceding sentence is being converted to a title for the lemma
• p147 - Exr3.3.14: This has a nice proof using the Berge-Tutte Formula but should be marked (+)
• p158 - Exr4.1.8: add hint - for the graph on the left, use Prop4.1.12 to establish the edge-connectivity
• p193 - Exm5.1.10: The box notation for cartesian product attributed here to Rodl is due originally to Nesetril and was popularized by Rodl
• p203 - Exr5.1.46: A better hint for the left graph is to consider the colors on the central vertices. Drawn in this way, the graph results from a modification of Mycielski's construction that yields the Gr\"otzsch graph
• p204 - Exr5.1.51: This result is due to Albertson [1998]. The later paper by Albertson and Moore has further results about extending a pre-coloring of specified vertices to a full proper coloring.
• p216 - Exr5.2.15: A stronger statement should actually be easier for students to prove: "Prove that every triangle-free graph with at most \CH(k+1,2)-2 vertices is k-colorable. Conclude that the chromatic number of a triangle-free n-vertex graph is at most \sqrt{2n}" (FG)
• p216 - Exr5.2.18: For all n and r, the simple criterion for a difference is b(r-b)/(2r)\ge1 (FG)
• p216 - Exr5.2.22: Uses Application 5.2.11, and hence should be marked (*)
• p222 - Thm5.3.8: The citation should be 1932c (JG)
• p251 - before Def6.2.12: The date for Schnyder should be 1990 (JG)
• p252 - bottom: the "Kelmans [1984a]" reference should be "Kelmans [1981b]"
• p252 - bottom: Recent planarity-testing algorithms include J. Boyer and W. Myrvold [1999] and another algorithm by F. Hsu.
• p270 - Exr6.3.8: For a better problem, require at least two internal vertices
• p271 - Exr6.3.15: this was proved earlier by Peter Mihók [1983]
• p279 - Thm7.1.13: the original proof of Shannon, without using the Vizing-Gupta result not proved here, is self-contained and about the same length as this. Also, it foreshadows the recoloring arguments in the proof of 7.1.10. Hence in the next edition that proof will replace this and move before 7.1.10
• p288 - Rem7.2.6: The date for Chvatal should be 1973 (JG)
• p296 - Exr7.2.17-18: These results about cartesian products appear in V.G. Vizing, The cartesian product of graphs (Russian), Vy\v cisl. Sistemy 9 (1963), 30--43.
• p304 - Conj7.3.8: Now that Tutte's 3-edge-coloring Conjecture has been proved by Robertson, Sanders, Seymour, and Thomas, what should the theorem be called?
• p315 - Exr7.3.12: This should be changed to the statement that a plane triangulation has a vertex partition into two sets inducing forests if and only if the dual is Hamiltonian, proved by S.K. Stein [1970]

Comments and Updates for Chapter 8

• p330 - before Exm8.1.22: The date for Burlet and Uhry should be 1982 (JG)
• p355 - Rem8.2.19: the discusion of rank in vector spaces should be clarified as follows: The rank of a set X\esub E in a vectorial matroid is the dimension of the space spanned by X. The submodularity inequality is related to the dimension formula for subspaces: \dim U\cap V+\dim W = \dim U+\dim V, where W is the space spanned by U\cup V. When X and Y are spanning sets of vectors in U and V, the dimension of the space spanned by X\cap Y may be less than \dim U\cap V. Nevertheless,\dim U\cap V+\dim W\le \dim U+\dim V is proved naturally for vector spaces using the proof of U\ImpR below."
• p384 - R(5,9) is at least 121 as of July 2000
• p387 - second sentence: should be "Burr and Erdos [1983] conjectured that equality holds when H is a complete graph and m is sufficiently large in terms of \chi(H) and . . ." (the correct date for Brandt will be added when the paper is published)
• p410 - top: the correct date for Molloy and Reed will be added when the paper is published
• p429 - Thm8.5.11: definition of the notation for the falling factorial (n_(j)=n(n-1)...(n-j+1)) was omitted from the text and from the list of notation (JG)
• p466 - before Friendship Theorem: Craig Huneke has a fairly short proof to exclude regular graphs; it uses counting of walks and modular arithmetic and is no longer than the proof of the integrality condition

Comments and Updates for Appendices

• p471 - DefA.1: since the strict inclusion sign is used on 10 pages in the text, it should be included in this definition (JG)
• p514 - Exr6.2.11: the hint suggested is not the best approach; better to consider the subgraphs of H' that contract to vertices of H
• p537 - Albertson-Moore: should be M.O. Albertson, You can't paint yourself into a corner, J. Combin. Theory Ser. B 73 (1998), 189--194.
• p537 - Allan-Laskar (missing reference): R.B. Allan and R.C. Laskar, On domination and independent domination numbers of a graph, Discrete Math. 23 (1978), 73-76.
• p541 - Bondy-Simonovits (missing reference): Cycles of even length in graphs. J. Combinatorial Theory Ser. B 16 (1974), 97--105.
• p541 - Boyer-Myrvold (missing reference): J. Boyer and W. Myrvold, Stop minding your P's and Q's: a simplified O(n) planar embedding algorithm, Proc. 10th ACM-SIAM Symp. Discr. Alg. (ACM, 1999)
• p541 - Brylawski (missing reference): T. Brylawski, Appendix of matroid cryptomorphisms, in Theory of matroids, Encyclopedia Math. Appl., 26, (Cambridge Univ. Press, 1986), 298--316 (JG)
• p545 - Erdos-Renyi: The 1959 paper cited on p426 is On random graphs, I, Publ. Math. Debrecen 6 (1959), 290-297
• p552 - Hoffman (missing reference, cited by the correction to Exr8.6.16): On eigenvalues and colorings of graphs, in Graph Theory and Its Applications (B. Harries, ed.), Academic Press (1970), 79-91
• p555 - Laskar-Shier: The reference should be "On powers and centers of chordal graphs, Discrete Applied Math 6 (1983), 139-147"
• p558 - Mih\'ok (missing reference): P. Mih\'ok, On vertex partition numbers of graphs, in Graphs and other combinatorial topics (Prague, 1982), Teubner-Texte Math. 59, (Teubner, 1983), 183--188
• p561, 573 - "Rizzo" should be "Rizzi" (Greg Bachelis)
• p562 - Sachs [1967]: page reference should be 455 (JG)
• p564 - Stein (missing reference): S.K. Stein, B-sets and coloring problems, Bull. Amer. Math. Soc. 76 (1970), 805-806
• p564 - Szemeredi [1978]: page reference should be 388 (JG)
• p567 - Vizing-Goldberg (missing reference): V. Vizing and M. Goldberg, On the Length of a Minimal Round of a Strongly Connected Graph, Kibernetica, 1969, pp. 79-82 (in Russian), English Translation: Cibernetics, 1972, Vol. 5, No. 1, pp. 95-98.
• p568 - Younger (missing reference): D.H. Younger, Integer Flows, J. Graph Theory 7 (1983), 349-357
• p569 - Allan R.B.: add name and p118
• p569 - Boyer J.: add name and p252
• p569 - Brylawski T.: add name and p360 (JG)
• p570 - Goldberg: add p65
• p571 - Hoffman A.: add J. and p469
• p571 - Laskar: add p118
• p572 - Mih\'ok P.: add name and p271
• p572 - Moore: delete item