Introduction to Graph Theory - Second Edition
Corrections Page
This page contains corrections to mathematical aspects of the text.
Most items are minor errors in notation; others are omissions of conditions
in exercises, etc. The typos in notation appear in this list instead of the
list of typos because notational typos can confuse a reader.
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
dwest@math.uiuc.edu.
Related pages
Corrections found SINCE the FOURTH printing
- p8 - Prop1.2.24: when corrections were made to this page for the fourth
printing, the printer did not produce the page correctly. Each instance of
"f 1" should be "f -1". The minus signs
are in the file that produced the page, but they were not printed on the page.
(Rongheng Lin)
- p12 - Exm1.1.35: the "+e" and "-e" used in defining the
paw and the kite have not been defined; here the notation should be replaced
with words (FG)
- p17 - Exr1.1.23a: the effect of loops on vertex degrees is introduced later,
so this exercise should not appear until later (FG)
- p21 - before Lem1.2.5: the meaning of when a walk contains a path is not
given clearly; the edges in order must be traversed in the direction they would
be when following the path (FG)
- p24 - before Lem1.2.15: in saying what it means for a closed walk to
contain a cycle, the restriction "closed" can be dropped, and the same
clarification as above about following edges in the right direction is needed
(FG)
- p29 - Prop1.2.29: "maximal path P" should be
"nontrivial maximal path P" so that P has at least two vertices
(Michael Pelsmajer)
- p33 - Exr1.2.30: "nearest to n" should be "in {n-1,n}"
(FG)
- p34 - Exr1.2.36: "the trails in this list" should be "such trails",
and the problem (particularly part (a)) should be restricted to loopless graphs
(FG)
- p34 - Exr1.2.43: "an even number of edges" should be "2k edges"
(FG)
- p45 - Thm1.3.31: we must also ensure that d' is well defined,
which requires that \Delta < n (FG)
- p51 - Exr1.3.42: the problem must be restricted to simple graphs, but it
can be strengthened by specifying only the minimum degree. It is as easy and
more natural without the pigeonhole principle, and in the next edition the
problem will ask for a proof of impossibility for Q4
(FG)
- p52 - Exr1.3.54: Closing parenthesis missing at end of hint (Leen
Droogendijk)
- p52 - Exr1.3.58: "k largest elements" should be
"dk largest elements"
- p55 - Exm1.4.7: the expression for the edge set of a functional digraph
is missing a right parenthesis (Peter Hamburger)
- p57 - App1.4.14: for purposes of this discussion, the digraph should be
acyclic and W should be the full set of sinks (FG)
- p62 - after Def1.4.27: the sentence saying that an oriented graph is
the same thing as a loopless simple digraph is nonsense, since simple digraphs
can have opposed edges. The formal definition is given correctly.
(Stephen Hartke)
- p65 - Exr1.4.34: The hint on p510 is misleading. More accurate is changing
the last sentence to "Reduce the number of differences by performing a 3-cycle
reversal in G or in H that involves a vertex of maximum outdegree
in F". (FG)
- p67 - Exm2.1.2: A tree is a path if and only if its maximum degree is
at most 2 (Michael Pelsmajer)
- p75 - Exr2.1.2b: requires restriction to simple graphs in order to
forbid loops from G (FG)
- p75 - Exr2.1.13: requires restriction to connected graphs (FG)
- p76 - Exr2.1.28: "Let" should be "For n\ge2, let" (FG)
- p76 - Exr2.1.29: "tree" should be "nontrivial tree" (Mike Pelsmajer)
- p76 - Exr2.1.30: "tree" should be "nontrivial tree" (FG)
- p77 - Exr2.1.38: "d'T" should be
"dT'"
- p77 - Exr2.1.41: The problem of finding the largest $f(n)$ such that some
$n$-vertex graph with $n+f(n)$ edges has no two cycles with the same length
was originally posed by Erdős in 1975. The mention of
Chen-Lehel-Jacobson-Shreve [1988] in the IGT text is only a small part of the
story. Shi [1988] proved roughly $f(n)\ge\sqrt{2n-4}$. The C-L-J-S paper and
also Lai [1990] proved $f(n)\le O(\sqrt{n\log n})$.
Lai [2020] improved the lower bound to $f(n)\ge 1.55\sqrt n$,
and Boros-Caro-Füredi-Yuster [2001] proved $f(n)\le 1.98\sqrt n$.
The restriction of the problem to $2$-connected graphs has been solved
asymptotically; the number of edges is $n+f_2(n)$ where $f_2(n)\sim \sqrt{n}$.
The lower bound is in Boros-Caro-Füredi-Yuster [2001], upper bound in
Ma-Yang [2021]. (Chunhui Lai)
- p78 - Exr2.1.52: In part (a), k denotes the eccentricity of x
(Bruno Petazzoni)
- p79 - Exr2.1.57: In part (b), "a tree T" should be "an
n-vertex tree T" and the hint will be deleted (Leen
Droogendijk)
- p79 - Exr2.1.60: The closed-form expression for the upper bound requires
k > 2 (FG)
- p79 - Exr2.1.61: Add the restrictions k\ge2 and g\ge3
(FG)
- p79 - Exr2.1.65: The restriction can be weakened to n\ge k+3,
but a restriction to simple graphs must be added (FG)
- p80 - Exr2.1.69: There are 9 vertical edges, not 12, and
"v3,2" should be "h3,2" (FG)
- p80 - Exr2.1.73: "sufficiency" should be "necessity" (FG)
- p93 - Exr2.2.12: The formula may also use the numbers of vertices and edges
of G (Alexandr Kostochka)
- p104 - Exr2.3.6: "the subgraph consisting of" should be "the
spanning subgraph whose edges are", to include the case where all weights
are odd (Leen Droogendijk)
- p106 - Exr2.3.31: it should be stated more clearly that the set of
code words is required to be prefix-free, as in Huffman's algorithm
(Larry Brown)
- p109 - Def3.1.6: As stated, an M-augmenting path could have length 0. It
should be specified that the endpoints are distinct (Haiko Muller)
- p117 - Thm3.1.30: requires restriction to simple graphs or hypothesis that
every vertex has at least k neighbors; same for Rem3.1.31 (FG).
Also, the reference to Alon's paper is incorrect and should be deleted (Bruce
Priddy)
- p117 - Rem3.1.31: "total domination number satisfies a bound asymptotic to
this" should be "one can obtain a dominating set with asymptotically the same
size having the additional property of inducing a connected subgraph
- p119 - Exr3.1.12: "single path" should be "single nontrivial path"
- p119 - Exr3.1.13: the bold and solid edges should be switched (Peter
Winkler)
- p120 - Exr3.1.23: in the hint, "proper subset" should be "nonempty proper
subset" and "minimal nonempty" should be "nonempty" (FG)
- p121 - Exr3.1.36: restrict to simple graphs (FG)
- p123 - Exr3.1.60: "sharp" should be "almost sharp"; in the graph described
the smallest dominating set has size 3m-2
- p129 - Rem3.2.12: "reachable in X and T" should be
"reachable in X and Y, respectively" (Guilherme Ottoni)
- p130 - Appl3.2.14: in the definition of the demand at y, the
superscripts "+" and "-" should be interchanged (Dan Cranston)
- p137 - Thm3.3.3: At the bottom of the page, the set in which the 1-factor
is to be found is the union of M1 and
M2 together with {xy,yz} (Jerry Grossman)
- p148 - Exr3.3.29c: should begin as "Use part (b) to conclude that
nonnegative integers d1,...,dn with
d1\ge...\ge dn are . . ." (Ebrahim
Ghorbani)
- p152 - Def4.1.7: The graph K1 has no disconnecting set
(not even the empty set); its edge-connectivity must be taken to be 0 by
convention (Sandi Klavzar)
- p153 - Thm4.1.11: The 2-vertex graph with a triple-edge must be
excluded. When "graph" forbids multiedges in the third edition, that wil
not be a problem, but still K4 must be handled separately,
since it has no vertex cut (Songling Shan)
- p154 - Thm4.1.11: The picture is not sufficiently general, since
deleting {v1,v2} may leave three components.
To be more precise, for each v∈S delete the edge to
H1 if there is only one such edge; otherwise there is only
one edge from v to H2 and we delete that. Now every
path from V(H1) to V(H2) traverses a
deleted edge (Robert McCann)
- p155 - Rem4.1.18: When multiple edges are allowed, a multi-edge has no
cut-vertex but is not 2-connected, so an exception is needed here (Rob Ellis).
In the third edition, "graph" will forbid multi-edges, so this difficulty will
disappear.
- p159 - Exr4.1.22: The complete graph must be excluded. The point is to
show that G has no separating set of size at most k
- p163 - Def4.2.7: We must also require that the endpoints of the ear have
degree at least 3 in G. (Sandi Klavzar)
- p163 - Thm4.2.8: When multiple edges are allowed, a multi-edge can be viewed
as having an ear decomposition but is not 2-connected, so an exception is
needed here (Rob Ellis). In the third edition, "graph" will forbid
multi-edges, so this difficulty will disappear.
- p160 - Exr4.1.25: in part (a), when |S|=n(G)/2, one can only
guarantee that one side of the cut has this property, not both (Tao Jiang).
Furthermore, to make the statement correct, one should first assume that the
edge-connectivity is less than the minimum degree (Randy Komperda)
- p169 - Thm4.2.21: The first statement fails in the special case where
all pairs of vertices are joined by at least two edges (Bruce Sagan). In
future editions, such statements will be made only for simple graphs, which is
the context of interest for connectivity, to avoid such difficulties
- p170 - Thm4.2.23: Again, the context of simple graphs will fix the problem
in the sufficiency proof here that k distinct neighbors are needed
(instead of \dlt(G)\ge k), which indeed is guaranteed by a
v,V(G)-{v}-fan. The problem that z might be an internal vertex
in a w,N(z)-fan will be corrected by defining paths in an x,U-fan
to reach U only at their endpoints. (Bruce Sagan)
- p173 - Exr4.2.8: The exercise should be restricted to graphs with more than
two vertices. (Alexandr Kostochka)
- p174 - Exr4.2.24: It is not necessary that S and T be disjoint
(Leen Droogendijk)
- p175 - Exr4.2.28: Change "nonnegative" to "positive" or change
"X,Y-paths" to "paths from X to Y". With the specific
definition given for X,Y-paths (no internal vertices in X or
Y), there is a technical counterexample with 0 weights.
(Stephen Hartke)
- p175 - Exr4.2.29: The edge implication and vertex implication should be
separated and should be stating for individaul vertex pairs, yielding stronger
statemens (Leen Droogendijk)
- p175 - Exr4.2.30: The statement should be restricted to simple graphs
(Shir Kehila)
- p182 after Rem4.3.14: The reference to Theorem 4.2.25 should be to the
*second* Theorem 4.2.24 (Nick Matteo)
- p195-6 Exm5.1.15 - Prop5.1.16: It should be observed that we may assume
without loss of generality that the intervals in a representation are closed,
since that is used in the proof of the proposition (Bruce Sagan)
- p195 - bottom: "a, d, . . ." should be
"a, e, d, . . ." (Andrew Badr)
- p197 - Thm5.1.21: in line 4 of the proof, "the longest path" should be
"a longest path" (Bruce Sagan)
- p204 - Exr5.1.55: the unequal sign should be the incongruent sign (FG)
- p213 - Thm5.2.20: at the beginning of the last paragraph, "x\in V(G)"
should be "x\in V(H)" (Bruce Sagan)
- p215 - Exr5.2.9: require also that G is nontrivial, since the
statement is not true when G is 1-critical (Bruce Sagan)
- p217 - Exr5.2.25: part (a) should specify that G has n
vertices
- p217 - Exr5.2.32: part (a) should require k\ge3
- p218 - Exr5.2.37b: should be restricted to simple graphs (FG)
- p218 - Exr5.2.39: n\ge2 is required (Bruce Sagan)
- p225 - Lem5.3.16: it must also be required that G is connected
(Bruce Sagan) (Note: 5.3.16-17 will be replaced in the next edition by a
single, less technical proof, with the stronger statement in 5.3.16 becoming
an exercise)
- p230 - Exr5.3.10: "{n-1\choose i}" should be
"{n-1\choose i-1}" (Leen Droogendijk)
- p231 - Exr5.3.23: S should be restricted to be the vertex set of
a cycle of length at least 4 (Peter Hamburger)
- p232 - Exr5.3.32: "\chi(G;k)" should be
"\chi(G;-k)" (Nathan Reading)
- p240 - Prop6.1.18: loops must be forbidden (FG)
- p242 - Prop6.1.26: n\ge3 is required (Bruce Sagan)
- p243 - Exr6.1.6: should restrict to "loopless" (Mike Pelsmajer)
- p245 - Exr6.1.30: It should be specified that k is finite
(Yiu Yu Ho)
- p245 - Exr6.1.34: "dodecahedron" should be "icosahedron" (Jerry
Grossman)
- p246 - Exr6.1.36: n\ge3 is required (Brendon Rhoades)
- p246 - Exr6.1.37: l\ge2 is required (Jerry Grossman)
- p247 - before Lem6.2.4: The first sentence of the paragraph should be
"We will prove that a graph with fewest edges among nonplanar graphs with no
Kuratowski subgraph must be 3-connected" (this is the goal in Lem 6.2.7) (Jerry
Grossman)
- p248 - Lem6.2.7: To avoid isolated vertices, one should require G
to be connected or assume that the number of vertices plus number of edges has
been minimized (Wasin So)
- p250 - Thm6.2.11: in the next-to-last line, "u,v,x" should be
"u,v,w" (John Harper)
- p251 - Def6.2.12: emphasizing here the duality between deletion and
contraction (as in matroids) produced an error; this definition does not
allow deletion of isolated vertices. The correct definition is that H
is a minor of G if H can be obtained from G by contracting
a subset of the edges in a subgraph of G (Bruce Sagan)
- p256 - Exr6.2.12: deletion of isolated vertices must also be allowed
(Andre Kundgen)
- p265 - after Exm6.3.17: The leading term for the number of edges in the
grid with n points should be 2n, not n (Alexis
Seferlis)
- p270 - Exr6.3.7: it needs to be assumed also that H' is 2-connected
(Bruce Sagan)
- p271 - Exr6.3.17: the floor symbol on (n+2)/6 should be ceiling,
like the instance before it
- p271 - Exr6.3.24: "|i-j| <= k" should be "0 < |i-j| <= k"
for clarity (the graph is simple)
- p272 - Exr6.3.28-29: It should be noted that we consider only drawings
in which incident edges do not cross. Even better is to count only pairs
of nonincident edges that cross an odd number of times.
- p283 - Exr7.1.13: C5 is another example (FG)
- p283 - Exr7.1.15: the reference to Ex3.3.22 should be to Ex3.3.23
(Roland Loetscher)
- p285 - Exr7.1.35: set bracket missing at the end of the definition of
P
- p285 - Exr7.1.38: this exercise should assume also the hypothesis from
Theorem 7.1.17 that G has no double triangle with both triangles odd
(John Caughman)
- p287 - Prop7.2.3: "S\subseteq V" should be "S\subset V(G)"
(Bruce Sagan)
- p289 - Def7.2.10: "at least n" should be "at least n(G)"
(Luke St. Clair)
- p297 - Exr7.2.30: Ore's Condition is that for each pair of nonadjacent
vertices, the degree sum is at least the number of vertices. The sufficiency
of this condition for the existence of Hamiltonian cycles is an immediate
corollary of Lemma 7.2.9, but it is not the statement of Lemma 7.2.9.
(Lale Ozkahya)
- p301 - Thm7.3.2: in line 2 of this page, "solid" and "bold" should be
switched (Sun-Yuan Hsieh)
- p301 - Lem7.3.3: "xy,uv are distinct" should be
"xu,yv are distinct, with x and y on the same side of the
cut" (Bruce Sagan)
- p304 - Lem7.3.10: "girth less than 4" should be "girth at most 4"
(Gabe Cunningham); also, "bridgeless" should be added to first part of the
hypothesis (Leen Droogendijk)
- p310 - after Thm7.3.24: It should be observed that both existence and
nonexistence of nowhere-zero k-flows is preserved by subdivision
(Leen Droogendijk)
- p317 - Exr7.3.22: the case (k,t)=(2,3) is an exception
- p322 - Thm8.1.6: since it has not been shown that every vertex of G
lies in some Q, it remains possibile that
ω(H)<ω(G), but that does not affect the rest of the proof
(Leen Droogendijk)
- p325 - above Alg8.1.12: The reference to Theorem 5.3.17 should be to
Lemma 5.3.16 (Leen Droogendijk)
- p346 - Exr8.1.23: G has n vertices
(Leen Droogendijk)
- p345 - Exr8.1.21: The requirement n>k is missing
(Leen Droogendijk)
- p347 - Exr8.1.35: only induced odd cycles of length at least 5 are
forbidden
- p372 - Exr8.2.9: this problem should be stated for partition matroids,
not transversal matroids, and then it is a (-) problem
- p373 - Exr8.2.16: this problem should specify using the dual version
of the base exchange property (Lemma 8.2.33)
- p374 - Exr8.2.22: in order to be a (-) problem, this should follow and
use Exr8.2.24
- p375 - Exr8.2.31: the second part of this exercise doesn't seem to
make much sense
- p379 - Thm8.3.3: the last term in the example list at the bottom of the
page should be "10", not "0" (Zhaojun Wu). Alternatively, the pair underneath
it should be "1,4" instead of "4,1" (M. Falahat).
- p387 - Thm8.3.15: the conclusion holds for m at least 2
(Leen Droogendijk)
- p395 - Exr8.3.32: the square root sign should apply to all of
n(G)-3
- p395 - Exr8.3.33: "proved that" should be "proved that if"
- p399 - Cor8.4.9: "less than n-1" should be "at most n-1"
(Leen Droogendijk)
- p408 - Thm8.4.24: in the last sentence, "Claim 3" should be "Claim 2"
(Leen Droogendijk)
- p409 - after Prop8.4.25: For m=4, the bound should be n≤18,
not n≤20 (Dan Cranston)
- p410 - Lem8.4.29: "the kernel" should be "a kernel"
(Leen Droogendijk)
- p414 - below picture: Gallai's Conjecture should be stated for connected
graphs
(Leen Droogendijk)
- p415 - line below picture: superscript 2 should be superscript 1
(Leen Droogendijk)
- p417 - Lem8.4.36: "si,tj-path" should be
"vsi,vtj-path"
(Leen Droogendijk)
- p418 - Thm8.4.38: "the j neighbors" should be
"the successors of the j neighbors"
(Leen Droogendijk)
- p423 - Exr8.4.19: "lg n" should be "\ceil{lg n}"
- p423 - Exr8.4.22: "\dlt(G)" should be "\dlt(H)",
and n should be n(G)
- p427 - after Rem8.5.5: The k here is the p of Theorem 8.5.4
(Leen Droogendijk)
- p429 - Theorem 8.5.11: The theorem statement should use k rather
than m to agree with the usage of k in the proof (Leen
Droogendijk)
- p434 - bottom: it is not true that all forests are balanced graphs;
the statement should be for trees (Andrey Ruhkin)
- p444 - Thm8.5.33: the exponent n is missing on the upper bound
in the inequality to be proved by induction in the second paragraph
- p449 - Exr8.5.4: "at least" should be "at most", and it should be required
that there be r vertices in the first partite set and s vertices
in the second (Luis Goddyn)
- p450 - Exr8.5.25: "\rho(G)=\maxG\esub He(G)/n(G)" should
be "\rho(H)=\maxG\esub He(G)/n(G)" (Michael Pelsmajer)
- p470 - Exr8.6.25: it must be required that G and H each
have at least two vertices
- p480 - RemA.27: In the third paragraph, "we began with L"
should be "we began with S" (Alexander Johnson)
- p506 - ExrB.16: "Given a graph G" should be "Given a graph G
without isolated vertices" (Andre Kundgen)
- p515 - Arborescence: "outdegree at most one" should be "indegree at most 1"
(Gitta Marchand)
- p538 - Alon [1990]: the wrong paper is cited; it should be
N. Alon, Transversal numbers of uniform hypergraphs,
Graphs and Combinatorics 6 (1990), 1-4.
- p540 - Bollobás [1981]: the correct citation is Discrete Math.
33 (1981), 1-19 (Simon Spacapan)
- p548 - Ghouila-Houri: the volume number is 251, not 156 (Art Busch)
- p552 - missing reference: Jacobs K. (1969) Der Heiratssatz. In: Jacobs K.
(eds) Selecta Mathematica I. Heidelberger Taschenbücher 49.
Springer, Berlin, Heidelberg. (Jacobus Swarts)
- p561 - missing reference: Richardson M., Solutions of irreflexive relations,
Ann. of Math. (2) 58 (1953), 573-590; errata 60 (1954),
595. (Jacobus Swarts)
- p588 - Whitney's Theorem: the page number should be 161 (Dave Keller)
All subsequent corrections listed on this page WERE MADE for the second
printing of the second edition, EXCEPT for those in the first section below,
which were made later.
Corrections IMPLEMENTED for the fourth printing (this section only)
Note: I was never told about the third, fifth, or sixth printings, so no
corrections were made at those times.
- p8 - Prop1.1.24: Logicians say that there are too many simple graphs to
form a set; graph theorists mostly ignore this. To finesse the difficulty,
just rephrase this statement as "On any set of simple graphs, the isomorphism
relation is an equivalence relation." (Ken Bogart, Gerard Chang)
- p8 - Prop1.1.24: "f -1(x)f -1(y)\in E(H)"
should be "f -1(x)f -1(y)\in E(G)" (Hasnor
Lot)
- p18 - Exr1.1.45: The problem is correctly stated but should be marked
"+". However, the graph given as a solution in the solution manual has a
nontrivial automorphism and hence is incorrect. The next version of
the manual will have a picture of a graph that looks more symmetric but
in fact has no such automorphism (Luis Dissett)
- p50 - Exr1.3.33: The number of vertices should be 1 plus the
binomial coefficient d(x)+1 choose 2, not d(x)
(Reza Dorrigiv). The "k=5" in part (b) should be "d(x)=5"
(Gerard Chang)
- p94 - Exr2.2.26: "Frucht [1979]" should be "Rosa [1967]" (JG)
- p98 - Thm2.3.7: "w(u,z)" should be "w(uz)" (JG)
- p99 - App2.3.9: The name "Guan Meigu", given in the Chinese order, should
be given in the English order "Meigu Guan" for consistency
- p104 - Exr2.3.7: The reference to Exercise 2.1.34 should be to
Exercise 2.1.37 (JG, Gabor Hetyei)
- p105 - Exr2.3.19: The C-L-R reference has now been added to the bibliography
and the author index
- p109 - Def3.1.7: This definition is too restrictive, since sometimes
it is convenient to take the symmetric difference of graphs that don't
have the same vertex set. Having defined symmetric difference of sets,
it should be extended to graphs by letting G\symd H be the subgraph of
G\cup H with edge set E(G)\symd E(H) and no isolated vertices.
(JG)
- p111 - Before Cor3.1.13: The statement about the Marriage Theorem would
be clearer as follows: "If, for some k\in\NN, every man
is compatible with exactly k women and every woman is compatible with
exactly k men, then a perfect matching must exist."
- p118 - Thm3.1.34: Various slight inaccuracies in the proof and figure
are fixed by changing all appearances of "N(S')" to "R", where
R is defined to be the set N(S')\cup S' of vertices dominated by
S'. (The last character of the first paragraph has been corrected from
S to T in the second printing.) For further clarity, after its
first sentence the second paragraph continues as "Since S' is a maximal
independent subset of S, every vertex of S-S' has a neighbor in
S'. Similarly, T' dominates T-T'. Hence S'\cup T'
is a dominating set." In the final paragraph, the second sentence becomes
"Since each vertex of S-S' has a neighbor in S', each such vertex
has at most one neighbor in T', because S'\cup T' is independent
and G is claw-free."
- p122 - Exr3.1.51b: Mentioning diameter in a lower bound requires the
graph to be connected. Here the upper bound can be improved to
n-\ceiling{(2 diam(G))/3}. The lower bound should have the ceiling
function applied to it, at which point one can add "Show that both inequalities
are sharp for all n." (JG)
- p122 - Exr3.1.53: Rem3.1.33 says that the constructions in this exercise
show that its bounds are sharp; this exercise should therefore require minimum
degree 2 and 3 for the examples (FG)
- p122 - Exr3.1.56: The second part is incorrect; there is in fact a
dominating set of five pairwise non-attacking queens on the eight-by-eight
chessboard
- p123 - Exr3.1.57: Restrict to n at least 4 (JG)
- p123 - Exr3.1.58: Restrict to r at least 3 (FG)
- p123 - Exr3.1.59: Restrict to connected graphs (JG) and n > 2
(FG)
- p123 - Exr3.1.60: Restrict to connected graphs, and "\dlt(G)\le k"
should be "\dlt(G)\ge k" (FG)
- p125 - pre-Alg3.2.1: It was not clearly explained how negative weights can
be eliminated. Replace negatives by 0, and then after running the algorithm to
find a maximum weight perfect matching, discard the edges of weight 0 to find a
maximum weight perfect matching in the original problem (Gerard Chang)
- p131 - Thm3.2.18: In order to show that the algorithm terminates, one must
show that no man can be rejected by all the women, after which the argument
about the length of the remaining lists applies. Proving this claim takes
only a few lines, but there is not room on the page for the proof as a
correction, so I have added it as an exercise at the end of the section.
(Gerard Chang)
- p132 - top parg: In the matching listed, "ca" should be "za"
(JG)
- p146 - Exr3.3.12: "one endpoint in T" should be
"at least one endpoint in T"
- p150 - Exm4.1.4: Require k to be at least 2 (Don Monk)
- p152 - Def4.1.7: These definitions of k-edge-connected and
edge-connectivity should be restricted to graphs with at least two vertices,
and the edge-connectivity of K1 should be taken by convention
to be 0 (FG)
- p153 - above Them4.1.11: "has diameter 2" should be "has diameter 2 and
is simple" (FG)
- p160 - Exr4.1.26: F should be restricted to be nonempty
- p160 - Exr4.1.29: It would be clearer to add "of G" after "bond"
- p163 - Def4.2.7: The definition given for "ear" is inadequate, as it allows
a graph to grow through a cut-edge. It should be this: "An ear of a
graph G is a path that is maximal with respect to internal vertices
having degree 2 in G and is contained in a cycle in G."
(Dan Pritikin)
- p165 - Prop4.2.13: In the containment inequalities specifying the main
case, "S" should be "S\cap D" (Shive Bansal)
- p172 - Thm4.2.25: in line 2 on this page, the definitions should be
I={i\in[m]: ai\notin R} and
J={j\in[m]: bj\notin R} (also similar correction to example,
labels I,J,R added to figure, and fuller explanation of last line
of proof) (JG)
- p173 - Exr4.2.10: should be (+)
- p174 - Exr4.2.19: "belong to a common cycle" should be "equal or belong
to a common cycle"
- p203 - Exr5.1.50: last line missing from bottom of page, should be
"minimizing \sum e(Gi)/ki has the desired
property.) (Lovász [1966])"
- p216 - Exr5.2.14b: k should be at least 2
- p270 - Exr6.3.10: "Tovey-Steinberg" should be "Steinberg-Tovey" (and the
citation on p565 should move one page earlier)
- p296 - Exr7.2.18: "two graphs" should be "two nontrivial graphs"
(the factors should have at least two vertices each)
- p297 - Exr7.2.26-7: in these problems, n must be at least 2
- p305 - Def7.3.11: "3-colorable" should be "3-edge-colorable"
(Candida Nunes da Silva)
- p307 - first paragraph: Tait's Theorem states this equivalence for the
duals of plane triangulations, not for the triangulations themselves
(Candida Nunes da Silva)
- p310 - before Thm7.3.25: The sentence beginning "Nevertheless" should end
with "in cubic 3-edge-colorable graphs" (the Petersen graph is cubic but
not 4-flowable) (Candida Nunes da Silva)
- p325 - Exm8.1.13: "c,e,d,b,h,g,a,u" should be
"c,e,d,b,h,u,g,a", and the reverse order should be similarly corrected.
Also, "the graph G above" should refer explicitly to the graph
illustrating Theorem 8.1.11. (Yaokun Wu)
- p336 - Exm8.1.36: the last line is nonsense - showing that the only
p-critical cycle-powers are odd cycles and their complements reduces the
SPGC to showing that all p-critical graphs are cycle-powers
- p338 - Thm8.1.39: all of the constant vectors of 1s in the first display
should have a transpose indication on them (Yaokun Wu)
- p352 - Exm8.2.13: "``augments'' I2" should be
"``augments'' I1"
- p376 - Exr8.2.46: there is no "graph below" - just construct a graph and
an abstract dual of it that is not a geometric dual of it
- p393 - Exr8.3.13: "(3k-1)/2" should be
"(3k+1)/2" (Gerard Chang)
- p403 - Thm8.4.18: In the last paragraph on the page,
"{fi(k),fj(k)}" should be
"{fk(i),fk(j)}" (Sandeep Joshi)
- p419 - Thm8.4.40: the originator of this proof is Feng Tian, not Tian Feng
(in Western notation); the family name is Tian. Prof. Tian has recently found
a proof that is still shorter than the 1988 proof presented here
- p426 - Rem8.5.5: the numbers don't make any sense. Better would be
"The probability that a random 64-vertex graph has a 10-clique or independent
10-set is bounded by ((26)10/10!)2-44, which
is less than .03. If the first random one has such a 10-set, generate another.
The probability of continued failure is the product of numbers less than 1
and soon becomes incomprehensibly small." (Borys Bradel)
- p437 - second paragraph: the text says that when pn is a constant
larger than 1, the number of vertices outside the giant component becomes
o(n). This is wrong. The point is that the order of the largest
component becomes linear in n, and the fraction of the vertices
contained in it depends on c. Outside the component, the fraction is
1 minus this, so again the number of vertices is linear in n
(Jerry Grossman)
- p452 - Exr8.5.39: the first right parenthesis should be deleted (Jozef Skokan)
- p452 - Exr8.5.40: the first right parenthesis should be deleted (Jozef Skokan)
- p458 - Thm8.6.16: should be restricted to connected graphs
- p486 - ThmA.42: In the last line of the page, the dot should be
three dots (Don Monk)
- p503 - ThmB.10: In the next-to-last paragraph, "P" should be
"Q" twice in the first sentence (Andre Kundgen)
- p546 - Feng, T.: should be Tian, F.
- p551 - P. Hall: "representation" should be "representatives" (David Pike)
- p572 - Lucas/Luczak: the mention of Lucas should be deleted from the
line for Luczak (Jozef Skokan)
- p583 - "Nordhaus-Gaddum Theorem": the missing page reference is 202
(David Pike)
Corrections for Chapters 1-7 IMPLEMENTED for the second printing
- p32 - Exr1.2.19: False as stated; the vertex set should be the set of
congruence classes mod n, with i and j adjacent if
and only if they have elements differing by r or s.
- p36 - figure: upper left vertex of lower square should be "010"
(Arnoud Hobbel)
- p37 - Prop1.3.9: "an X,Y-bigraph" should be "a k-regular
X,Y-bigraph" (JG)
- p37 - Prop1.3.11: In the display, "dG(vi)"
should be "dG(vj)" (Mozart Menezes)
- p37 - Prop1.3.11: "\sum(G-vi)" should be
"\sum e(G-vi)" (JG)
- p41 - Thm1.3.23: "Kn,k,k" should be
"Kn-k,k" (JG)
- p49 - Exr1.3.19: G should be restricted to be simple
- p49 - Exr1.3.22: the statements are not valid for graphs containing
K4; "triangle-free" should be added to the hypotheses
on G (also at one point the argument needs the graphs to be simple)
- p54 - before Def1.4.3: "(head, tail)" should be "(tail, head)"
(JG)
- p63 - Exr1.4.6: "D4" should be "D3"
(since D4 is shown in the text)
- p63 - Exr1.4.12: the definition of connection relation on p60 (index
incorrectly said p59) was not what is needed here. Thus this exercise should
be "For a digraph D, define a relation on V(D) that is satisfied
by the pair (x,y) if D has an x,y-path and a
y,x-path. Prove that this is an equivalence relation and that its
equivalence classes are the vertex sets of the strong components of D."
(JG)
- p64 - Exr1.4.15: "0\le n" should be "0\le j\le n" (JG)
- p64 - Exr1.4.16: Both parts should require n
to be a prime number.
- p68 - Thm2.1.4: condition D should also forbid loops (Mark Ellingham)
- p70 - Prop2.1.7: in the explanatory paragraph at the end of the proof
referring to the figure, the roles of T and T' should be switched
(JG)
- p77 - Exr2.1.38: the last "T'" should be "T" (JG)
- p84 - Exm2.2.6: the last spanning tree in the figure should be a star
centered at the lower-left vertex (JG)
- p93 - Exr2.2.14: "vertex [n]" should be "vertex set [n]"
(JG)
- p94 - Exr2.2.24: The question should be "Of the graphs with vertex set
{0,...,n-1} that have n-1 edges, how many are gracefully labeled
by their vertex names?"
- p103 - Exr2.3.4: The missing "graph below" was the graph obtained from
K5 by deleting two non-incident edges (Ed Pegg)
- p118 - Thm3.1.34: first paragraph should end with "T", not
"S" (JG)
- p119 - Exr3.1.15: part (a) was valid only for k at least 2
(Thyagarajan Nandagopal)
- p122 - Exr3.1.41: not true in the generality stated; should be "Let G
be a non-bipartite graph having exactly one cycle, C. Prove that
\alpha(G)>=(n(G)-1)/2, with equality if and only if G-V(C) has a
perfect matching
- p122 - Exr3.1.51: restrict to simple graphs and reverse the first inequality
sign
- p126 - Def3.2.6: "ui...vn and
vj...vn" should be
"u1...vn and
v1...vn"
- p137 - Thm3.3.3: At the bottom of the page, the set in which the 1-factor
is to be found is the symmetric difference together with {xy,yz}
- p138 - Thm3.3.3: Just before the end, we produce a 1-factor of
C+{xy,yz}, not a 1-factor of C (JG)
- p140 - Thm3.3.9: The degree needs to be positive (David Norris & Aaron
Lippold)
- p141 - Thm3.3.13: "f(v) edges at v" should be
"f(v) vertices of degree 1 corresponding to v" (JG)
- p146 - Exr3.3.9: restrict to graphs without isolated vertices (Dmitry
Fon-Der-Flaass)
- p147 - Exr3.3.19: The hint should refer to Corollary 3.3.8, not
Theorem 3.3.9.
- p155 - Prop4.1.15: "G[]" should be "G[\bar S]"
(Jason Tedor)
- p158 - Exr4.1.6: valid only for connected graphs
- p159 - Exr4.1.18: should be restricted to simple graphs
- p159 - Exr4.1.24a: should be restricted to n\ge4
(Carey Radebaugh)
- p164 - Def4.2.9: "closed ear in G" should be "closed ear in
"P0\union...\unionPi" (JG)
- p164 - Def4.2.11: as in the undirected case, the complete doubly-directed
digraph has no separating set; take its connectivity to be the number of
vertices whose deletion reduces it to a single vertex
- p165 - Prop4.2.13: "nonempty vertex subset" should be "nonempty proper
vertex subset" (JG)
- p167 - Thm4.2.17: "v\in(V1\cap V2)"
should be "v\in(V1\cap V2)-S". Also,
"V(G1)\cap V(G2)" should be
"V1\cap V2". Also, at the bottom
"{x" and "y}" should be "{x}" and "{y}"
(JG)
- p168 - Thm4.2.17: in the top paragraph, the last two occurrences of
"v" should be "u" (JG)
- p179 - Alg4.3.9: "f(uv>0)" should be "f(uv)>0" (JG)
- p179 - Exm4.3.10: "u,v" should be "u,x" (JG)
- p185 - Thm4.3.18: the theorem statement was missing the condition that
\sum pi = \sum qj
- p193 - Exm5.1.10: the notation for the cartesian product was introduced by
Nesetril [1981], not Rodl
- p199 - Exr5.1.6: "\chi(H)k=\omega(H)k+k"
should be "\chi(Hk)=\omega(Hk)+k"
- p200 - Exr5.1.17: "\chi(G)\le4" should be "\chi(G)\le3"
- p203 - Exr5.1.44b: the missing quantity to be minimized is
1+r(D)
- p204 - Exr5.1.51: the attribution has been corrected, but still a hyphen
between "k+1" and "coloring" was missing
- p206 - Thm5.2.3: "no two edges" should be "no two vertices" (Jozef Skokan)
- p212 - Thm5.2.20: The last sentence on the page should end
"H'+xy" (JG)
- p216 - Exr5.2.17: drop "and that this bound is sharp" in part a.
The bound is not always sharp; consider for example n=12 and
m=63
- p216 - Exr5.2.22: "has a transmission range of six miles" should be
clarified to "can transmit to other stations within a radius of three miles"
(Andreas Eisenblaetter)
- p217 - Exr5.2.27: "m-vertex" should be "n-vertex"
(Andreas Eisenblaetter)
- p222 - Thm 5.3.8: before "has" in the statement, it would be better
to add "of a simple graph G"
- p224 - Exm5.3.13: "If we have colored
v1,...,vi" should be
"If we have colored v1,...,vi-1" (JG)
- p224 - after Remark 5.3.14: the cycles without simplicial elimination
orderings are those of length at least 4, not 3 (David Piwinski)
- p229 - Exr5.3.4: "F" should be "H" (JG)
- p229 - Exr5.3.6: "graph" should be "simple graph"
- p243 - Exr6.1.5: The original statement was nonsense; one can make it
a "prove or disprove"
- p265 - Exm6.3.17: In the definition of the example graph G, the
number of copies of the complete graph should be n2/(2m)
- p271 - Exr6.3.15: should be restricted to simple outerplanar graphs
- p272 - Exr6.3.26: the formula for \nu(K6,n) was wrong; the
numerators should be n and n-1, not n-6 and n-7
- p272 - Exr6.3.28: "\nu(Km,m)" should be
"\nu(Km,n)", and the condition (applied when m
and n are odd) should be that m-3 and n-3 are divisible
by 4, not 3
- p272 - Exr6.3.35: the edge bound applies only for simple graphs
- p280 - Thm7.1.16: "Si,...,S1n" should be
"S1,...,Sk", and there are unbalanced set brackets
in the next line (JG)
- p283 - Exr7.1.13: The omitted "graph below" was the complement of the graph
on the left in Exr7.1.1, and its line graph is that graph
(L(G)=\bar{G})
- p285 - Exr7.1.30: "an k-regular graph" should be
"a k-regular simple graph"
- p297 - Exr7.2.32: n must be greater than 2, and it is G' whose
induced subgraph is Kn/2, not G (Jason Tedor)
- p305 - Lem7.3.10: The last paragraph shows that G contains
subdivisions of the graphs obtained by contracting either side of the
cut to a single vertex (JG)
- p315 - Exr7.3.9: "5" should be "3"; the icosahedron has only 12
vertices
Corrections for Chapter 8 IMPLEMENTED for the second printing
- p331 - top: the statement about Meyniel graphs was in the wrong place and
therefore false. Delete "all Meyniel graphs or" from the first line of the
second paragraph (Meyniel graphs *are* strongly perfect, as stated on p330).
Add "does not contain all Meyniel graphs" to the first line of the third
paragraph. (Andreas Eisenblaetter)
- p332 - Thm8.1.26: after "f(wj)=j", append
"for j\in{i+1,...,k}" (JG)
- p339 - Thm8.1.41: "\Chi(G-x) consisting" should be
"(denoted \Theta(G-x)) consisting" (JG)
- p339 - Thm8.1.42: "S2" should be "S'" (JG)
- p339 - Def8.1.43: "adding it" should be "adding an edge joining them"
(JG)
- p341 - Thm8.1.48: at the end of the proof,
"replace {v(a-1)w,vaw,v1,vw}
with {v(a-1)w+1,v0,vw-1}" should be
"replace
{v(a-1)w+1,vaw,v1,vw} with
{v(a-1)w+2,v0,vw-1}"
- p341 - Thm8.1.49: "exactly one of its endpoints" should be
"at least one endpoint of Ax", and "Equality holds" should be
"Equality holds (and no other arc contains both endpoints of
Ax)" (Yaokun Wu)
- p343 - Thm8.1.51: "have the form
vi,vi+w,...,vi+aw" should be "have the
form {vi+jw: 1\le j\le a} (indices modulo aw+1)".
Later, "v(a-1)w+" should be "v(a-1)w+1"
(JG)
- p362 - Thm8.2.39: "B or B*" should be
"B or \overline B"; in next line, "I*" should be
"I*" (JG)
- p363 - before Def8.2.40: the characterization given for the acyclic
subsets of E(G.e) requires that e not be a loop. The dual
description should be phrased by saying that the spanning sets of G.e
are those whose union with e is spanning in G
- p367 - Thm8.2.48: in the display in the center of the page,
"\overline{X}+e" should be "\overline{X+e}" (JG)
- p373 - Exr8.2.10: The intersection and union symbols should be exchanged
(Manish Sharma)
- p375 - Exr8.2.42: on the right side of the rank formula, "F"
should be "\bar F" in both places
- p375 - Exr8.2.44: insert "is binary" between "matroid" and "if"
- p381 - middle: in "at least N incident red edges",
"N" should be "s" (JG)
- p396 - Exr8.3.41: The reference to Exr2.1.37 should be to Exr2.1.40
(JG)
- p415 - Thm8.4.34, last paragraph: "F-decomposition of G"
should be "F-decomposition of H" (JG)
- p416 - Thm8.4.35: In the third line of the proof,
"e(G-x)≥m(n-2)/2" should be "e(G-x)>m(n-2)/2"
(Linda Lesniak)
- p416 - Thm8.4.35: "would yield a longer cycle" should be
"would yield a longer path", and "also has length l" should be
"also has length l-1" (JG)
- p417 - Lem8.4.36, next-to-last paragraph on page:
"G-vt-1" should be "G-vti-1"
(JG)
- p418 - Thm8.4.38: conclusion should end with "c(G) >= min{n(G),c}"
(JG)
- p421 - Thm8.4.42: in the paragraph before the figure, each "v" with a
subscript should be an "x", Also, "S-va+1" should be
"S-{xa+1}".
In the left figure "xa+c" should be "xa+1".
At the end of the next paragraph, "xc-1" should be
"xa+c-1". Three lines before the end,
"va+b belongs to at most m-c+b+2" should be
"xa+b belongs to at most m-c+b+1".
(JG)
- p429 - Thm8.5.11: "n--X" should be "n-X" (JG)
- p432 - Thm8.5.18: the three instances of "Gp" should be
"Gp"
- p446-7 - Lem8.5.36 statement, Exm8.5.37 display, and Exm8.5.38 two lines
before display: the description of the event has an extra right parenthesis
before the inequality(JG)
- p450 - Exr8.5.15: the upper bound in the comment applies only when
k is even (Weiting Cao); the date for the reference is 1974
- p453 - first line: the reference to Corollary 8.2.42 should be to
Corollary 8.2.37
- p453 - Rem8.6.2: "is the coefficient" should be "is the negative of the
coefficient"; "that coefficient is also" should be "that also equals"
- p455 - Lem8.6.8: in the value of Av, "By" should be
"By" (JG)
- p458 - Lem8.6.17: "Rn" should be
"Rn" (JG)
- p464 - Cor8.6.31: second line of proof was missing "(" (JG)
- p464 - before new section: "2\sqrt k-1(1-O(1/d))" should be
"(2\sqrt{k-1}(1-O(1/d))", and "2{\sqrt k}-1" should be
"2\sqrt{k-1}"
- p467 - in the figure on the right, the label "a" should be "x"
(JG)
- p469 - Exr8.6.17: the reference to Exercise 2.2.11 should be to Exercise
2.2.13
The corrections below for Section 8.6 were noted in the first edition but
were overlooked during revision.
- p455 - Thm8.6.9: In B, the statement applies to the nonzero
eigenvalues. In C, there may also be an overall factor of \lambda
(Gunnar Brinkman)
- p461 - Thm8.6.25: the last statement should be for
nonconstant eigenvectors (Dan Pritikin)
- p468 - Exr8.6.12: "s" should be "x"
- p469 - Exr8.6.16: The eigenvalue lower bound on the chromatic number is due
to Alan Hoffman, not Herb Wilf, in "On eigenvalues and colorings of graphs,
in Graph Theory and Its Applications (B. Harries, ed.), Academic Press (1970),
79-91" (Joan Hutchinson)
Corrections for the Appendices IMPLEMENTED for the second printing
- p474 - RemA.12: in the diagram, the superscript "c" should be an
overbar for complementation (JG)
- p483 - Functions, next line: It would be better to write "A function
transforms elements of a set into elements of a possibly different set"
(Chris Gordon-Smith)
- p494 - footnote: the last sentence should say that a function is
bounded by a polynomial in n if and only if it is bounded by a
polynomial in n2 or n3 (JG).
The word that precedes the footnote should be "input", not "problem"
- p497 - ExmB.2: the example given does not work. The correct example:
Distinguish two vertices x and y. Put weight 0 on all edges not
incident to these, weight 1 on all edges incident to exactly one of these, and
weight n on the edge xy. For n\ge4, every cycle found by
the nearest-neighbor heuristic has weight n+2, while the optimal cycles
have weight 4.