Discrete Mathematics: An Open Introduction PDF Download – Oscar Levin (4th Edition)

Students taking Discrete Structures can download the complete textbook “Discrete Mathematics: An Open Introduction” by Oscar Levin, free as a PDF from the author’s own Open Math Books site. It is a proof-driven, example-heavy text built around a small set of recurring structures — logic, sets, functions, sequences, relations, and graphs — introduced once in Chapter 0 and then taught in full over the chapters that follow.

This is a first course in mathematical reasoning rather than computation: it covers logic and proof technique, graph theory, counting and combinatorics, sequences and induction, and sets and functions, with an optional closing chapter on generating functions and number theory. No calculus background is required, and the 4th edition (Fall 2024) is the most recently updated book in this project’s Mathematics category.

Book Overview

Course	Discrete Structures
Degree Programs	BSCS, BSIT, BSSE, BS Mathematics — typically a first- or second-semester requirement
Level	University — first or second semester
Edition	4th Edition — Fall 2024
Author	Oscar Levin, University of Northern Colorado
Structure	7 chapters (0–6): Preliminaries, Logic & Proofs, Graph Theory, Counting, Sequences, Sets & Functions, and an optional Additional Topics chapter
Exercises	Every section ends with a practice-problem set, many chapters include reading questions, and selected hints/solutions are collected in the back matter
Language	English
License	Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) — Model: Link-only
Format	Free PDF and a free web/HTML reader with per-section, linkable pages

Chapter List

Chapter 0: Introduction and Preliminaries

Difficulty: Easy · Discrete Structures · Key topics: what discrete math is, sets, functions, sequences, relations, graphs (a preview)

This short opening chapter orients you to a mathematics fundamentally unlike the calculus you’ve likely already studied — discrete mathematics deals with countable, distinct objects rather than continuous change. Section 0.1 explains what makes the subject different and sets expectations for how the rest of the book reads: proof-driven, example-heavy, and built around a small set of recurring structures. Section 0.2 previews those structures — sets, functions, sequences, relations, and graphs — each introduced just deeply enough to recognize when it reappears, in full, in a later chapter. Read it as a map, not a destination.

Key Points:

• Discrete math studies distinct, countable objects, not continuous change — a genuine shift from calculus
• Six recurring structures anchor the whole book: sets, functions, sequences, relations, graphs, and others introduced later
• Each structure gets only a brief preview here; full treatment comes in its own chapter
• The chapter doubles as an orientation to the book’s proof-driven, example-heavy style

Practice Tip: Skim this chapter fast on a first read, then come back to Section 0.2 as a glossary whenever a later chapter references a structure you don’t fully recall.

Common Mistake: Treating this chapter as skippable. It sets vocabulary — “set,” “relation,” “well-defined function” — that later chapters use without redefining.

Important Questions:

• What makes discrete mathematics different from the calculus most students study first? Discrete math studies objects that are countable and distinct — integers, finite sets, graphs — rather than continuous quantities that vary smoothly, so its core tools are logic, counting, and proof rather than limits and derivatives.
• Name the five main discrete structures previewed in Section 0.2. Sets, functions, sequences, relations, and graphs — each gets a full chapter (or more) later in the book.

Chapter 1: Logic and Proofs

Difficulty: Medium · Discrete Structures · Key topics: mathematical statements, implications, rules of logic, direct/contrapositive/contradiction proofs

Discrete mathematics runs on proof, and this chapter builds the toolkit from scratch. It starts with mathematical statements — precisely what makes a sentence true or false — before moving to implications and the logical connectives (and, or, not) that combine them, including truth tables and logical equivalence. From there the chapter turns practical: direct proof, proof by contrapositive, and proof by contradiction, each demonstrated on genuine discrete-math claims about integers, sets, and divisibility rather than toy examples. The closing section applies every technique to proofs specifically about the discrete structures previewed in Chapter 0, so the skills transfer immediately.

Key Points:

