Combinatorial Mathematics  Errata, etc.
This page contains supplementary items for the first edition of
Combinatorial Mathematics, by Douglas B. West,
published in July 2020 by Cambridge University Press.
Sections include
mathematical and notational errors,
corrections to references,
comments and updates,
minor typos, and
supplementary exercises.
Send contributions of errors, comments, or supplementary exercises to
dwest@illinois.edu; contributors noted in parentheses.
Locating codes: X=Exercise, T=Theorem, L=Lemma, P=Proposition, C=Corollary,
E=Example, J=Conjecture, R=Remark, A=Application.
I expect that there will be a corrected printing to implement most of
the corrections listed here.
$
\def\nul{\emptyset}
\def\NN{{\bf N}}\def\ZZ{{\bf Z}}\def\RR{{\bf R}}
\def\FF{{\bf F}}\def\PP{{\bf P}}\def\EE{{\bf E}}
\def\FL#1{\lfloor{#1}\rfloor}\def\CL#1{\lceil{#1}\rceil}
\def\C#1{\left{#1}\right} \def\esub{\subseteq}
\def\FR#1#2{{{#1}\over{#2}}} \def\st{\colon\,} \def\join{\vee}
\def\Sb{\overline{S}} \def\cart{\square} \def\CH#1#2{{#1\choose #2}}
\def\XPOL#1#2{\chi_{#1}(#2)}
\def\VEC#1#2#3{#1_{#2},\ldots,#1_{#3}}
\def\D{{\diamond}}
\def\SE#1#2#3{\sum_{#1=#2}^{#3}}
\def\PE#1#2#3{\prod_{#1=#2}^{#3}}
$
Observations attributed to Leen Droogendijk are designated by "(LD)".
 p130 L3.3.33: At the end of the case $k\ne 1$, the sentence beginning
"Since $g$ is a formal power series" is valid only for $k\ge0$. The sentence
should be "Since $g$ is a formal power series, $g^{k+1}$ is a formal Laurent
series, and by the definition the derivative of any formal Laurent series
has residue $0$. Hence the coefficient of $x^{1}$ is $0$, as desired."
(Fanxin Wu)
 p133 X3.3.21: In part (b), the factor
"$i^{\FL{m/i}}$" should be "$i^{\FL{m/(i1)}}$".
 p172 X4.1.14: "$r_i$" should be "$s_i$". (Allan Bickle)
 p248 X5.4.18: "$n(k2)$" should be "$n(k1)$". (Allan Bickle)
 p235 X5.3.3: Part (c) is ambiguously stated. It was intended to be
"For each vertex $v$ in a circuit, the circuit contains a cycle through $v$",
without requiring a single cycle through all the vertices (containment
is in the sense of Lemma 5.3.8).
 p256 R6.1.4 vs preC6.1.6:
Before Corollary 6.1.6 the lower bound from Remark 6.1.4 for the number of
perfect matchings in a $k$regular bipartite graph is compared with the lower
bound from van der Waerden's Conjecture for the same number over $k$regular
bipartite multigraphs with $n$ vertices in each part. The latter is NOT
weaker. The problem is that 6.1.4 does not take $n$ into account, so it is a
lower bound over all $n$. In 6.1.4 the leading behavior of the bound is
$(k/{\rm e})^k$, while using vdW and incorporating $n$ the leading behavior
is $(k/{\rm e})^n$. (Sasha Kostochka)
 p262 X6.1.29: "$y\delta(G)$" should be "$2\delta(G)$" (Jozsi Balogh)
 p321 T7.3.11: The notation in the figure was not defined.
Insert "Let $\bar N(w)=V(G)\{v\}N(v)$".
 p342 X8.1.12: Technically, if $G$ is disconnected, then blocks can also
be isolated vertices.
 p441 X10.1.21: In the hint, $\sum_{i=1}^r$ should be $\sum_{j=1}^r$.
(LD)
 p442 X10.1.37: In part (a), "$\CL{n+1}2$" should be "$\CL{(n+1)/2}$".
In part (b), all runs with size $k$ and stepping by $k$ have the form
$(ki,2ki,\ldots,k^2i)$. This specifies the runs but not their order.
The runs were intended to be put in order from $i=0$ to $i=k1$, as is done
in the given example. (LD)
 p459 X10.2.20: The given lower bound ignores a lowerorder term in the
exponent. (LD)
 p460 X10.2.36: Part (c) is correct as stated, but there is a third lower
bound that is stronger when $r$ and $s$ are small: $r+s+2$. The statement in
(d) that the formula is an upper bound needs this expression to be included
when $2\ge s\ge r2$. The claimed Ramsey number is obtained in
J.W. Grossman, The Ramsey numbers of the union of two stars,
Utilitas Math. 16 (1979), 271279 (also mentioning Rosta's discovery of
the result).
 p462 E10.3.2: "$s_5=45$" should be "$s_4=45$", and now it is also known
that $s_5=161$, in M. Heule, Schur Number Five. Proceedings of AAAI18, (2018),
65986606. (Allan Bickle)
 p474 X10.3.15c: The final theorem in the paper of Gyárfás
and Simonyi states "Any Gallai coloring of $K_n$ has a color with largest
degree at least $2n/5$". This is true, but it is weaker than the statement
of the Ramsey number. When $m$ is even, setting $n$ to be the smallest value
that forces a rainbow triangle or monochromatic $K_{1,m}$ in their formula
only guarantees a color with degree at least $m1$. The correct answer for
$m\ge3$ is $(5m3)/2$ when $m$ is odd, $5m/23$ when $m$ is even. The case
$m=4$ seems to require an ad hoc argument. (LD)
 p482 proof at page top: In the fourth paragraph, "The reduced graph
