| GeoGebra files | Mathematica Demonstration | Mathematical Links | Less Mathematical Links | Second-Edition Errata | First-Edition Errata |
GeoGebra files:
3.5 Graphs: Definitions and Examples
Fig. 3.8 bipartite graph
3.6 Isomorphisms
Fig. 3.11 graphs
Fig. 3.12 graphs
3.8 Try This! More Graph Problems
Fig. 3.21 graphs
Fig. 3.22 graphs
Fig. 3.23 graphs
Fig. 3.24 graphs
Bonus Graph Isomorphism exercises available only here on the web!
11.2 Try This! Planarity Explorations
Fig. 11.1 left graph
Fig, 11.1 right graph
End-of-Theme Problems
ETI-2. graphs
ETIII-12. graph
ETIII-13. graph
Mathematica Demonstration: (for Chapter 9) Cutting Space into Regions with Four Planes
Mathematical links mentioned in the text:
Frontmatter
Chapter 2 (Sets and Logic)
Chapter 3 (Graphs and Functions)
Chapter 4 (Induction)
Chapter 5 (Algorithms with Ciphers)
Chapter 6 (Binomial Coefficients and Pascal's Triangle)
Chapter 8 (Recurrence)
Chapter 9 (Counting and Geometry)
Chapter 10 (Trees)
Chapter 11 (Euler's Formula)
Chapter 12 (Traversals)
Chapter 13 (Coloring)
Chapter 14 (Expectation)
Chapter 15 (Cardinality)
Chapter 16 (Number theory)
Chapter 17 (Computational Complexity)
Backmatter and References
Less- and Non-mathematical links:
page 259, problem 1, part (e) should have the initial values a0 = a1 = 1.
page 319, the sentence starting "In either case, there must be two vertices..." should continue as "...of G between which there exists a path in G but not in H. There may be many such pairs of vertices, so choose v1 and v2 such that the distance between them is shortest possible. Notice that this means no edge on the v1--v2 path in G can be in H, or else there would be closer vertices with no path between them in H. Now consider the edges of this v1--v2 path in G." Then, "...this means that v1 and v2 are in H, which is a tree. Therefore, there is a path in H between v1 and v2, which is a contradiction." should instead read "...this means that v1 and v2 are in H, which is a forest. If H is a tree, we have a contradiction as any two vertices in a tree are joined by a path. If H has more than one component, then according to our algorithm the addition of any edge along the v1--v2 path creates a cycle, so all of the vertices on the path must be in the same component, and thus there is a path between v1 and v2."
page 321, the first paragraph should be replaced with "We can label the edges of P by the order in which we added them. (Think of this as having the weights written in black and the order-added labels written in teal.) And we know that G has a minimum-weight spanning tree---after all, there are only a finite number of spanning trees, so we can select those with minimum total weight.
So let's look at all the minimum-weight spanning trees and choose one that has the maximum number of edges from the beginning of P (as many of the lowest numbered teal-labeled edges in a row as possible). We will call this tree T."
page 322, the paragraph beginning with "But wait a sec!" should continue "The tree (T ∪ e)\ehwyaden has one more edge from the beginning of P than T does, which is also a contradiction---we chose T to have the maximum number of edges in common with the start of P !"
page 331, Figure 10.18, the right-hand graph has an extra edge. (Removing any of the edges in the 4-cycle will be fine.)
page 344, Figure 10.32, two edges are missing labels. Both should be labeled `1'.
page 353, the last line of the proof of Theorem 11.5.1 should read "...this becomes the desired result, vG - eG + fG = 2."
page 562, Section 2.3 Check-Yourself problem 7 solution, the final column of the header for the truth table should end in P.
First-Edition Errata (not all errors are in all printings, but there is no way to tell which printing your copy is...):
page 29, the sentence after Example 2.2.8 should read "...in
these cases, we interpret B \ A to mean B
\ (elements of A in B) = B \ (A (intersect)
B)."
page 74, Section 3.6 Check-Yourself problem 2 should have "(See
below for definition of subgraph.)" appended.
page 88, the caption for Figure 3.27 should read "Two possibly
isomorphic infinite graphs."
page 121, step 4 should read "If k=10, output k, and stop; otherwise, go to step 2."
page 134, Example 5.4.4, the numerically encrypted message should end in "18 17 14 20" instead of "8 17 14 20," and the ciphertext should be "fumo lm foocesrou" instead of "fumo lm fooceirnu."
page 135, Example 5.4.5, the message should end in "bus lal vvl" instead of "bus lal vll."
page 136, second box, the last three numbers in the last line should be 8 18 1.
page 199, Example 7.4.7, second paragraph, the explanation of the binomial coefficient should read "...ways to place two bars (that demarcate three variables) among two stars (the ones)..."
page 200, Example 7.4.8, PARALLELOGRAM should have 13!/(3!2!3!) anagrams.
page 217, problem 15, the course Physics-with-Calculus II should
just be Physics II.
page 234, Check Yourself! exercise 6 should be about the recurrence a0 = 0, an = an-1 + (n+1)(-1)n+1.
page 235, the second line after Definition 8.8.2 should read
"...but an=an-11+n2-5
gives 0+n2-5 not equal to 0 and..."
page 237, step 10 should read an = (1/6)3n + (1/2)(-1)n .
page 284, Figure 10.3, the rightmost edge should have weight 22.
page 289, at the end of the proof that Prim's algorithm works,
there are two references to ek.
Both should simply be references to e.
page 298, Try This! problem 2 should read "Create a binary
decision tree for a robot to use so it can determine which of the
current U.S. coins (penny, nickel, dime, quarter, half-dollar, and
dollar) you have just offered it. The robot can use its sensors
but cannot directly recognize the coins."
page 299, Figure 10.15, the right-hand graph has an extra edge. (Removing any of the edges in the 4-cycle will be fine.)
page 353, proof of Theorem 12.4.2, the Hamilton path should be P = vb-...-vn-v1-v2-...-va and the parenthetical remark in the following paragraph should read: (Va lists the subscripts for the vertices adjacent to va, and Vb lists the subscripts for the vertices following those adjacent to vb.) Notice that neither Vanor Vbcontains va because va is not adjacent to itself and no vertex follows va in the path (and even using the labeling order, vb is not adjacent to itself).
page 389, problem 18 should read "Suppose G has a Hamilton circuit H. How many colors are required to vertex-color H?"
page 399, second line from the bottom, W(d)=0 should be WH(d)=0.
page 408, Example 14.5.3 should say "We can view this as the probability that a friend receives a postcard and owns a cat plus the probability that a friend receives a postcard and owns no cats."
page 409, at the start of Section 14.5.1, all instances of 35 should be 28, and all instances of .35 should be .28.
page 412, end of Example 14.5.7, an inequality should read P(E1 and E2)=P(E1)+P(E2)-P(E1 or E2) ≤ 3/5+1/3 - 3/5=1/3
page 416, Theorem 14.7.3 only holds for graphs with at least 4 vertices.
page 487, answer to Section 1.4 Check-Yourself problem 2: The
tail end of the solution should read "... = 4k2+4k+1+10k+5-3
= 2(2k2+2k+5k+3) -3 = 2(2k2+2k+5k+1)
+1 = (odd)."
page 491, answer to Section 3.2 Check-Yourself problem 2(c) and 2(d): The tail end of the solution should read "...f(a) = f(b)."
page 493, answer to Section 3.6 Check-Yourself problem 2: the list should include P4.
page 500, answer to Section 6.7 Check-Yourself problem 2: 43 should be (-4)3 so that the answer is -1,280.
page 514, answer to Section 14.3 Check-Yourself problem 1: When using the Lemma, we have only one state (seeing all four ducks) so E[W] = 4x1=4 white ducks and E[WH] = 1x1 = 1 white duck.
page 515, answer to Section 14.3 Check-Yourself problem 2(b): The black duck appears in 8 of the subsets, so E[B] = 1/2.