• A mathematical statement is precisely true or false — vague sentences aren’t statements at all
• Implications (if P then Q) have a converse, inverse, and contrapositive — only the contrapositive is logically equivalent to the original
• Truth tables settle whether two logical statements are equivalent, mechanically
• Direct proof, proof by contrapositive, and proof by contradiction are the three core proof strategies covered
• Choosing contrapositive over direct proof is often the difference between an easy proof and a stuck one
• Every technique is practiced on real claims about integers, sets, and divisibility, not abstract symbols alone

Practice Tip: Before writing any proof, translate the claim into if-P-then-Q form and ask whether proving the contrapositive (if not-Q then not-P) looks easier — for many number-theory claims, it is.

Common Mistake: Confusing a statement’s converse with its contrapositive. “If P then Q” and “if Q then P” (the converse) are NOT logically equivalent, even though they look like a simple swap — only “if not-Q then not-P” (the contrapositive) is guaranteed equivalent.

Important Questions:

• What is the difference between a statement’s converse and its contrapositive, and which one is logically equivalent to the original? The converse of “if P then Q” is “if Q then P”; the contrapositive is “if not-Q then not-P.” Only the contrapositive is guaranteed logically equivalent to the original — the converse can be false even when the original is true.
• Outline the structure of a proof by contradiction. Assume the claim is false (assume its negation), then reason logically from that assumption until you reach a statement that is self-evidently false or contradicts a known fact — since your only unproven assumption was the negation, that assumption must be false, so the original claim is true.

Chapter 2: Graph Theory

Difficulty: Hard · Discrete Structures · Key topics: vertices/edges, trees, planar graphs, Euler trails/circuits, coloring, bipartite matching

Graphs — networks of vertices connected by edges — are the discrete structure most directly useful for modeling real networks, from road maps to social connections, and this is the book’s longest chapter. It opens with basic definitions and classic motivating problems, then covers trees and spanning trees, planar graphs and Euler’s formula (V − E + F = 2), and the classic Euler-trail/Hamiltonian-path distinction — “visit every edge once” versus “visit every vertex once” are genuinely different problems. Later sections cover vertex and edge coloring (including the four-color theorem), reinterpret relations as graphs, and close with matching in bipartite graphs — the assignment-problem structure behind everything from job-matching to marriage-stability algorithms.

Key Points:

• A graph is vertices plus edges connecting them — deceptively simple, capable of modeling almost any network
• Trees are connected graphs with no cycles; a spanning tree touches every vertex using the fewest possible edges
• Euler’s formula (V − E + F = 2) governs every planar graph, and identifies K5 and K3,3 as graphs that can never be drawn without crossings
• An Euler trail visits every edge exactly once; a Hamiltonian path visits every vertex exactly once — different problems with very different difficulty
• The four-color theorem says every planar map needs at most four colors so no two adjacent regions share one
• Relations from set theory can be drawn as graphs, connecting this chapter back to the abstract algebra of Chapter 5
• Bipartite matching finds valid pairings between two groups — the mathematics behind stable job/marriage assignment problems

Memory Tip: Keep Euler and Hamilton straight by their letter count: “Euler trail” is about Edges, “Hamiltonian path” is about vertices — H for “hit every vertex.”

Common Mistake: Assuming every connected graph has an Euler circuit. A graph has an Euler circuit only if every vertex has even degree — a graph with odd-degree vertices either has no Euler circuit or, with exactly two odd vertices, an Euler trail but not a closed circuit.

Important Questions:

• State Euler’s formula for planar graphs and what it’s used for. V − E + F = 2, where V is vertices, E is edges, and F is faces (including the unbounded outer face). It’s used to prove which graphs can and cannot be drawn without edge crossings — for instance, it shows K5 (five mutually connected vertices) is never planar.
• What condition on vertex degrees determines whether a connected graph has an Euler circuit? A connected graph has an Euler circuit if and only if every vertex has even degree. If exactly two vertices have odd degree, the graph has an Euler trail (starting and ending at those two vertices) but not a closed circuit.

Chapter 3: Counting

Difficulty: Hard · Discrete Structures · Key topics: Pascal’s triangle, sum/product principles, inclusion-exclusion, permutations/combinations, multisets, probability