$R$ with vertex set $\VEC v1n$" should be "The reduced graph $R$ with vertex
set $\VEC v1k$. (LD)
 p491 X11.1.29: The $t$ to be used in the special case for $r=2$ is the
smallest $t$ such that the inequality of part (c) is satisfied.
(LD)
 p492 X11.1.34: The needed condition $n\geV(F)$ was omitted from the
problem statement. When $n \lt V(F)$, the only $F$saturated $n$vertex
graph is $K_n$, which may have more edges than the claimed bound.
(LD)
 p492 X11.1.42: Part (b) should request showing that there are
asymptotically at least $\FR14(12\epsilon)(d\epsilon)^4n^4$ such $4$cycles.
(LD)
 p495 L11.2.10  T11.2.11: In the lemma, it is better to allow $i\ne j$,
and in the proof of the theorem, the definition of dominant element should
restrict to sets $x$ not containing $i$. (LD)
 p497 T11.2.14: In the last paragraph, "all sets above $\partial A$"
should be "all sets above $\partial A$". (Stephen Hartke)
 p495 T11.2.18: "immediately following some $a_1$" should be
"immediately following some $a_i$". (LD)
 p505 L11.2.34: "Since lg is strictly convex" should be
"Since $$lg is strictly convex". (LD)
 p506 D11.2.36: "When $Y$ is a random variable and $E$ is the event $Y = y$,
taking the weighted average of these distributions over the distribution of $Y$"
should be "When Y is a random variable, taking the expectation of these
entropy values over the events of the form $Y=y$". (LD)
 p509 L11.2.44 proof: The equality in the middle of the displayed formula
should be "$\le$". (LD)
 p512 X11.2.32: "size at most 2" should be "size 1 or 2". If the conjecture
holds for families containing the empty set, then it holds in general. (LD)
 p513 X11.2.40: In the Comment, "$\PE j1n$" should be "$\PE j1d$". (LD)
 p539 X11.3.44b: The matroid must be loopless. (LD)
 p540 X11.3.59c: "Without using other results, use part (a) directly" should
just be "Use part (a)". Part (a) can be proved simply, without using the
Matroid Intersection Theorem, but then the Matroid Intersection Theorem is
needed to restate (a) in a way that leads to (c).
 p548 T12.1.21: "$k\gt\alpha(G)$" should be "$k\gt\alpha(D)$". (LD)
 p566 X12.2.16: The notation "${\bf 2}^{[n]}$" is left over from more
advanced material and is not used in this book. All instances of
"${\bf 2}^{[k]}$" or "${\bf 2}^{[n]}$" should be "${\bf 2}^{k}$" or
"${\bf 2}^{n}$", respectively. See also p570 E12.3.6, p571 before C12.3.8,
and p590 E12.4.17. (LD)
 p577 T12.3.29: For consistency, "$A_x$" should be "$A$". (LD)
 p585 before D12.4.2: "$[a_x,b_x]$" should be "$[a_z,b_z]$". (LD)
 p589 E12.4.12: "when viewed in all of ${\bf 2}^P$" should be
"in the subset lattice"
 p589 E12.4.13: "Example 12.4.13" should be "Example 12.2.13". (LD)
 p595 before T12.4.34: "${\bf P}(AB)$" should be "${\bf P}(A\cap B)$"
(LD)
 p595 T12.4.34: The denominators should be $2^n$, and the inequality
should be "$\ge$". (LD)
 p601 D12.4.43: "$\VEC H1k$" and "$H_i$" should be "$\VEC G1k$" and "$G_i$".
(LD)
 p605 X12.4.16: In part (c), "$M_{n+1}$" should be "$M_n$".
 p606 X12.4.20: It should be indicated that the parts of partitions are
listed in nonincreasing order, and again in X12.4.21 zeros are appended.
(LD)
 p607 X12.4.34: "on a distributive lattice" should be "on a finite
distributive lattice". (LD)
 p616 L13.1.22: In the statement, "$b_3^3$" should be "$b_3^2$".
(Ojoung Kwon)
 p631 after D13.2.17: "$z(m,n;3,2)$" should be "$z(m,n;2,3)$", since no
two circles have three common points. (Michael Pelsmajer)
 p631 T13.2.19 proof: $\CH yt$ is a convex function of $y$ only for
$y > t1$, but that is where we need it. When the number of edges is maximized,
every vertex in $x$ has degree at least $t1$. (Michael Pelsmajer)
 p632 E13.2.22: "prime power and $n=$" should be "prime power such that
$(q1)/s$ is an integer and $n=$" (this restriction on $s$ is needed).
Also, "an element $\omega$" should be "an element $w$". (LD)
 p633 T13.2.23: In the final line of the proof, "$a_1$" should be "$a_i$".
(Ojoung Kwon)
 p638 X13.2.78: These two problems require an understanding of what a
finite field is that was unfortunately omitted from the text. When $q=p^k$
for a prime number $p$, the finite field $\FF_q$ can be described as the
congruence classes of polynomials over $\FF_p$ modulo a fixed unfactorable
polynomial $f$ of degree $k$ in $x$. Each class has a representative
polynomial of degree less than $k$. Powers of $x$ at least $k$ can then be
reduced to lowerdegree polynomials. The element $x$ is a "primitive" element;
its powers from $0$ through $q2$ are the nonzero elements of the field, with
$x^{q1}=1$.
 p639 X13.2.10: Part (c) should be restricted to $t\ge2$. (LD)
 p655 X13.3.7: The definition of $(i,j)$difference is inadequate.
