Discrete Mathematics: An Open Introduction

Citation

Levin, O. (2025). Discrete Mathematics: An Open Introduction (4th ed.). Chapman & Hall/CRC. Free official edition: https://discrete.openmathbooks.org/dmoi4.html

Chapter Summary

Chapter 0: Introduction and Preliminaries

The short opening chapter explains what makes mathematics "discrete" through small puzzles about handshakes, sequences and counting, and then gives a first, informal tour of the discrete structures used throughout the book: sets, functions, sequences, relations and graphs. These structures are introduced "as needed" here and treated more formally in Chapter 5.

Chapter 1: Logic and Proofs

This chapter serves as the book's bridge to proof. It covers atomic and molecular statements, quantifiers and predicates, implications with their converses and contrapositives, truth tables, logical equivalence (including for quantified statements) and deductions. It then teaches direct proof, proof by contrapositive and proof by contradiction, and a new section applies these methods to sets, functions, relations and graphs. The chapter summary uses the Goldbach conjecture to show how a statement's logical form suggests the shape of a proof.

Chapter 2: Graph Theory

Starting from problems such as the bridges of Königsberg, the chapter defines graphs and studies trees (properties, spanning trees and rooted trees), planar graphs with Euler's formula and its connection to polyhedra, Euler trails and circuits along with Hamilton paths, and vertex and edge colouring. A section on relations shows how relations, equivalence relations and partitions can be viewed as graphs, and the chapter ends with matchings in bipartite graphs and Hall's Marriage Theorem.

Chapter 3: Counting

Reorganised in this edition to focus on sets of outcomes rather than rules, the chapter begins with Pascal's triangle viewed through lattice paths, bit strings and subsets, then develops the sum and product principles, inclusion–exclusion for overlapping outcomes, combinations and permutations with the quotient principle, multisets ("stars and bars" via bit strings) and combinatorial proofs. A new section applies counting to probability, including conditional probability, and a final section uses inclusion–exclusion for multisets, derangements and counting functions.

Chapter 4: Sequences

Sequences are described by closed and recursive formulas, partial sums and differences, with short Python examples. The chapter studies arithmetic and geometric sequences, polynomial sequences found through finite differences, and summation techniques ("reverse and add", "multiply, shift and subtract"), and solves linear recurrences with the characteristic root technique. It closes with proof by induction and strong induction, linking recursive descriptions of sequences with inductive reasoning.

Chapter 5: Discrete Structures Revisited

This self-contained chapter gives a fuller treatment of sets (notation, subset relations, operations and Venn diagrams) and functions (ways of describing them, injections, surjections and bijections, and images and inverse images). The preface notes that it can be studied independently of the rest of the book.

Chapter 6: Additional Topics

Two further topics complete the book. Generating functions are built and manipulated by differencing, multiplication and partial sums, and used to solve recurrence relations. An introduction to number theory covers divisibility, remainder classes, properties of congruence, solving congruences and solving linear Diophantine equations.

Key Concepts

Chapter 0: Introduction and Preliminaries

• Discrete structure: a mathematical object made of separate, distinct elements—such as a set, sequence, relation or graph—used to model real-world problems.
• Function as a discrete structure: a rule assigning each element of a domain exactly one element of a codomain, often between finite sets.

Chapter 1: Logic and Proofs

• Implication: a statement "if P, then Q", which is false only when P is true and Q is false; its contrapositive is logically equivalent to it, while its converse is not.
• Quantifiers: "for all" and "there exists", whose order and negation determine a statement's meaning.
• Proof styles: direct proof, proof by contrapositive and proof by contradiction, chosen according to the logical form of the statement.

Chapter 2: Graph Theory

• Tree: a connected graph with no cycles; a tree with n vertices has n − 1 edges.
• Euler's formula: for a connected planar graph, vertices minus edges plus faces equals 2.
• Euler trail: a walk that uses every edge exactly once, which exists exactly when the graph is connected and has zero or two vertices of odd degree.
• Chromatic number: the smallest number of colours needed so that adjacent vertices receive different colours.

Chapter 3: Counting

• Sum and product principles: counting disjoint alternatives by adding and independent stages by multiplying.
• Inclusion–exclusion: correcting for overlaps by alternately adding and subtracting the sizes of intersections.
• Combinatorial proof: establishing an identity by showing that both sides count the same set.
• Derangement: a permutation with no fixed points, counted using inclusion–exclusion.

Chapter 4: Sequences

• Recursive and closed formulas: describing a term from earlier terms, or directly from its index.
• Characteristic root technique: solving linear recurrences such as the Fibonacci recurrence using the roots of an associated polynomial.
• Mathematical induction: proving a statement for all n by a base case and an inductive step, with strong induction using all earlier cases.

Chapter 5: Discrete Structures Revisited