Counting sounds elementary but becomes genuinely subtle once outcomes can overlap or repeat, and this chapter builds the full combinatorics toolkit a discrete-math course needs. It starts from Pascal’s triangle and the closely related sum and product principles, then tackles non-disjoint outcomes with the Inclusion-Exclusion Principle. The heart of the chapter distinguishes permutations (order matters) from combinations (order doesn’t), develops the “stars and bars” technique for counting multisets, and shows how to prove binomial identities by counting the same set two different ways — a combinatorial proof. The chapter closes by applying every technique to discrete probability and extending Inclusion-Exclusion to harder counting problems, including derangements.

Key Points:

• The product principle (multiply) applies to sequential independent choices; the sum principle (add) applies to mutually exclusive alternatives
• Permutations count ordered arrangements; combinations count unordered selections — the Quotient Principle converts between them
• The Inclusion-Exclusion Principle corrects for double-counting when outcomes overlap: add the individual counts, then subtract the overlap
• “Stars and bars” counts multisets (selections that allow repeats) by converting them into a bit-string counting problem
• A combinatorial proof establishes an algebraic identity by counting one collection two different ways and showing both counts must be equal
• Pascal’s triangle encodes the binomial coefficients and reveals several of these identities visually, as row and diagonal patterns
• Discrete probability is just counting favorable outcomes divided by total outcomes — every technique in the chapter feeds directly into it

Practice Tip: When a counting problem feels stuck, ask explicitly: does order matter (permutation) or not (combination)? Can an item be chosen more than once (multiset) or not? Naming these two properties out loud picks the right formula almost every time.

Common Mistake: Applying a plain combination formula when outcomes actually overlap. If two conditions can both be true for the same outcome, counting each condition separately and adding double-counts the overlap — Inclusion-Exclusion (subtracting the overlap back out) is required, not optional.

Important Questions:

• What’s the difference between a permutation and a combination, and how does the Quotient Principle relate them? A permutation is an ordered arrangement (ABC and BCA count as different); a combination is an unordered selection (ABC and BCA count as the same). The Quotient Principle gets combinations from permutations by dividing the number of permutations by the number of ways to reorder each selection (k! for a selection of size k).
• State the Inclusion-Exclusion Principle for two overlapping sets A and B. |A ∪ B| = |A| + |B| − |A ∩ B| — add the sizes of the two sets, then subtract the size of their overlap once, since counting A and B separately counts every element in both twice.

Chapter 4: Sequences

Difficulty: Hard · Discrete Structures · Key topics: describing sequences, arithmetic/geometric/polynomial/exponential growth, induction, strong induction

This chapter studies infinite sequences of numbers and the two proof techniques used to establish facts about them. It opens with ways to describe a sequence — explicit formulas, partial sums, and term-to-term differences, worked through in Python — before classifying growth patterns as arithmetic (constant difference), geometric (constant ratio), polynomial, or exponential, each with its own summation technique (reverse-and-add for arithmetic sums, the characteristic-root method for exponential recurrences). The chapter’s real payoff is proof by mathematical induction: a rigorous way to prove a claim holds for every natural number by proving a base case and an inductive step. Strong induction extends this to recursive claims that depend on more than just the immediately preceding case.

Key Points:

• A sequence can be described explicitly (a formula for the nth term) or recursively (each term defined from previous ones)
• Arithmetic sequences have a constant difference between terms; geometric sequences have a constant ratio
• “Reverse and add” sums an arithmetic sequence quickly by pairing the first and last terms, second and second-last, and so on
• The characteristic root method solves recurrence relations for exponential/geometric sequences by turning them into a polynomial equation
• Proof by induction has two parts: a base case (the claim holds for the first value) and an inductive step (if it holds for k, it holds for k+1)
• Strong induction is the same idea, except the inductive step may use ANY earlier case, not just the immediately preceding one — essential for divide-and-conquer arguments

Memory Tip: Think of induction as dominoes: the base case knocks over the first domino, and the inductive step proves that any falling domino knocks over the next one — together they guarantee every domino falls, forever.