After the missing period to end the first sentence, it should read
"A value $a\in\ZZ_v$ occurs as an $(i,j)$difference in a set
$D\esub\ZZ_v\times\ZZ_m$ when there exist $x_i,y_j\in D$ with $a=xy$."
Thus in the mixed difference system $D_1,\ldots,D_t$, differences are taken
only within each individual set $D_h$. (LD)
 p656 X13.3.27: "not containing $v$, obtain a $(15,3,1)$design" should be
"not containing $u$, obtain a $(6,3,2)$design". This part of the exercise
is the same as X13.3.10. (LD)
 p663 T14.1.5: "$k$ vertices with degree $k=1$" should be
"$k$ vertices with degree $k1$".
 p667 X14.1.19: One must also assume that the plane is fully booked.
(LD)
 p668 X14.1.27b: The denominator in the given formula should be
"$2\CL{n/2}1$", not "$2\cdot(\CL{n/2}1)$". (Jameson Neff)
 p684 X14.2.8: "Given $S\subseteq V(G)$" should be "Given $S\subset V(G)$".
(LD)
 p684 X14.2.10a: "union of disjoint triangles" should be
"union of edgedisjoint triangles". (LD) More subtly, "if and only if it has
no" should be "if and only if the given list of edgedisjoint triangles has
no". Forbidding two triangles on four vertices from the *graph* already
trivially makes the graph locally linear.
 p684 X14.2.15: For clarity, the inequality in the second line should be
labeled (*), and then in part (c) "Reed's Conjecture" should be "(*)".
(LD)
 p686 X14.2.23: Although the additive constant can be reduced, for the goals
of this exercise it suffices to solve it with "2.5" in place of "2.25".
 p690 T14.3.10: Since the notation $\bar N(v)$ was not defined, replace
"when there is no vertex $v$ with $S\subseteq N(v)$ and $T\subseteq\bar N(v)$"
with "when no vertex is adjacent to all of $S$ and none of $T$". (LD)
 p697 T14.3.29: At the end of the proof, "${\rm e}^{(d1)^2}/4$" should be
"${\rm e}^{(d1)^2/4}$"
 p703 X14.3.19: In the comment, "$n2\log n$" should be "$n2c\lg n$".
 p704 X14.3.29: The two expressions given for the moment generating function
are inconsistent: "generating function $\sum a_nx^n$" should be
"exponential generating function $\sum a_nx^n/n!$". (LD)
 p704 X14.3.32: "$n(20c^2)$" should be $n/(20c^2)$. (Misha Lavrov)
 p704 X14.3.32: $\ln n/\ln \ln n$ is not quite sufficient for an easily
provable upper bound on $\Delta(G)$ whp. $(1+\epsilon)\ln n/\ln\ln n$ and
even $\ln n/(\ln \ln n2\ln\ln \ln n)$ are sufficient. Frieze and Karonski
[2016, Theorem 3.4] showed that whp the maximum degree is between
$\ln n/(\ln \ln n+2\ln\ln \ln n)$ and
$\ln n/(\ln \ln n2\ln\ln \ln n)$. (Misha Lavrov)
 p705 X14.3.36: In the first line, "the number of vertices" should be
"the expected number of vertices".
 p706 before E14.4.1: "$\EE(X\EE(X))$" should be "$\EE((X\EE(X))^2)$"
(LD)
 p708 T14.4.4: The proof as stated is not valid for the case $t=q$,
which becomes $\PP(X\ge n)=p^n$. Nevertheless, this quantity is still bounded
by ${\rm e}^{2nt^2}$, which is now requested as a supplementary exercise below.
(Kevin Milans)
 p708 T14.4.4: In the last line of the proof, the notation for integrating
twice is faulty: "$f(t)=\int_0^t\int_0^t f''(s)ds\le 2t^2$" should be
$f(t)=\int_0^t\int_0^s f''(r)dr ds
\le \int_0^t\int_0^s(4dr) ds =\int_0^t(4s)ds =2t^2$. (Kevin Milans)
 p722 X14.4.13: This exercise is stated as Exercise 5.1 on page 46 of
MolloyReed [2002], with different parameter names. The statement as given both
here and there is false. "every edge has size at least $r$" should be "every
edge has size at most $r$". For simplicity, assume that every edge intersects
at most $k$ edges (including itself), and then $k\le {\rm e}^{\alpha^2/2r}/8$
suffices. (Kevin Milans)
 p744 X15.1.3a: "$n$, with equality possible when $n$ is odd" should be
"$n$ when $n$ is odd, with equality possible". Otherwise, the best way to
complete (a) for even $n$ is to prove (b). (LD)
 p745 X15.1.13: The comment is garbled and unhelpful and should be
eliminated (LD)
 p745 X15.1.15: "$\RR^2$" should be "$\RR^n$". (LD)
 p745 X15.1.17: The result can be found in FranklWilson [1981].
 p745 X15.1.18: This exercise is badly misstated. The vertex set should
be $\CH{[t]}3$, and the conclusion should be $R(t+1,t+1)\gt\CH t3$. The
corrected problem in fact is a repeat of Exercise 10.2.17.
 p762 X15.2.1: "graph" should be "multigraph".
 p763 X15.2.8: The reference to X10.1.28 is incorrect; it should be to
