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)

- Click to shade parts of an Interactive Venn Diagram (requires
*Mathematica*or free CDF Player) and the demonstration shows the set notation for the corresponding set and its complement. - The Venn Game applet has you click on a set-notation description and then shades the corresponding regions of a Venn diagram.
- This "quiz" applet has 15 different symbolic descriptions of sets. You have to figure out which regions on the corresponding Venn Diagrams should be shaded, and mousing over a nearby diagram will show the correct shading.
- The Propositional
Logic Puzzle Generator (requires
*Mathematica*or free CDF Player) shows some polygons along with a list of statements about the polygons in logic notation. (The logic notation is not quite the same as used in*Discrete Mathematics with Ducks*, but there is a `help' option that explains it.) Each statement is marked as true or false. The trick is that the polygons are not labeled but referred to in the statements as A, B, C, etc. and you get to match the labels with the polygons. - The puzzles Logic
with Letters, 2D
Logic Game with Letters, and Logic
with Logicians (all require
*Mathematica*or free CDF Player) do not use formal logic notation but give practice in logical thinking. - Here you are invited to type in a logical statement, and are then given a corresponding blank truth table to fill in---it just has headers and a few beginning columns. You can choose whether to have your work checked entry by entry, or when you're done filling in the table. Warning: this applet uses a single arrow for
*implies*instead of the double arrow we use in*Discrete Mathematics with Ducks*. - For a good survey of what's known about Venn diagrams, go here.
- The logic puzzle generators Knights
and Knaves Puzzle Generator, Knights,
Knaves, and Normals Puzzle Generator, and Another
Knights and Knaves Puzzle Generator (all require
*Mathematica*or free CDF Player) generate collections of statements. You decide which speakers are knights (who tell the truth) and which are knaves (who lie). The software has options to translate each statement into logic notation and to reveal the solution to each puzzle.

Chapter 3 (Graphs and Functions)

- Play the dot game.
- Experiment with different 2-colorings of the edges of various
complete graphs at Graphs
and Their Complements (requires
*Mathematica*or free CDF Player). - As you draw some vertices/edges, this applet produces the graph complement in real time.
- As you draw the graph vertex by vertex and edge by edge, this applet constructs the corresponding adjacency matrix.

Chapter 4 (Induction)

- Applets
that allow you to tile 8 x8 and
*M*x*N*grids with L-shaped tiles.

Chapter 5 (Algorithms with Ciphers)

- Collatz Problem gives a summary of the history, current state of knowledge, and related generalizations of the Collatz Conjecture.
- Computational Verification of the 3x+1 Conjecture
- Automate encryption/decryption for shift ciphers
- Automate encryption/decryption for the standard Vigenere cipher
- Graph
Searching Breadth First and Depth First (requires
*Mathematica*or free CDF Player) gives you a slider to control how many steps of the search have been done. - The
Pigeonhole Principle Repunits (requires
*Mathematica*or free CDF Player) lets you explore which numbers divide numbers like 111, 1111, 11111, etc.

Chapter 6 (Binomial Coefficients and Pascal's Triangle)

- Find Math Curse at your local library.
- This BubbleSort page (click on the Bubblesort button) shows the eponymous algorithm in action.
- Download Donald E. Knuth's The
Computer as Master Mind. (.pdf)
*J. Recreational Mathematics*,**9**(1) (1976-77), 1--6.

Chapter 8 (Recurrence)

- MacTutor History of Mathematics Archive biography of Fibonacci
- OEIS lookup service and overall description
- The Fibonacci Quarterly (back issues freely downloadable) publishes the latest research and exposition on Fibonacci numbers.
- The Journal of Integer Sequences (free) is devoted to research involving integer sequences.
- Play with theTower of Hanoi.

Chapter 9 (Counting and Geometry)

- David Eppstein's Geometry in Action page is an extensive directory of applications of discrete and computational geometry.
- Play SET online here or here.
- Lots of information about the physical card game SET
- Preprint
of The card game Set (.pdf) by Ben Davis and Diane
Maclagan, published in
*The Mathematical Intelligencer,*Vol. 25, No. 3 (Fall 2003), pp. 33--40.

Chapter 10 (Trees)

- This applet shows Kruskal's algorithm executed step-by-step on some customizable graphs.
- This applet shows Prim's algorithm executed step-by-step on some customizable graphs.
- This applet generates a variety of graphs with step-by-step executions of Kruskal's algorithm.
- This applet generates graphs on which Prim's algorithm is worked step-by-step.
- For an example of the branch-and-bound algorithm, go here and choose option 10. This opens two windows: one holds the tree and the other shows blocks that can be used to fill a bag. You can have the software step through the algorithm, or you can explore the tree via the (show entire tree) button.

Chapter 11 (Euler's Formula)

- Planarity. (No more need be said.)
- At least 19 proofs of Euler's Formula.
- Play with Proving
Eulers Polyhedral Formula by Deleting Edges (requires
*Mathematica*or free CDF Player). - Toroidal
Wrapping (requires
*Mathematica*or free CDF Player). - A summary of the classification of topological surfaces.
- Details of the classification of topological surfaces (.pdf).

Chapter 12 (Traversals)

- Practice finding Euler circuits at this site.
- Comprehensive history of and research on TSP.
- Dijkstra's algorithm in action
- Generate a variety ofstep-by-step examples of Dijkstra's algorithm
- Some decent
approximations to TSP solutions (requires
*Mathematica*or free CDF Player). - This website will let you try to make your own solutions for TSP examples, and describes several algorithms for generating solutions.
- Optimizing
Dispersal Corridors for the Cape Proteaceae Using Network Flow
(.pdf) by Steven J. Phillips, Paul Williams, Guy Midgley, and
Aaron Archer, in
*Ecological Applications*, 18(5), 2008, pp. 1200--1211.

Chapter 13 (Coloring)

- Practice coloring the vertices of graphs properly here and here.
- A brief history of the Four Color Theorem and a somewhat technical explanation of the 1995 proof
- Four-color some graphs
(requires
*Mathematica*or free CDF Player) and maps (warning: uses Flash!).

Chapter 14 (Expectation)

- Steve Strogatz's
*>New York Times*column on uses and misuses of conditional probability in medicine and politics. - Simple tools for understanding risks,
*BMJ*(2003).

Chapter 15 (Cardinality)

Chapter 16 (Number theory)

- Clock manufacture and the Stern-Brocot Tree as well as another take on the mathematics.

Chapter 17 (Computational Complexity)

- Sorting algorithms in action.
- Prof. Mary K. Vernon's computer-science perspective on complexity.
- Gary MacGillivray's technical notes on how to prove functions are (or are not) in O(type).

Backmatter and References

- MacTutor History of Mathematics biography of Pascal
*Discrete Mathematics with Algorithms*by Michael O. Albertson and Joan P. Hutchinson, Wiley, 1988.*Combinatorics Through Guided Discovery*(.pdf) by Kenneth P. Bogart, 2004.*Book of Proof*by Richard Hammack, Department of Mathematics & Applied Mathematics

Virginia Commonwealth University Mathematics Textbook Series, 2009.*Discrete Mathematics*(Lecture Notes, Yale University, Spring 1999) by László Lovász and Katalin Vesztergombi}.- MIT OpenCouseWare

**Less- and
Non-mathematical links:**

- Find
*Ducks!*at your local library. - Minimal Criminal is a band.
- WEBS is a real store.
- At Chicago O'Hare International Airport, there are an average of 1,185 direct flights per day (source: Fly Chicago).
- The population of San Francisco is at least 870,000, according to the US Census.
- The mean age at which a child-bearing woman has her first child is 25 (26.3 as of 2014).
- How to know how many ---- you can shake a stick at.
- They really do grow rice on Iki Island. And historically, there really were pirates (use google translate) inhabiting the island!
- Dijkstra's algorithm is fairly efficient, and so is often used in practice for applications such as IP routing\dots but it is not actually fast enough to be used in Google Maps.
- A game was marketed with the board for the Icosian game, but laid out over the head of a mushroom-like object.
- The Egg Yolk Wasn't Here building.
- The Donuts.
- Cake Wrecks blog.
- Big Bird singing the abcdefghi... song.
- A Doctor Who clip (from The Pyramids of Mars) containing a truth-tellers problem.
- The Yarn Harlot's description of her living-room-became-a-mitten-factory episode, in two posts.
- Get The Blue Sea Deck.
- Pretty Good Privacy plugins for software

page 259, problem 1, part (e) should have the initial values a_{0} = a_{1} = 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 *v*_{1} and *v*_{2} such that the distance between them is shortest possible. Notice that this means no edge on the *v*_{1}--*v*_{2} 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 *v*_{1}--*v*_{2} path in *G*."
Then, "...this means that *v*_{1} and *v*_{2} are in *H*, which is a tree. Therefore, there is a path in *H* between *v*_{1} and *v*_{2,} which is a contradiction." should instead read "...this means that *v*_{1} and *v*_{2} 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 *v*_{1}--*v*_{2} 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 *v*_{1} and *v*_{2}."

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*)\*e*_{hwyaden} 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, *v _{G}* -

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 *a*_{0} = 0, *a*_{n} = *a*_{n-1} + (*n*+1)(-1)^{n+1}.

page 235, the second line after Definition 8.8.2 should read
"...but *a*_{n}=*a*_{n}_{-11}+*n*^{2}-5
gives 0+*n*^{2}-5 not equal to 0 and..."

page 237, step 10 should read a_{n} = (1/6)3^{n}
+ (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 *e** _{k}*.
Both should simply be references to

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*
= *v _{b}*-...-

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*(*E _{1}* and

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 "... = 4*k*^{2}+4*k*+1+10*k*+5-3
= 2(2*k*^{2}+2*k*+5*k*+3) -3 = 2(2*k*^{2}+2*k*+5*k*+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 *P*_{4}.

page 500, answer to Section 6.7 Check-Yourself problem 2: 4^{3}
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.