Combinatorial Mathematics - Errata, etc.

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)".

Mathematical and Notational Errors

• p26 T1.2.3(6): In the proof of (6), "by how many elements come from the first $k$" should be "by how many elements come from the first $m$". (Andrew Mehler)
• p62 X2.1.33: "$n\ge3$" should be "$n\ge2$". (David Grenier)
• p74 A2.2.18: In the definition of $Q(x)$, the expression "$Q(x)=1-\sum_{i=1}^k c_ix^k$" should be "$Q(x)=1-\sum_{i=1}^k c_ix^i$" (David Grenier)
• 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/(i-1)}}$".
• p172 X4.1.14: "$r_i$" should be "$s_i$". (Allan Bickle)
• p248 X5.4.18: "$n(k-2)$" should be "$n(k-1)$". (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 pre-C6.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.
• p388 X9.1.48: The condition $n\ge3$ should be added to avoid a trivial counterexample. To avoid confusion, one may also want to forbid 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 $(k-i,2k-i,\ldots,k^2-i)$. This specifies the runs but not their order. The runs were intended to be put in order from $i=0$ to $i=k-1$, as is done in the given example. (LD)
• p459 X10.2.20: The given lower bound ignores a lower-order 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 r-2$. The claimed Ramsey number is obtained in J.W. Grossman, The Ramsey numbers of the union of two stars, Utilitas Math. 16 (1979), 271-279 (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 AAAI-18, (2018), 6598-6606. (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 $m-1$. The correct answer for $m\ge3$ is $(5m-3)/2$ when $m$ is odd, $5m/2-3$ 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)
• p490 X11.1.26: The even case of 11.1.27 strengthens the even case of 11.1.26; the proof is the same. 11.1.27 should have come before 11.1.25 and 11.1.26. In the odd case of 11.1.26, the bound is valid only for $n\ge11$, as noted by Parsa Zarezadeh. 11.1.26 should be a (+) exercise.
• 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\ge|V(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(1-2\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$". (O-joung 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 > t-1$, but that is where we need it. When the number of edges is maximized, every vertex in $x$ has degree at least $t-1$. (Michael Pelsmajer)
• p632 E13.2.22: "prime power and $n=$" should be "prime power such that $(q-1)/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$". (O-joung Kwon)
• p638 X13.2.7-8: 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 lower-degree polynomials. The element $x$ is a "primitive" element; its powers from $0$ through $q-2$ are the nonzero elements of the field, with $x^{q-1}=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=x-y$." 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 $k-1$".
• p665 T14.1.20: In the second line of the proof, the subscript $k$ on $B^j_k$ should be $n$. On the next page, a comma is missing after $B^1$.
• 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 edge-disjoint triangles". (LD) More subtly, "if and only if it has no" should be "if and only if the given list of edge-disjoint 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}^{-(d-1)^2}/4$" should be "${\rm e}^{-(d-1)^2/4}$"
• p703 X14.3.19: In the comment, "$n-2\log n$" should be "$n-2c\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 n-2\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 n-2\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 Molloy-Reed [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 Frankl-Wilson [1981].
• p745 X15.1.18: This exercise is badly mis-stated. 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.
• p764 X15.2.18: The answer formula "$n2^{m-n}$" should be "$m2^{m-n}$"
• p764 X15.2.22: The statement is not incorrect, but it should be improved by requesting a doubly-exponential lower bound.
• p765 X15.2.33: "$g(x)=\sum_{y\le x}f(x)$" should be "$g(x)=\sum_{y\le x}f(y)$".
• 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)
• p781 X15.3.15: The maximum should be restricted to vectors with all coordinates nonzero.
• p790 T16.1.20: It is not true that assigning each vertex the triple of its heights in a 3-dimensional 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 straight-line 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(n-1)^{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 pp133-134 of E.M. Palmer, Graphical Evolution (Wiley-Interscience, 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)
• p847 X15.2.18: The hint is irrelevant; a bijective argument is better.

Bibliographic items

Due to an error in the cross-referencing 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), 235-239. (David Callan)
• p174 X4.1.39: The inclusion-exclusion argument for this formula may appear in Brualdi's book as early as the 1992 edition.
• p226 X5.2.13: The mountain-climber problem appeared in A. Tucker (1995), The Parallel Climbers Puzzle, Math Horizons, 3:2, 22-24, and earlier in J.~V.~Whittaker (1966), A mountain-climbing problem, {\it Canadian J. Math.}, 18: 873-882, plus a version in Homma, Tatsuo (1952), "A theorem on continuous functions", Kodai Mathematical Seminar Reports, 4: 13-16.
• 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{2n-4}$. The CM text mis-states the result of Chen-Lehel-Jacobson-Shreve [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 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]. Lin-Zhai-Zhao [2022] proved a spectral analogue (see Chapter 15): if $G$ has at least 26 vertices and it largest eigenvalue is at least the largest eigenvalue of the graph $J$, then $G$ contains two cycles of the same length unless $G=J$, where $J$ is obtained from $K_{1,n-1}$ by adding one edge. (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), 13-20. The final conclusion for list-chromatic numbers appears in the Erdős-Rubin-Taylor [1979] paper. (Allan Bickle)
• p355 X8.2.32: The most accurate citation is probably "V.G. Vizing, personal communication in 1976 to O.V. Borodin". It seems that the example does not appear in Vizing's paper.
• 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, 61-63).
• p612 E13.1.8: The citation given for Stinson's proof is pages 130-133 of Anderson's 1997 book. That book says it "incorporates and expands on" Anderson's 1990 book "Combinatorial Designs: Construction Methods". In fact, the pages 130-133 where Stinson's proof is presented are in the 1990 book. In the 1997 version Stinson's proof is cited but apparently not presented. (Jacobus Swarts)
• p632-3 E13.2.22 and T13.2.23: The citations for Füredi 1996b and 1996c are reversed (also p639 X13.2.14).
• p654 X13.3.4: This result is due to Rosa [1967]. (Allan Bickle)
• p656 X13.3.23: Both parts are due to Rosa [1967]. (Allan Bickle)
• p734, 735, 745, 746, 851: The name "Rusza" should be spelled "Ruzsa"
• p900 Mabry: The page numbers are 119-122, not 119-112. (Allan Bickle)
• p925: "W.H. Wiedemann" should be "D.H. Wiedemann"

Comments and Updates

• p26 T1.2.3(5): When explaining the Summation Identity using lattice paths, the term $\CH kr$ counts the paths to $(r+1,n-4)$ in which the height of the last horizontal step is $k-r$. (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) 177-185; F. J. Faase, On the number of specific spanning subgraphs of the graphs $G\times P_{n}$, Ars Combinatoria, 49 (1998) 129-154; 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 $(1-2p)^2$ makes sense. With this, the computations in parts (a) and (b) both work out nicely for the relevant values of $p$. (Kevin Milans)
• p129-131: Another proof of the Lagrange Inversion Formula appears in Erlang Surya and Lutz Warnke, Lagrange Inversion Formula by Induction, Amer. Math. Monthly 130 (2023), 944-948.
• p150 X3.4.26: This problem is worthy of ($\D$).
• p207-208 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.
• p228 X5.2.40: Further results about transforming betweeen tournaments having the same outdegree list by reversing edges in various types of subgraphs appear in C. Waldrop Jr., An ARC-reversal theorem for tournaments, Proc. 7th SE Conf. Comb. Graph Th. Computing (Louisiana State Univ., Baton Rouge, La., 1976), Congressus Numerantium 17 (1976), 501-507. See also L.W. Beineke and J.W. Moon, On bipartite tournaments and scores, Theory and applications of graphs (ed G.Chartrand et al), Wiley, (1981), 55-71.
• p270-1 D6.2.17-T6.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 non-inductive 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 4-connected 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), 325-332. (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 set-systems, Acta Math. Acad. Sci. Hungar. 17 (1966), 61-99, 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 edge-coloring appears in B. Toft and R. Wilson, Discrete Mathematics Letters 6 (2021), 38-46.
• p353 X8.2.7 and p375 X8.3.42: Dirac [1960] showed that $n$-vertex graphs with more than $2n-3$ edges contain a $K_4$-subdivision. In Dirac [1964], he showed that the $n$-vertex graphs with $2n-3$ 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, (North-Holland, 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 Lederberg-Bosák-Barnette graph is the smallest example was proved by D.A. Holton and B.D. McKay in The smallest non-hamiltonian 3-connected cubic planar graphs have 38 vertices, J. Combinatorial Theory (B) 45 (1988), 305-319.
• p419 X9.3.24: This exercise generalizes Exercise 8.1.29. The partitioning of the vertices of a planar graph into sets inducing a 1-degenerate and a 3-degenerate 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 1-degenerate and a 2-degenerate graph (his definition of k-degenerate was shifted by 1 from ours). (Allan Bickle)
• p438 J10.1.33-34: The Erdős-Faber-Lová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ős-Faber-Lová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 three-color 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), 375-393. 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.)"
• p490-491 X11.1.25-27: The results of 11.1.25 are due to Clapham [1973], 11.1.27 to Goodman [1959] and Sauvé [1961], and 11.1.26 to G. Lorden, Blue-empty chromatic graphs, Amer. Math. Monthly 69(1962), 114-120.
• 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önig-Egerváry Theorem. This exercise is in fact a stronger result than the Anderson-Griggs 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.
• p647 E13.3.18: The "Walecki decomposition" refers to the decomposition of $K_n$ into spanning cycles (for odd $n$) obtained in Exercise 5.3.48. There should be a reference to the exercise here, especially since the existence of such a decomposition is used in Theorem 13.3.20. The term "Walecki decomposition" should appear in the index. (Allan Bickle)
• p649 E13.3.21: The Kirkman Schoolgirls Problem is in fact the special case OP(3,3,3,3,3) of the Oberwolfach Problem. (Allan Bickle)
• 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 AM-GM 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, 2-list-coloring planar graphs without monochromatic triangles, J. Combin. Theory Ser. B 98 (2008), no. 6, 1337-1348. (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), 41-48. 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)
• p795 E16.1.33: In fact, Pelsmajer et al. showed that odd-cr and pair-cr are not the same parameter (Allan Bickle)