X5.3.59. The text never actually defines a de Bruijn cycle. Given $k,n\in\NN$,
it is a $k$ary cyclic arrangement of length $k^n$ in which the segments of
length $n$ are distinct.
 p766 X15.2.34c: "$\varnothing$" should be "$\{0\}$". (Stephen Hartke)
 p780 X15.3.3: "obtained from $G$" should be "obtained from a $k$regular
graph $G$ with girth greater than 4". (John Caughman)
 p790 T16.1.20: It is not true that assigning each vertex the triple of its
heights in a 3dimensional realizer produces a barycentric representation,
even after projecting to the plane $x+y+z=1$ and normalizing to make all
coordinates nonnegative. There seems to be no easy way to obtain a barycentric
representation directly. However, projecting the embedding given by the
realizer for both the vertices and the edges into that plane (or $x+y+z=0$)
does give a straightline embedding of the subdivision graph. See page 129 of
Trotter's 1992 book Combinatorics and Partially Ordered Sets: Dimension
Theory. (Michael Pelsmajer, Stefan Felsner)
 p794 T16.1.31: There is a difficulty with points appearing in only two
unit pairs, since the circle around such a point generates two copies of the
same edge. The best fix is to iteratively delete points lying in at most
two unit pairs (this also replaces the argument of the first paragraph).
Since $4n^{4/3} > 4(n1)^{4/3} + 2$, the bound we obtain for the resulting set
suffices. (Michael Pelsmajer)
 p798 X16.1.23: The bound should be $4n^{2/3}m^{2/3}+m$, not
$4n^{2/3}m^{2/3}$. (Michael Pelsmajer)
 p818 T16.2.41: "(see Theorem 14.4.4)" is an errant reference for the bound
on the sum of the initial binomial coefficients. The bound can be obtained
as a special case of the bound (4.3) on the lower tail of the binomial
distribution proved on pp133134 of E.M. Palmer, Graphical Evolution
(WileyInterscience, 1985). The general result appears below as a supplementary
exercise for Chapter 14.
 p843 X10.1.19: $S$ in the hint refers to a given multiset of $k$ positive
integers with sum $n$. (LD)
 p843 X10.2.32: "$(x)+d(y)$" should be "$d(x)+d(y)$".
(LD)
 p844 X11.1.8: The coordinates are indexed by $[n]$, not by vertex names.