Common Mistake: Writing an inductive step that shows the claim is true for k+1 without explicitly using the inductive hypothesis (that it’s true for k). If the hypothesis is never actually used, the argument isn’t really induction — it’s an incomplete, separate proof for each case.

Important Questions:

• What are the two required parts of a proof by mathematical induction? A base case, proving the claim holds for the smallest value (usually n=0 or n=1), and an inductive step, proving that IF the claim holds for some value k, THEN it also holds for k+1.
• How does strong induction differ from ordinary (weak) induction? In strong induction, the inductive step may assume the claim is true for ALL values up to and including k (not just k itself) when proving it for k+1 — essential for recursive or divide-and-conquer arguments where a case depends on more than just the immediately preceding one.

Chapter 5: Discrete Structures Revisited

Difficulty: Medium · Discrete Structures · Key topics: sets (notation, operations, Venn diagrams), functions (injective/surjective/bijective, image/inverse image)

A short, self-contained reference chapter that gathers the two most foundational discrete structures — sets and functions — into full treatments, either as first exposure or as review before the harder chapters that depend on them. Section 5.1 covers set notation, subset and equality relationships, the standard operations (union, intersection, complement, difference), and Venn diagrams as a visual aid. Section 5.2 covers functions properly: how to describe a function by its domain, codomain, and rule, and the three key classifications — injective (one-to-one), surjective (onto), and bijective (both) — along with image and inverse image, the sets a function maps to and from.

Key Points:

• A set is a well-defined, unordered collection of distinct elements — no element can appear twice, and order doesn’t matter
• The core set operations are union (∪), intersection (∩), complement, and difference — Venn diagrams make all four visually intuitive
• A function is injective if no two inputs share an output, surjective if every possible output is hit, and bijective if both hold
• Only a bijective function has a well-defined inverse function
• The image of a function is the set of outputs it actually produces; the inverse image of a set is every input that maps into it
• This chapter is explicitly designed as a standalone reference — read it early for foundations, or return to it later as review

Practice Tip: When classifying a function, check injective and surjective separately and explicitly — a function can be one without the other (x² on all reals is neither; restricted to non-negative reals, it becomes injective).

Common Mistake: Assuming every function has an inverse. Only bijective functions (both injective and surjective) have a genuine inverse function — a function that is only injective or only surjective cannot be reversed as a proper function on the full codomain.

Important Questions:

• Define injective, surjective, and bijective for a function f: A → B. Injective (one-to-one): no two distinct inputs map to the same output. Surjective (onto): every element of B is the output of at least one input. Bijective: both injective and surjective — every output is hit exactly once.
• What is the difference between the image and the inverse image of a function? The image of f is the set of all outputs f actually produces (a subset of the codomain B). The inverse image of a subset of B is the set of all inputs in A that map into that subset.

Chapter 6: Additional Topics

Difficulty: Hard · Discrete Structures · Key topics: generating functions, number theory (divisibility, congruence, linear Diophantine equations)

An optional capstone chapter covering two advanced topics that many, but not all, Discrete Structures courses include. Generating functions represent a whole sequence as a single formal power series, turning sequence problems into algebra problems — the section covers building a generating function from a sequence, manipulating it through differencing and multiplication, and using it to solve recurrence relations in closed form, an alternative to the characteristic-root method from Chapter 4. The number theory section covers divisibility, remainder classes and congruence (the arithmetic of remainders, or “clock arithmetic”), and solving both congruences and linear Diophantine equations — integer-only solutions to linear equations, with direct application to cryptography.

Key Points:

• A generating function encodes an entire sequence as the coefficients of a formal power series — sequence problems become algebra problems
• Differencing and multiplying generating functions correspond to specific, predictable operations on the underlying sequence
• Generating functions offer a second route to solving recurrence relations, alongside the characteristic-root method from Chapter 4
• Two integers are congruent modulo n if they leave the same remainder when divided by n — the basis of “clock arithmetic”
• A linear Diophantine equation asks for integer-only solutions to a linear equation, and has one if and only if gcd of the coefficients divides the constant term
• Both sections are flagged by the book itself as optional/additional — not every Discrete Structures course covers this chapter, so check your syllabus