Minor Typos

• pxvi: In line-7, "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)
• p215: R5.1.24: "discussino" should be "discussion". (Zach Langley)
• 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: "non-cut vertices" should be "non-cut-vertices". (Stephen Hartke)
• p608 X12.4.47: "postively" should be "positively". (LD)
• p608 X12.4.48: "$Q$" should be declared to be a poset. (LD)
• p634 P13.2.29: "there one such set" should be "there is one such set" (Allan Bickle)
• 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)
• p918: "problem 1192" should be "problem 11192"
• 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)

Supplementary Exercises

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.
• By devising a set counted by both sides of the identity, give a direct combinatorial proof that $\SE j1m2^j\CH{m-1}{j-1}\CH xj=\SE j0m\CH{x+m-j-1}{m-j}\CH xj$.
• Consider rectangles with integer corners in $[0,n]\times[0,n]$. For $1\le k\le n$, prove that the number of such rectangles whose shortest sides have length $k$ is $(n-k+1)^3$. From this conclude $\sum_{k=1}^n k^3 =[n(n+1)/2]^2$. (Comment: An algebraic proof of the identity is discussed in Application 1.2.7 and completed in Exercise 1.2.8.) (F. Morley, Amer. Math. Monthly Problem 3792 43 (1936), 435; solution 45 (1938), 391.)
• Given positive integers $i,j,n$ with $1\le i\lt j\lt n$, prove that $\CH ni$ and $\CH nj$ are not relatively prime. (Hint: Consider the Subcommittee Identity.) P. Erdős and G. Szekeres, Some number theoretic problems on binomial coefficients, Aust. Math. Soc. Gazette 5 (1978) 97-99.
• (P. Lalonde [2023]) Let $m$ and $n$ be positive integers with $m\lt n$.
  (a) Prove that $\SE k0m(-1)^{m-k}\CH{m+1}{k+1}\FR{\CH{x}{m+1}}{x-k}$ and $\SE k0m\CH{x}{k}\FR{(-1)^k}{k+1}$ are equal as polynomials in $x$.
  (b) Prove $ \FR{(-1)^m}{\CH{x}{m+1}\,(m+1)} =\SE k0m\FR{(-1)^k\CH mk}{x-k}. $
  (c) Conclude $ \left( \sum_{k=0}^m {m \choose k} \frac{(-1)^k}{n-k} \right)\, \left( \sum_{k=0}^m {n \choose k} \frac{(-1)^k}{k+1} \right) =\sum_{k=0}^m {m \choose k} \frac{(-1)^k}{(n-k)(k+1)}. $

