Discrete Mathematics: Elementary and Beyond

Citation

Lovász, L., Pelikán, J., & Vesztergombi, K. (2003). Discrete Mathematics: Elementary and Beyond. Springer (Undergraduate Texts in Mathematics).

Chapter Summary

The book has fifteen short chapters on about 290 pages, followed by a long final chapter of answers to exercises. The preface explains that it does not try to cover discrete mathematics in depth. It discusses selected results and methods, mostly from combinatorics and graph theory, with a little elementary number theory, probability and combinatorial geometry. Section titles are often informal ("A Party", "Distributing Presents", "A Planet Under Attack").

Chapter 1: Let's Count!

The book opens with a party (who shakes hands with whom, how many seatings there are) and builds the basic counting tools from it. It covers sets, the number of subsets and its approximate size, sequences, permutations, ordered subsets and subsets of a given size.

Chapter 2: Combinatorial Tools

Induction, comparing and estimating numbers, inclusion–exclusion and the pigeonhole principle. The chapter closes with "the twin paradox and the good old logarithm".

Chapter 3: Binomial Coefficients and Pascal's Triangle

The binomial theorem and counting problems about distributing presents and money and forming anagrams lead to Pascal's triangle. The chapter studies its identities and then takes a "bird's-eye" and an "eagle's-eye" view of how the coefficients behave.

Chapter 4: Fibonacci Numbers

Fibonacci's rabbit exercise, a collection of identities, and an explicit formula for the Fibonacci numbers.

Chapter 5: Combinatorial Probability

Events and probabilities on finite sample spaces, independent repetition of an experiment, the law of large numbers, and a section on the law of small numbers and the law of very large numbers.

Chapter 6: Integers, Divisors, and Primes

The longest chapter: divisibility, primes and their history, factorization into primes, the set of primes, Fermat's "little" theorem, the Euclidean algorithm and congruences. It continues with "strange numbers", connections between number theory and combinatorics, and primality testing.

Chapter 7: Graphs

Even and odd degrees, paths, cycles and connectivity, and Eulerian walks and Hamiltonian cycles.

Chapter 8: Trees

How to define, grow, count and store trees, and the number of unlabeled trees.

Chapter 9: Finding the Optimum

Two optimization problems on graphs: finding the best tree and the traveling salesman problem.

Chapter 10: Matchings in Graphs

A dancing problem and a second matching problem motivate the main theorem on matchings, followed by a method for finding a perfect matching.

Chapter 11: Combinatorics in Geometry

Counting intersections of diagonals and regions, and results on convex polygons.

Chapter 12: Euler's Formula

"A planet under attack" introduces planar graphs and Euler's formula for polyhedra.

Chapter 13: Coloring Maps and Graphs

Coloring regions and graphs with two colors, coloring graphs with many colors, and map coloring and the Four Color Theorem.

Chapter 14: Finite Geometries, Codes, Latin Squares, and Other Pretty Creatures

Small exotic worlds, finite affine and projective planes, block designs, Steiner systems, Latin squares and codes.

Chapter 15: A Glimpse of Complexity and Cryptography

Starting from a "Connecticut class in King Arthur's court", the chapter discusses classical cryptography. It then turns to saving the last move in chess, verifying a password without learning it, finding large primes, and public-key cryptography.

Chapter 16: Answers to Exercises

Answers to the exercises in the text, running to more than thirty pages.

Key Concepts

Chapters 1–4: Counting

• Counting subsets and permutations: the basic counts behind binomial coefficients and factorials.
• Inclusion–exclusion and pigeonholes: two general tools for counting and existence arguments.
• Pascal's triangle: the arrangement of binomial coefficients, with its identities and large-scale behaviour.
• Fibonacci numbers: a recurrence with many identities and an explicit closed formula.

Chapters 5–6: Probability and number theory

• Law of large numbers: the behaviour of averages under repeated independent experiments.
• Unique factorization into primes: every integer is a product of primes in essentially one way.
• Euclidean algorithm and congruences: computing greatest common divisors and arithmetic modulo m.
• Fermat's little theorem and primality testing: the link between congruences and recognizing primes.

