# 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 supplementary problems.

Send contributions of errors, comments, or supplementary problems to dwest@illinois.edu; contributors noted in parentheses. Locating codes: X=Exercise, T=Theorem, L=Lemma, P=Proposition, C=Corollary, E=Example, J=Conjecture. $\def\nul{\emptyset}\def\NN{{\bf N}}\def\ZZ{{\bf Z}}\def\RR{{\bf R}} \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}}$

## Mathematical and notational errors

• p133 X3.3.21: In part (b), the factor "$i^{\FL{m/i}}$" should be "$i^{\FL{m/(i-1)}}$".
• 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).

## Bibliographic items

• 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 [1988], 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 [2020+]. (Chunhui Lai)

• 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)
• p150 X3.4.26: This problem is worthy of ($\D$).
• p207-208 X4.3.13,19,20: These ($\D$) exercises are fairly long.