Chapter 2 - Recurrence Relations

• Prove $\SE l0n (-1)^l\CH nl\CH {2l}m=(-1)^n2^{2n-m}\CH n{m-n}$ by showing that both sides satisfy the recurrence $f(n,m)=-2f(n-1,m-1)-f(n-1,m-2)$ for $m\ge2$.
• Prove that a positive integer $n$ is a Fibonnaci number if and only if $5n^2+4$ or $5n^2-4$ is a square. (Gessel [1972]) (Hint: For necessity, use $F_{k-1}F_{k+1}=F_k^2+(-1)^k$. For sufficiently, prove that if $5n^2\pm4$ is the square of some positive integer $m$, then $n=F_k$ and $m=F_{k-1}+F_{k+1}$ for some integer $k$. Consider $n_1=(m-n)/2$ and $m_1=(5n-m)/2$.)
• Prove that $\CH nk=\CH{n-1}{k+1}$ when $n=F_{2i+2}F_{2i+3}$ and $k=F_{2i}F_{2i+3}$ for some positive integer $i$. (Here $F_0=0$ and $F_1=1$.) (Lind [1968], Singmaster [1975], Tovey [1985])
• Fix $n\in\NN$, and let $X_0 =n$. Repeatedly choose $X_k$ uniformly at among the $X_{k-1}$ values in $\{0,\ldots,X_{k-1}-1\}$, stopping when $X_m=0$. Compute the expected value of $m$ and the expected value of $X_{m-1}$. (Bhanu-Deshpande-Dixit [2019])