• Set operations: union, intersection, difference, complement and Cartesian product, illustrated with Venn diagrams.
• Bijection: a function that is both injective and surjective, and therefore pairs elements of two sets one-to-one.

Chapter 6: Additional Topics

• Generating function: a power series whose coefficients are the terms of a sequence, used to manipulate and solve recurrences.
• Congruence modulo n: two integers are congruent if they leave the same remainder on division by n.
• Linear Diophantine equation: an equation ax + by = c to be solved in integers.

Critical Analysis

Strengths

• Built for inquiry-based teaching. Every section starts with an open-ended "Investigate!" question and a structured preview activity, ends with reading questions, and then offers practice problems and additional exercises. The preface describes using these in several ways—previews before class, activities as group work—and the structure also supports self-study.
• Large, varied exercise bank. The fourth edition adds nearly 300 exercises for a total of more than 750, separated into preview, reading, practice and additional exercises, plus a chapter review at the end of each chapter; selected hints and solutions fill two appendices.
• Interactive online version. Many preview activities and practice problems online give immediate feedback, some with randomised versions, and a Python scratch pad is available; Chapter 4 includes short Python examples for sequences.
• Counting through outcomes. The reworked counting chapter emphasises identifying sets of outcomes rather than memorising formulas, and the closing Investigate! of the chapter summary asks students to sort superficially similar problems by method.

Limitations

• Topic selection fits a particular course. The preface states that topics were chosen for students at the University of Northern Colorado; algorithm analysis (asymptotic notation), Boolean algebra, finite-state machines and formal languages are not covered, so computer science courses may need supplementary material.
• Limited depth in some areas. Number theory and generating functions are brief "additional topics", probability occupies a single section, and graph theory stops before topics such as network flows or shortest-path algorithms.
• Induction appears late. Induction is placed at the end of the sequences chapter rather than with the other proof methods in Chapter 1, which some instructors may want to move earlier.
• Print and PDF lose interactivity. The feedback, randomised practice and hidden hints are features of the online version; readers using the PDF need the appendices and discipline to check their work.

Applications in the Book

Applications are woven into examples and exercises rather than separate chapters. Graph theory is motivated by problems such as the Königsberg bridges, map colouring, polyhedra and matching problems; counting is applied to probability, including conditional probability; sequences connect to recursive descriptions of real situations, with Python used to compute terms; strong induction is related to divide-and-conquer reasoning; and number theory concludes with solving congruences and linear Diophantine equations.

Where It Fits in the Course

In this Discrete Mathematics list, Levin's book sits alongside Lovász, Pelikán and Vesztergombi's Discrete Mathematics: Elementary and Beyond, which is generally described as a problem-driven introduction with a stronger number-theory and combinatorics emphasis. Rosen's Discrete Mathematics and Its Applications and Epp's Discrete Mathematics with Applications are generally described as comprehensive textbooks; they cover topics Levin omits, such as algorithms and complexity, and can serve as references for computer science courses that use Levin as an accessible core text.

Graham, Knuth and Patashnik's Concrete Mathematics and van Lint and Wilson's A Course in Combinatorics go further. Levin's Chapters 3, 4 and 6 (counting, sequences and recurrences, generating functions) are good preparation for both; students who enjoy those chapters can move to Concrete Mathematics for summation and asymptotic techniques or to van Lint and Wilson for deeper combinatorics.

How to Use This Book

The book targets first- and second-year undergraduates in mathematics and computer science, including future school teachers; it also serves as a bridge-to-proof course. Secondary-school algebra is enough to begin, and no prior proof experience is assumed.

A one-semester course can follow the book in order: Chapter 0, Chapter 1 (logic and proofs), Chapter 2 (graph theory), Chapter 3 (counting) and Chapter 4 (sequences and induction), with Chapter 5 used as a reference or review and Chapter 6 as optional extension. The preface notes that sections are largely independent, so instructors can reorder topics. For each section, attempt the Investigate! question and preview activity before reading, answer the reading questions afterwards, then work the practice problems—ideally online for immediate feedback—before the additional exercises and the end-of-chapter review. Use the selected hints and solutions sparingly, as the author advises.

Edition and Sources

This guide is based on the fourth edition of Discrete Mathematics: An Open Introduction (© 2013–2025 Oscar Levin, CC BY-NC-SA 4.0; preface dated 2024, PDF built September 2025), read in the free PDF linked from the official edition page, https://discrete.openmathbooks.org/dmoi4.html. It draws on the acknowledgements, the preface (aims, inquiry-based design and fourth-edition changes), "How to Use This Book", the full table of contents to subsection level, Chapter 0 in full, the chapter summaries of Chapters 1–4, and section openings and key statements throughout, including Hall's Marriage Theorem, the pigeonhole principle and the sequences and induction material.