Hence the phrasing should be "if $v_iv_j\notin E(G)$ and $x_i,x_j\ne 0$, then
$f(x')\ge f(x)$ for some $x'$ such that $x'_ix'_j=0$." (LD)
 p844 X11.1.39: The suggestion to show $\alpha'(G)\gt n\delta(G)$ is
irrelevant, and the augmenting path will have length at most $5$.
(LD)
Due to an error in the crossreferencing program, it seems that every
citation that appears in the first paragraph of any page has been recorded
in the references as being on the preceding page. When looking for where an
article is cited, please check the first paragraph of the subsequent page if
you can't find it on the page listed.
 p105 X3.1.27: Another bijection relating these sets appears in
W. Y. C. Chen, The skew, relative, and classical derangements,
Discrete Math. 160 (1996), 235239. (David Callan)
 p174 X4.1.39: The inclusionexclusion argument for this formula may appear
in Brualdi's book as early as the 1992 edition.
 p249 X5.4.27: 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. Shi [1988] proved roughly
$f(n)\ge\sqrt{2n4}$. The CM text misstates the result of
ChenLehelJacobsonShreve [1998], which is $f(n)\le O(\sqrt{n\log n})$
(also proved earlier in Lai [1990]). Lai [2020] improved the lower bound to
$f(n)\ge 1.55\sqrt n$,
and BorosCaroFürediYuster [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 BorosCaroFürediYuster [2001], upper bound in
MaYang [2021]. (Chunhui Lai)
 p349 R8.2.15: "Dirac [1952b]" should be "Dirac [1952a]", as in
T8.2.17. (Allan Bickle)
 p355 X8.2.31: The first part is stated without proof in
O. V. Borodin, Bidegree of graph and degeneracy number, Mat. Zametki 53 4
(1993), 1320. The final conclusion for listchromatic numbers appears
in the ErdősRubinTaylor [1979] paper. (Allan Bickle)
 p565 X12.2.8: The citation to West [1980] is incorrect! That paper gives
a symmetric chain decomposition for $L(4,n)$. The result for $L(3,n)$ is due
to Lindstrom [1980] (European J. Combinatorics 1, 6163).
 p6323 E13.2.22 and T13.2.23: The citations for Füredi 1996b and
1996c are reversed (also p639 X13.2.14).
 p900 Mabry: The page numbers are 119122, not 119112. (Allan Bickle)
 p925: "W.H. Wiedemann" should be "D.H. Wiedemann"
 p26 T1.2.3(5): When explaining the Summation Identity using lattice paths,
the term $\CH kr$ counts the paths to $(r+1,n4)$ in which the height of the
last horizontal step is $kr$. (Silpian D.)
 p65 X2.1.61: Further and more general references include
M. Desjarlais and R. Molina, Counting spanning trees in grid graphs, Congressus
Numerantium, 145 (2000) 177185;
F. J. Faase, On the number of specific spanning subgraphs of the graphs $G\times
P_{n}$, Ars Combinatoria, 49 (1998) 129154; and
P. Raff, Spanning Trees in Grid Graphs, (2008),
https://arxiv.org/abs/0809.2551. See sequence A001353 of OEIS.
(Allan Bickle)
 p114 X3.2.12 and p116 X3.2.33: Unfortunately, these two are the
same exercise, in slightly different notation.
 p128 X3.2.28: An excellent exercise; should be marked ($\D$).
There should be a hint in the back reminding solvers to be careful about which
square root of $(12p)^2$ makes sense. With this, the computations in parts
(a) and (b) both work out nicely for the relevant values of $p$.
(Kevin Milans)
 p150 X3.4.26: This problem is worthy of ($\D$).
 p207208 X4.3.13,19,20: These are fairly long for ($\D$) exercises.
 p228 X5.2.34 and p255 C6.1.5: A proof of C6.1.5 by directly improving a
given orientation is requested in X5.2.34.
 p2701 D6.2.17T6.2.19: This is wonderful material but should have been
marked optional; it is beyond the basic course.
 p273 X6.2.20: There is nice noninductive proof using augmenting paths.
 p297 X7.1.25: Parts (a) and (b) are suitable exercises separately.
 p317 E7.3.3 and p330 X7.3.23: Tutte actually wrote "it is tempting to
conjecture", which is perhaps not quite conjecturing. A paper by Brinkmann,
Goedgebeur, and McKay (see https://arxiv.org/pdf/2101.00943.pdf)
(1) points out that the graph found by Georges is the first of an infinite
family found also by A.K. Kelmans in Cubic bipartite cyclic 4connected graphs
without hamiltonian circuits, Russian Mathematical Surveys, 43 (1988),
205, and
(2) shows that 50 is the smallest order of a counterexample to Tutte's
"conjecture". (Allan Bickle)
 p330 X7.3.16: The analysis of $m$by$n$ boards in general is by
A. Schwenk in Which rectangular chessboards have a knight's tour?,
Math. Mag. (1991), 325332. (Allan Bickle)
 p335: A more recent book with substantial material on graph coloring is
G. Chartrand and P. Zhang, Chromatic Graph Theory, CRC Press, 2009.
(Allan Bickle)
 p338 P8.1.12: The term "colouring number'' was used in this way by
P. Erdős and A. Hajnal as early as On chromatic number of graphs and
setsystems, Acta Math. Acad. Sci. Hungar. 17 (1966), 6199, where they
comment that P8.1.12 is "well known". (Allan Bickle)
 p344 X8.1.40: Finck [1968] also characterized the extremal graphs.
(Allan Bickle)
 p356 X8.2.35: Note that $K_{3,3,1}$ is the join of $K_{3,3}$ and $K_1$,
illustrating that the list chromatic number of the join of $G$ and $H$ may
be less than the sum of the list chromatic numbers of $G$ and $H$.
(Allan Bickle)
 p357ff Section 8.3: A brief presentation of the history of edgecoloring
appears in B. Toft and R. Wilson,
Discrete Mathematics Letters 6 (2021), 3846.
 p353 X8.2.7 and p375 X8.3.42: Dirac [1960] showed that $n$vertex graphs
with more than $2n3$ edges contain a $K_4$subdivision. In Dirac [1964],
he showed that the $n$vertex graphs with $2n3$ edges having no
$K_4$subdivision are the $2$trees. (Allan Bickle)
 p377 intro: Another book on topological graph theory is
A. T. White, Graphs of Groups on Surfaces, Interactions and Models,
(NorthHolland, 2001). (Allan Bickle)
 p402 bottom and p421 X9.3.35: The Mirzakhani graph is also $3$colorable.
(Allan Bickle)
 p418 X9.3.15: The fact that the LederbergBosákBarnette graph
is the smallest example was proved by D.A. Holton and B.D. McKay in
The smallest nonhamiltonian 3connected cubic planar graphs have 38 vertices,
J. Combinatorial Theory (B) 45 (1988), 305319.
 p419 X9.3.24: This exercise generalizes Exercise 8.1.29.
The partitioning of the vertices of a planar graph into sets inducing a
1degenerate and a 3degenerate graph is indeed a special case of the
easy general statement requested here, but in fact Thomassen proved the
stronger statement that the vertices can be partitioned into sets inducing a
1degenerate and a 2degenerate graph (his definition of kdegenerate was
shifted by 1 from ours). (Allan Bickle)
 p438 J10.1.3334: The ErdősFaberLovász Conjecture has been
proved for sufficiently large $n$ by D.Y. Kang, T. Kelly, D. Kühn,
A. Methuku, and D. Osthus in "A proof of the ErdősFaberLovász
Conjecture", arXiv:2101.04698.
 p441 X10.1.18: It is better to ignore the ceiling function in the upper
bound.
 p449 after D10.2.10: There is now another known threecolor Ramsey number:
$R(3,3,4)=30$, in M. Codish, M. Frank, A. Itzhakov, and A. Miller, Computing the
Ramsey Number R(4,3,3) using abstraction and symmetry breaking, Constraints 21
(2016), 375393. Also the dynamic survey of small Ramsey numbers has been
updated with many improvements to the upper bounds. (Allan Bickle)
 p460 X10.2.32: One can also ask when $k=3$ to guarantee a monochromatic
subgraph with more than half the vertices if $n$ is not divisible by $4$.
 p490 X11.1.21: In fact, there are exactly two extremal graphs.
 p490 X11.1.22: Add "(Hint: Use induction on $n$ and prove the statement
more generally for multigraphs.)"
 p511 X11.2.13: Maybe this should be a (+) problem, since the construction
is not given.
 p539 X11.3.51: A better exercise would be to prove the following:
(a) The intersection of two closed sets is closed.
(b) If $X$ and $Y$ are closed sets with $Y\esub X$ and
$r(Y)=r(X)1$, then $M$ has a hyperplane $H$ such that $Y=X\cap H$.
(c) The closed sets are the intersections of hyperplanes, with a
closed set of rank $r(M)k$ being the intersection of $k$ hyperplanes.
(d) The union of two closed sets need not be a closed set.
 p566 X12.2.18: This exercise is here because it shows that the chains in
E12.2.12 are the same whether generated from the top down or the bottom up.
 p567 X12.2.24: For consistency with Chapter 6, the term defect
should have been used here instead of deficiency, and strong Hall
property should have been strong Hall condition for $Y$. (LD)
Note also that the matching joining the copies of $Y$ can be any matching.
Part (a) should have given the hint to use the KönigEgerváry
Theorem. This exercise is in fact a stronger result than the AndersonGriggs
result at T12.2.26, using a supplementary exercise given below.
 p567 X12.2.25: It is clearer to change the word "consecutive" to "adjacent".
Also, the reference to E12.2.34 should probably be to P3.1.15. (LD)
 p583 X12.3.16: "putting $Y$ over $X$" should be
"putting $Y$ over $X$ (see Definition 12.3.17)".
 p607 X12.4.39: The definitions of semimodular and modular lattices used in
this exercise are different from those given in R12.4.33. They are in fact
equivalent. Nevertheless, the exercise just asks for a relationship for
lattices under the definition given in the exercise. (LD)
 p622 X13.1.2: This is harder than a typical "()" exercise.
 p659 R14.1.4: It may be better to give the formula
$\left({64\atop10}\right)2^{44}$ for the upper bound and say that it is
about .00861 . (LD)
 p666 X14.1.4: Consider also what happens when the individual absence
probability is $.2$.
 p667 X14.1.15: For clarity, "if and only if $K_{n,n}$ is $L$colorable
when each part has $E(H)$ as its color lists" would be better as
"if and only if $K_{n,n}$ is $L$colorable when $L$ uses $E(H)$ as the lists on
each part". (LD)
 p669 X14.1.47: For clarity, "one labeled 1" should be
"one labeled 1 (loops allowed)". (LD)
 p692 L14.3.16: Pedagogically, this lemma should be followed immediately
by an example computing $\EE(X^2)\EE(X)^2$ for a binomial random
variable.
 p709 T14.4.6: The "extension to arbitrary ranges" requested in Exercise 11
is not so easy following this method exactly. Instead of using the AMGM
Inequality, obtain a bound individually on $\EE({\rm e}^{u(X_i\EE(X_i)})$.
 p747 X15.1.33: The 2001 conjecture by Ramamurthi that the hypergraph of
facial vertex sets of a planar graph is $2$choosable was proved (and
strengthened) in C. Thomassen, 2listcoloring planar graphs without
monochromatic triangles, J. Combin. Theory Ser. B 98 (2008), no. 6,
13371348. (André Kundgen)
 p792 T16.1.26: An engaging article about the early history of the
crossing number problems for complete graphs and complete bipartite graphs
is L.W. Beineke and R. Wilson, "The early history of the brick factory
problem," The Mathematical Intelligencer 32 (2010), 4148. The
conjectured optimal drawing seems to be due to the British artist Anthony Hill
in the late 1950s.
 p793 T16.1.28: Eyal Ackerman proved that the lemma holds with $1/29$
instead of $1/64$ in the lower bound if $m > 7n$. (Laszlo Szekely)
 pxvi: In line7, "latin" should be capitalized. (Chris Jeuell)
 pxix: Regarding the result of Grytczuk and Zhu mentioned in the preface,
"show that" should be "showing that".
 pxx: "forgottten" should be "forgotten",
"perl" should be "Perl", and "millenial" should be "millennial".
(Chris Jeuell)
 p9: E0.17: "latin" should be capitalized. (Chris Jeuell)
 p74: A2.2.18: "helful" should be "helpful". (Chris Jeuell)
 p88: before E2.3.14: "quckly" should be "quickly". (Chris Jeuell)
 p111: E3.2.13: "differentation" should be "differentiation".
(Chris Jeuell)
 p149: X3.4.15a: "occuring" should be "occurring". (Chris Jeuell)
 p187: X4.2.12: "all leaves leaves a path" should be
"all leaves produces a path". (Chris Jeuell)
 p196: L4.3.12 (last paragraph): "larger then $p$" should be
"larger than $p$". (Chris Jeuell)
 p201: before D4.3.25: actually "consecutivity" is not an English word.
(Chris Jeuell)
 p242: D5.4.9: "the shortest path" should be "a shortest path".
(Allan Bickle)
 p312 X7.2.8: "proved" should be "prove".
(Allan Bickle)
 p459 X10.2.14,20: Elsewhere in the book, a roman "e" is used for the base
of the natural logarithm.
 p490 X11.1.25: This exercise should have been placed immediately after
X11.1.27.
 p495 T11.2.11: Although the first "$\ge$" in the display at the bottom of
the page is not wrong, the argument given earlier is that in fact equality
holds. (LD)
 p536 X11.3.3: "$G$ graphs" should be "graphs $G$". (LD)
 p537 X11.3.28: "tranversal" should be "transversal". (LD)
 p558 T12.2.15: The "$\FL{n/2}$" in the problem statement changes to
"$\CL{n/2}$" at the end of the proof, but it doesn't matter because the
binomial coefficients are equal. (Stephen Hartke)
 p566 X12.2.21: "yields chain partition" should be "yields a chain partition"
(LD)
 p568 X12.2.33: The close parenthesis is missing at the end of the hint.
(LD)
 p583 X12.3.15: "noncut vertices" should be "noncutvertices".
(Stephen Hartke)
 p608 X12.4.47: "postively" should be "positively". (LD)
 p608 X12.4.48: "$Q$" should be declared to be a poset. (LD)
 p666 X14.1.2: "Each $A$ sends an invitation to a $B$" should be
"Each member of $A$ sends an invitation to a member of $B$". (LD)
 p675 T14.2.9: "Lóvasz" should be "Lovász".
(Jozsef Balogh)
 p737 T15.1.34: In the statement, "subgraph $H$" should be
"spanning subgraph $H$". (LD) At the start of the proof,
the variables in $x$ should be indexed by the edges, not by integers.
 p746 X15.1.27: "for all $v\in V(G)$" should be "for all $v\in V(H)$"
 p786 T16.1,8: actually "consecutivity" is not an English word (but should
be DBW). (Chris Jeuell)
 p798 X16.1.19: The exercise ends with the label "(Comment:", which
inadvertently did not get removed when the material of the comment
moved to E16.1.32 on page 794. (Michael Pelsmajer)
 p946 MOLS(n,k): "othogonal" should be "orthogonal". (Chris Jeuell)
 p954: The subject index lacks "determinant". (LD)
 p964: The missing page number for "probability generating function" should
be 111. (LD)
 p969: "Venn diagam" should be "Venn diagram". (Chris Jeuell)
 p969: The index should have a pointer to the definition of "whp". (LD)
Additional exercises will be listed here as collected.
Suggestions welcome.
Chapter 1  Combinatorial Arguments
 For $n,a,b\in\NN$ with $n\ge2$, give a combinatorial argument to prove
$\CH{n+a}n+\CH{n+b}n\le \CH{n+a+b}n$. Why does the argument fail when
$n=1$?

In a bucket with marbles of at least three colors, there are $r$ red marbles
and $b$ blue marbles, with $b+1\lt r\le k$. Give a combinatorial argument to
explain why the number of distinguishable ways to have $k$ marbles from the
bucket increases when a red marble is replaced with a blue marble.
Chapter 2  Recurrence Relations
 Prove $\SE l0n (1)^l\CH nl\CH {2l}m=(1)^n2^{2nm}\CH n{mn}$ by showing
that both sides satisfy the recurrence $f(n,m)=2f(n1,m1)f(n1,m2)$ for
$m\ge2$.
 Fix $n\in\NN$, and let $X_0 =n$. Repeatedly choose $X_k$ uniformly at
among the $X_{k1}$ values in $\{0,\ldots,X_{k1}1\}$, stopping when $X_m=0$.
Compute the expected value of $m$ and the expected value of $X_{m1}$.
(BhanuDeshpandeDixit [2019])
Chapter 3  Generating Functions
 An odd polynomial
(a) Give a direct combinatorial proof of the identity below (devise a set
counted by both sides).
$\SE j1m2^j\CH{m1}{j1}\CH xj=\SE j0m\CH{x+mj1}{mj}\CH xj.$
(b) Prove $F_m(x)=(1)^mF_m(x)$, where $F_m$ is defined by
$F_m(x)=\SE k1m(x)^k\SE jkm\FR{(2)^j\CH mj c(j,k)}{(j1)!},$
and $c(j,k)$ is the number of permutations of $[j]$ with $k$ cycles.
(c) Conclude
$\sum_{j=k}^m \frac{(2)^j {m\choose j} c(j,k)}{(j1)!} = 0$
whenever $m$ and $k$ have opposite parity. (Isaacson [2020])
Chapter 5  Graphs
 Determine all $n$vertex trees whose subtrees with $n2$ vertices are
pairwise isomorphic.
Chapter 6  Matchings
 Let $G$ be an $X,Y$bigraph having a matching that covers $X$. Prove that
if $d(y)\ge k$ for all $y\in Y$, then $G$ has at least $k!$ matchings covering
$X$. For each $k$, construct an infinite family of examples where there are
only $k!$ such matchings. (Kostochka)
Chapter 7  Connectivity and Cycles
 For vertices $x,y,z$ in a graph $G$, is it true that $\lambda'(x,y)\ge k$
and $\lambda'(y,z)\ge k$ together imply $\lambda'(x,z)\ge k$?
Is it true that $\lambda(x,y)\ge k$ and $\lambda(y,z)\ge k$
imply $\lambda(x,z)\ge k$?
 Prove that every $n$vertex graph satisfying Ore's Condition has at least
$n^2/4$ edges. (Comment: Bondy [1971a] proved that every $n$vertex
Hamiltonian graph with at least $n^2/4$ edges is pancyclic, except for
$K_{n/2,n/2}$ when $n$ is even (Exercise 7.3.25). With this addendum and
Ore's Theorem, Exercise 7.3.25 also implies that every $n$vertex graph
satisfying Ore's Condition is pancyclic, except for $K_{n/2,n/2}$.
Chapter 8  Colorings
 The pancake graph $PG_n$ is the graph whose vertices are the
permutations of $[n]$, with two permutations adjacent if one is obtained from
the other by reversing a prefix. For example, $21435$ and $41235$ are
adjacent; the graph is $(n1)$regular. Prove that the chromatic number of
the pancake graph is subadditive; that is,
$\chi(PG_{a+b})\le \chi(PG_a)+\chi(PG_b)$.
Conclude that $\chi(PG_n)\le \CL{(2/3)n}$ for $n\in\NN$. (LD)
(Comment: A.H. Ghodraty found explicit proper $4$colorings for $PG_8$ and
$PG_9$, by computer. This makes it possible to prove
$\chi(PG_n)\le 4\FL{n/9}+4$.
Computing the diameter of the pancake graph is a famous open
problem.)
 A 2tree is a chordal graph obtained from $K_2$ by iteratively
adding a simplicial vertex with two neighbors. For $n\ge3$, prove that the
maximum number of edges in an $n$vertex graph containing no $K_4$subdivision
is $2n3$, and show that every such graph is a $2$tree. (Dirac [1960,
1964]) (Comment: This result is also a corollary of the fact that
a maximal $k$degenerate graph is a $k$tree if and only it it contains
no subdivision of $K_{k+2}$, proved in
A. Bickle, Structural results on maximal kdegenerate graphs,
Discuss. Math. Graph Theory 32 (2012), 659676.
The extremal graphs avoiding a $K_5$subdivision have $3n6$ edges
(Mader 1998) and were characterized as the ``3sums'' of planar
graphs in W. Mader, Graphs with $3n6$ edges not containing a subdivision of
$K_{5}$, Combinatorica 25 (2005), 425438.)
Chapter 10  Ramsey Theory
 Let $H_{r,s}$ be the graph $K_{1,r}+K_{1,s}$.
Prove $R(H_{r,s},H_{r,s})=\max\{2r+1,r+2s,r+s+3\}$ (Rosta)
(Comment: The lower bound is in X10.2.36; just prove the upper bound here.
(Hint: Consider the degreesum of a graph not containing $H_{r,s}$.)
Chapter 12  Posets
 Given an $X,Y$bigraph $G$, prove that the Strong Hall Condition for $Y$
(Exercise 12.2.24) is implied by the normalized matching condition for
the $2$level poset whose cover graph is $G$ and implies Hall's Condition for a
matching in $G$ covering $X$.
Comment: By this exercise, the condition in X12.2.24 applies more
generally than the condition in T12.2.26, so X12.2.24 provides a stronger
result than T12.2.26.
 Let $A$ and $B$ be families of subsets of $[n]$ such that
$x\cap y\le k$ for all $x\in A$ and $y\in B$.
Prove $A\cdot B\le 2^n \sum_{0\le i\le k}\CH ni$.
(Hint: Use Kleitman's Inequality.) (P. Frankl)
Chapter 13  Designs
 Let $\VEC A1m$ be $k$sets such that $\C{A_i\cap A_j}\le \lambda$ for all
distinct $i$ and $j$ in $[m]$.
Prove $\C{\bigcup A_i}\ge\FR{k^2m}{\lambda m+k\lambda}$.
Express this as a bound on the size of a family of $k$subsets of $[n]$
that pairwise share at most $\lambda$ elements. (Johnson [1962])
Chapter 14  The Probabilistic Method
 For $0\lt p\lt 1$ and $s\le pn$, prove
$\sum_{k=0}^s \left({n\atop k}\right)p^k(1p)^{nk}
\le \left({n\atop s}\right)p^s(1p)^{ns}{p(ns+1)\over p(n+1)s}$.
Conclude $\sum_{k=0}^{\alpha n}\left({n\atop k}\right)
\lt {1\alpha\over 12\alpha}\left({n\atop \alpha p}\right)$
when $\alpha \le p$.
 Let $L$ be a list assignment for a graph $G$. Let each vertex $v$ have
a nonnegative weight function $w_v$ on its list $L(v)$ of available colors,
such that $\sum_{c\in L(v)} w_v(c)=1$. Prove that if every edge $uv\in E(G)$
satisfies $\sum_{c\in L(u)\cap L(v)} w_u(c)w_v(c)\le (2{\rm e}\Delta(G))^{1}$,
then $G$ is $L$colorable. (See Section 8.2 for definitions.)
(MolloyReed [2002, p42]
 Prove that the Chernoff Bound holds when $t=q=1p$. That is, prove
$\PP(Xnp\ge nt)\le{\rm e}^{2nt^2}$ when $t=1p$ and $X$ has the distribution
${\rm Bin}(n,p)$.
Chapter 15  Linear Algebra

(Supplement to X15.3.10)
Prove that the adjacency matrix of a forest $G$ is invertible if and only
if $G$ has a perfect matching.

$(+)$ Let $A$ be the adjacency matrix of a graph $G$.
(a) Prove that a permutation of $V(G)$ is an automorphism of $G$ if and only if
the corresponding permutation matrix commutes with $A$; that is, $PA=AP$.
(b) Prove that if $x$ is an eigenvector of $G$ for an eigenvalue of ultiplicity
$1$ and $P$ is the permutation matrix for an automorphism of $G$, then
$Px=\pm x$.
(c) Prove that if every eigenvalue of $G$ has multiplicity 1, then every
automorphism is an involution. (Mowshowitz [1969], PetersdorfSachs [1969])

(Supplement to X15.3.17) Prove that the smallest eigenvalue of a $k$regular
graph with $n$ vertices is at least $kn$.