Chapter 3 - Generating Functions

• Prove $ \sum_{n=2}^\infty \frac1{n+1} \sum_{i=1}^{\lfloor{n/2}\rfloor} \frac1{2^{i-1} (i-1)! (n-2i)!} = 1. $ (Hint: One proof recognizes the inner sum on the left as a coefficient in the product of two generating functions and uses this to reduce the left side to an integral.) Santmyer [2021]

Chapter 4 - Further (Enumerative) Topics

• (-) Involutions are permutations whose square is the identity. Prove that when $n\ge2$, the number of involutions on $[n]$ (including the identity) is even.

Chapter 5 - Graphs

• (-) Let $x,y,z$ be vertices in a tree $T$. Prove that $d(x,y)+d(y,z)+d(z,x)$ is even.
• (-) Let $G$ be an $X,Y$-bigraph. Suppose that for every subset $S$ of $X$, the number of vertices in $Y$ adjacent to all of $S$ is given. Prove that this information determines the isomorphism class of $G$.
• Determine all $n$-vertex trees whose subtrees with $n-2$ vertices are pairwise isomorphic.

Chapter 6 - Matchings

• For a vertex subset $T$ in a graph $G$, a $T$-join is a spanning subgraph of $G$ in which the degree of every vertex in $T$ is odd and the degree of every vertex outside $T$ is even. Prove that if $T$ is contained in the vertex set of one component of $G$, then $G$ has a $T$-join if and only if $|T|$ is even.
• Let $G$ be an $X,Y$-bigraph (without multi-edges) 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)
• Let $G$ be an $X,Y$-bigraph with $|X|=|Y|$. Prove that $G-\{x,y\}$ has a perfect matching whenever $x\in X$ and $y\in Y$ if and only if $|N(S)|\gt|S|$ for every nonempty proper subset $S$ of $X$. (Lovász-Plummer [1986])
• Given a graph $G$, let $G'$ denote the graph with vertex set $V(G)$ whose edges are the pairs of vertices that have a common neighbor in $G$. Prove $|E(G')|\ge |E(G)|-\FL{n/2}$, and show that this is sharp. (Hint: Consider a maximal matching $M$ and show that $G'$ has at least $|E(G)|-|M|$ edges.) (Füredi [1992])

Chapter 7 - Connectivity and Cycles

• Let $G$ be a connected $n$-vertex graph in which all vertices have the same eccentricity. Prove that $G$ has diameter at most $n/2$.
• 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

• (-) Prove that applying the Mycielski construction to a graph increases the degeneracy by at least $1$. (Comment: S. Hartke has noted that applying the Mycielski construction to the Gr\"otzsch graph increases the degeneracy by 2.
• 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 $(n-1)$-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 2-tree 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 $2n-3$, 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 k-degenerate graphs, Discuss. Math. Graph Theory 32 (2012), 659-676. The extremal graphs avoiding a $K_5$-subdivision have $3n-6$ edges (Mader 1998) and were characterized as the ``3-sums'' of planar graphs in W. Mader, Graphs with $3n-6$ edges not containing a subdivision of $K_{5}$, Combinatorica 25 (2005), 425-438.)
• (!) Let $\hat P$ denote the Petersen graph.
  (a) Prove that $\hat P$ has exactly 12 perfect matchings.
  (b) Prove that any two perfect matchings in $\hat P$ share exactly one edge.
  (c) Prove that $E(\hat P)$ cannot be covered by four perfect matchings.
  (Comment: Berge conjectured that the edges of any $2$-edge-connected $3$-regular graph can be covered using at most five perfect matchings. The Petersen graph shows that this conjecture is sharp. Fulkerson [1971] conjectured that every $2$-edge-connected $3$-regular graph has six (not necessarily distinct) perfect matchings such that every edge appears in exactly two of them. Trivially, Fulkerson's Conjecture implies Berge's Conjecture. Mazzuoccolo [2010] used the result of this exercise to show that Berge's Conjecture implies Fulkerson's Conjecture.)

Chapter 9 - Planar Graphs

• Which sets of two edges in the Petersen graph leave a planar graph when deleted from the Petersen graph?
• A map on the sphere is determined by $n$ great circles, no three meeting at a point. The countries are the maximal regions not crossing any of the great circles. Prove that when $n$ is divisible by $4$, there is no path that passes through each country exactly once. (L. Moser [1947])
• (Addendum to Exercise 9.1.26) Let $G$ be a graph formed by $n$ great circles on the sphere, with vertices for the intersection points and edges along the great circles (no three circles meet at a point). Prove that $G$ is Hamiltonian when $n\ge2$.
• Let $H$ be an $n$-vertex $k$-regular graph that decomposes into $k$ perfect matchings.
  (a) Prove that if $K_n$ decomposes into $t$ copies of $H$ plus a leftover perfect matching, then the multigraph $K_n^{(k)}$ having $k$ copies of each vertex pair as edges decomposes into $kt+1$ copies of $H$.
  (b) Apply part (a) to the octahedron, the cube, and the icosahedron.

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 degree-sum of a graph not containing $H_{r,s}$.)