Practice Tip: Treat this chapter as elective unless your course syllabus specifically lists generating functions or number theory — many one-semester Discrete Structures courses stop at Chapter 5 and never assign Chapter 6.

Common Mistake: Assuming every linear Diophantine equation has an integer solution. ax + by = c has one if and only if gcd(a,b) divides c — if it doesn’t, no integer solution exists at all, no matter how you search.

Important Questions:

• What is a generating function, in one sentence? A generating function represents an entire sequence a0, a1, a2, … as the coefficients of a formal power series a0 + a1x + a2x² + …, turning sequence and recurrence problems into algebra problems on the power series.
• When does the linear Diophantine equation ax + by = c have an integer solution? If and only if gcd(a, b) divides c evenly. If it does, infinitely many integer solutions exist (found via the extended Euclidean algorithm); if it doesn’t, no integer solution exists.

---

Download Discrete Mathematics: An Open Introduction PDF (Free)

This book is free from its official source, author Oscar Levin’s own Open Math Books site. Click below to download the complete PDF — a free web-based reader edition (with per-section, linkable pages) is also available if you’d rather read online.

↓ Download PDF

---

How to Study This Book

Chapter 0 is a short map, not a full lesson — skim it once, then treat Section 0.2 as a glossary to revisit whenever a later chapter references “sets,” “relations,” or another structure you don’t fully recall.

Chapter 1 (Logic and Proofs) is the real foundation — every later chapter assumes you can write a direct proof, a proof by contrapositive, and a proof by contradiction without hesitation. Do not move on until these feel routine.

Chapters 2 through 4 (Graph Theory, Counting, Sequences) can usually be read in the order your syllabus assigns them — they don’t depend heavily on each other, though Chapter 4’s induction proofs are used informally throughout Chapter 2’s graph arguments.

Chapter 5 (Discrete Structures Revisited) is written as a standalone reference on sets and functions. If your course covers sets and functions early, read it right after Chapter 1 instead of where it’s numbered — the book itself says it can be read either way.

Chapter 6 (Additional Topics: generating functions and number theory) is explicitly optional in the book’s own structure. Many one-semester Discrete Structures courses never assign it — check your syllabus before spending time on it.

This is the 4th edition (Fall 2024), the most recently updated book in this project’s Mathematics category — content and examples are current, with no age caveat needed anywhere in the book.

---

Used In These Programs

This book is used for the Discrete Structures course in: BSCS, BSIT, BSSE, and BS Mathematics programs. Browse all Discrete Mathematics books or all Mathematics books.

Who Should Read This

Discrete Mathematics: An Open Introduction is written for a student taking their first proof-based mathematics course — typically a first- or second-semester BSCS, BSIT, BSSE, or BS Mathematics student who has finished (or is finishing) high-school-level algebra but has not yet written a formal mathematical proof. Unlike the calculus books in this project, almost nothing here requires prior calculus — the prerequisite is comfort with algebraic notation and a willingness to think carefully and slowly rather than compute quickly. Its short sections, embedded reading questions, and large practice-problem sets suit self-study as well as classroom use, and its free web reader links every term to its own definition.

---

Applicable Universities

This book is useful for students at Pakistani universities offering BSCS, BSIT, BSSE, or BS Mathematics programs, including Punjab University, Virtual University, COMSATS, FAST, UET, NUST, and other HEC-recognized institutions, where Discrete Structures is a required core course.

FAQs

Related Books

• Think Python – Allen B. Downey (3rd Edition)
• Problem Solving with Algorithms and Data Structures using Python

Discrete Mathematics: An Open Introduction is this project’s first non-calculus Mathematics-category book — a foundational, proof-based course most BSCS, BSIT, BSSE, and BS Mathematics students take early in their degree. Browse more Mathematics books for the rest of your semester.

Discrete Mathematics: An Open Introduction, 4th Edition, by Oscar Levin. Free under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International licence. Access for free at https://discrete.openmathbooks.org/dmoi4.html