Chapters 7–13: Graphs

• Eulerian walks and Hamiltonian cycles: traversing every edge once versus visiting every vertex once.
• Trees: connected graphs without cycles, and how to count and store them.
• Optimization on graphs: choosing the best tree in a network, and the traveling salesman problem.
• Perfect matchings: when the vertices of a graph can be paired along edges.
• Planar graphs and Euler's formula: the relation between vertices, edges and faces.
• Graph and map coloring: two-colorability and the Four Color Theorem.

Chapters 14–15: Designs, codes and cryptography

• Finite projective planes and block designs: finite structures with balanced incidence properties.
• Latin squares and codes: combinatorial arrangements and error-correcting codes.
• Public-key cryptography: encryption based on number theory, after classical cryptography and complexity ideas.

Critical Analysis

Strengths

• Selective by design. The preface says the book does not aim to cover discrete mathematics in depth, which it calls ill-defined and impossible anyway. Instead it develops chosen results carefully, so each topic has room for motivation and proof.
• Proofs and problem solving at the centre. The authors give proofs wherever possible. Where a proof is too hard, they say that it is technical and beyond the book's scope. Readers are urged to answer the questions posed in the text and to work the problems at the end of each chapter "as puzzle solving".
• Shows mathematics as connected and alive. The preface hopes to show that results build on earlier ones, that there are pressing unsolved problems, and that beauty of ideas matters. The contents reach from Pascal's triangle and Fibonacci numbers to finite geometries, codes, complexity and public-key cryptography.
• Answers included. A substantial chapter of answers supports self-study.

Limitations

• Not a full discrete mathematics course. Logic, formal set theory, relations, recurrence-solving techniques beyond the Fibonacci numbers, and generating functions do not appear among the chapter headings. A course that requires these will need a fuller text.
• Light on algorithms as a subject. Algorithms appear inside topics such as the Euclidean algorithm, spanning trees, matchings and primality testing. There is no systematic treatment of algorithm analysis.
• Some chapters are brief. Several chapters run to about ten pages (Combinatorics in Geometry, Euler's Formula), so they introduce a topic rather than develop it at length.

Where It Fits in the Course

Within this course list, Lovász, Pelikán and Vesztergombi is the problem-centred, mathematician's introduction. Oscar Levin's free Discrete Mathematics: An Open Introduction and Susanna Epp's Discrete Mathematics with Applications cover the standard first course, including logic and proof techniques, more systematically. Kenneth Rosen's Discrete Mathematics and Its Applications is the comprehensive reference, broader than this book in almost every direction. Students taking a standard course from one of those books can read the matching chapters here for a deeper, more puzzle-led treatment of counting, number theory and graphs.

For more advanced study, Graham, Knuth and Patashnik's Concrete Mathematics develops sums, recurrences and generating functions far beyond Chapter 4 here. van Lint and Wilson's A Course in Combinatorics takes designs, codes, Latin squares and graph theory, the subjects of Chapters 10–14, to research level. Chapter 14 is a good preview of that book.

How to Use This Book

The publisher aims the book at undergraduate mathematics and computer science students who want a feeling for what mathematics is about. The preface addresses readers whose only college mathematics so far may be calculus. No calculus is needed, only secondary-school mathematics and willingness to work problems, since induction is introduced in Chapter 2.

• Core: Chapters 1–3 on counting, Chapter 6 on number theory, and Chapters 7–8 on graphs and trees form the backbone.
• Choose by interest: Chapter 5 for probability, Chapters 9–10 for optimization and matchings, Chapters 11–13 for geometry, planarity and coloring, Chapter 14 for designs and codes, and Chapter 15 for complexity and cryptography. Chapter 15 draws on the number theory of Chapter 6.
• Work the questions as you read. The preface treats problem solving as essential. Try each question in the text before reading on, and work the end-of-chapter problems before checking Chapter 16.
• Pair it with a systematic text if your course examines logic, relations or recurrences, and use this book for depth and motivation on the topics it does cover.