Chapter 11 - Extremal Problems

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])
• Let $w(n,m)$ denote the maximum sum of the clique numbers of $m$ subgraphs decomposing $K_n$ (see Exercise 5.3.55).
  (a) Prove that $z(m,n;2,2)=w(n,m)$ for all $m$ and $n$ (R.K. Guy [1968]).
  (b) Prove that $z(m,n;2,2)=n+\CH m2$ when $n\ge\CH m2$. (Comment: Čulík [1956] proved more generally that $z(m,n;s,t)=(s-1)n+(t-1)\CH ms$ when $1\le s\le m$ and $n\ge(t-1)\CH ms$.)
• Prove that some $n$-by-$n$ Latin square decomposes into $n$ disjoint transversal (sets of $n$ positions in distinct rows and distinct columns with distinct entries) if and only if the complete $4$-partite graph $K_{n,n,n,n}$ decomposes into copies of $K_4$. (Comment: Euler asked in 1782 for which $n$ such decompositions exist.)

Chapter 14 - The Probabilistic Method

• Give a simple formula for the expected value of the smallest value showing when $n$ fair dice are rolled that each have $k$ sides showing the numbers $1$ through $k$.
• Let $H$ be an $r$-uniform hypergraph with $m$ edges. Prove that $H$ contains an $r$-partite $r$-uniform subhypergraph with at least $(r!/r^r)m$ edges. Show that this bound is asymptotically sharp by considering complete $r$-uniform hypergraphs. (Comment: The special case $r=2$ is the elementary result of Erdős that every graph contains a bipartite subgraph with at least half the edges.) (Erdős-Kleitman [1968])
• For $0\lt p\lt 1$ and $s\le pn$, prove $\sum_{k=0}^s \left({n\atop k}\right)p^k(1-p)^{n-k} \le \left({n\atop s}\right)p^s(1-p)^{n-s}{p(n-s+1)\over p(n+1)-s}$. Conclude $\sum_{k=0}^{\alpha n}\left({n\atop k}\right) \lt {1-\alpha\over 1-2\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.) (Molloy-Reed [2002, p42]
• Prove that the Chernoff Bound holds when $t=q=1-p$. That is, prove $\PP(X-np\ge nt)\le{\rm e}^{-2nt^2}$ when $t=1-p$ 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 multiplicity $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], Petersdorf--Sachs [1969])
• (Supplement to X15.3.17) Prove that the smallest eigenvalue of a $k$-regular graph with $n$ vertices is at least $k-n$.
• The family of strongly regular graphs is contained in several other families of interest with weaker constraints. A graph is distance-regular if for any two vertices $u$ and $v$, the number of vertices at distance $i$ from $u$ and distance $j$ from $v$ depends only on the distance between $u$ and $v$, not on the choice of the vertices. For graphs with diameter $d$, Brouwer, Cohen, and Neumaier~\cite{BCN} showed that an equivalent condition is the existence of parameters $(\VEC b0d;\VEC c0d)$ (called the {\it intersection array} of $G$) such that for all $u,v\in V(G)$ separated by distance $m$, the numbers of neighbors of $u$ having distance $m+1$ or $m-1$ from $v$ are $b_m$ and $c_m$, respectively. A graph is weakly distance-regular with parameters $(k,\ell,m)$ if it is $k$-regular, any two adjacent vertices have exactly $\ell$ common neighbors, and any two vertices separated by distance $2$ have exactly $m$ common neighbors. A graph is $t$-partially distance-regular if for $0\le i\le t$, the $i$th distance matrix $A_i$ is given by a polynomial in the graph's adjacency matrix $A$.
  (a) Show that every strongly regular graph is distance-regular and every distance-regular graph is weakly distance-regular.
  (b) Show that a graph is weakly distance-regular if and only if it is $2$-partially distance-regular.

Chapter 16 - Geometry and Topology

• Determine the exact number of crossings in the drawing of $K_n$ on the tin can in Theorem 16.1.26.