Discrete Mathematics – Lecture Notes (Lovász & Vesztergombi, Yale 1999)
2 Let us count!
Subsets of an n-element set: |\mathcal{P}(A)|=2^n (Theorem 2.1).
Sequences (strings) of length n over k symbols: k^n (Theorem 2.2).
Generalized string counting: if the first element has k1 options, the second k2 options, …, the nth kn options, then the number of strings is k1k2\cdots k_n (Theorem 2.3).
Subsets of order; binomial notation: \binom{n}{k} counts k-subsets of an n-set (Theorem 4.2 context).
Permutations of n objects: n! (Theorem 2.4).
Stirling’s approximation (Stirling’s Formula):
n! \sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^n.
3 Induction
The sum of the first n odd numbers is n^2.
Induction principle: if 1 has the property, and whenever n−1 has the property then n has it, then all positive integers have the property.
Classic exercises:
3.1 Prove that n(n+1) is even for all non‑negative n.
3.2 Prove 1+2+\cdots+n=\frac{n(n+1)}{2} (handshake/handshake-like).
3.3 Handshake: number of handshakes among n people is \frac{n(n-1)}{2}.
3.8 Sum of first n squares: 1^2+2^2+\cdots+n^2=\frac{n(n+1)(2n+1)}{6}.
3.9 Sum of first n powers of 2: 1+2+4+\cdots+2^{n}=2^{n+1}-1 (binary/subset viewpoint).
Induction revisited: use induction to reprove Theorems 2.1, 2.2, 2.3, 2.4; introduce the handshake view and the idea of a one-to-one correspondence (bijective counting).
3.13–3.14 Classic invalid inductions (for illustration): show how induction can fail if the inductive step is misapplied.
4 Counting subsets
4.1 The number of ordered subsets: for an ordered selection of k items from n without repetition, the count is n(n-1)\cdots(n-k+1).
4.2 The number of k-subsets: \binom{n}{k}=\frac{n!(n-k)!}{k!(n-k)!}=\frac{n!}{k!(n-k)!}.
4.3 Binomial Theorem: for any x,y and n≥0,
(x+y)^n=\sum{k=0}^{n}\binom{n}{k}x^{n-k}y^{k}. Substituting x=y=1 gives 2^n=\sum{k=0}^{n}\binom{n}{k}.4.4–4.6 Distributing presents and money; anagrams; related counting problems. Key idea: binomial coefficients arise naturally in partitioning n items into k groups or distributing identical items to recipients.
4.14–4.16 Special cases show how binomial coefficients yield familiar counts (e.g., distributing identical objects, rooks on boards).
5 Pascal’s Triangle
Structure: rows contain \binom{n}{0},\binom{n}{1},\dots,\binom{n}{n} with symmetry \binom{n}{k}=\binom{n}{n-k} (5.1).
5.1 Identities: Pascal’s rule \binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}; used to generate triangle row by row.
5.2 A bird’s-eye view: largest entries are near the middle; growth: central binomial coefficients ~ \frac{2^n}{\sqrt{\pi n/2}} (approximate, via Stirling).
5.3 Sums in a row: \sum_{k=0}^n\binom{n}{k}=2^n. (extension of binomial theorem).
5.5 Additional identities such as convolution sums and diagonal sums; connection to counting n-element subsets with restrictions (e.g., exactly k from first half).
6 Fibonacci numbers
Definition: F1=F2=1; Fn+1=Fn+Fn−1; sequence 1,1,2,3,5,8,…; often extended with F0=0.
6.1 Fibonacci’s exercise: solution by recurrence; closed form (Binet) via golden ratio φ=(1+√5)/2 and ψ=(1-√5)/2:
F_n=\frac{φ^n-ψ^n}{\sqrt{5}}, where φ=\frac{1+\sqrt{5}}{2}, \ ψ=\frac{1-\sqrt{5}}{2}.6.2–6.3 identities and sums; key identity: \sum{i=0}^n Fi=F_{n+2}-1.
6.8 Growth and approximation: Fn grows roughly like φ^n/√5; ratio Fn+1/Fn → φ ≈ 1.618…
6.9–6.12 additional properties and planarity/diagonal arguments related to Fibonacci numbers.
7 Combinatorial probability
7.1 Probability basics: finite sample space S; events are subsets of S; uniform spaces have P(A)=|A|/|S|.
7.2 Independence of repeated trials: sequences in S^n; P(a1,…,an)=1/|S|^n for uniform independence.
7.3 Law of Large Numbers (simple form): for 2m coin tosses, probability that number of heads deviates from m by more than t is at most m/t^2. Corollary: with high probability heads count stays within m±O(√m).
7.4–7.8: basic probability identities; independence and exclusivity; simple algebraic relations such as P(A∩B)+P(A∪B)=P(A)+P(B).
8 Integers, divisors, and primes
8.1 Divisibility basics; division with remainder; gcd(a,b) and lcm(a,b) definitions.
8.2–8.6 Primes, fundamental theorem of arithmetic (unique prime factorization): every positive integer factors uniquely into primes. Outline of a minimal/contradiction proof.
8.7 Testing for primality; Fermat’s little theorem: if p is prime, then p|a^p−a for all integers a; Fermat’s theorem provides primality tests (with caveats due to pseudoprimes like 341).
8.10–8.12 Irrationality of sqrt(p) for prime p; general irrationality criteria.
8.3–8.4 Factorization and gcd/lcm formulas; gcd·lcm=ab; Euclidean algorithm for gcd; complexity bound: number of steps ≤ log2(a)+log2(b).
8.3 Fundamental theorem of number theory variants; prime distribution conjectures (briefly) and Prime Number Theorem statement: π(n) ~ n/log n.
8.6–8.7 Primality heuristics and probabilistic tests (Miller–Rabin) with error probability decreasing with repetitions; RSA as public-key cryptography example.
9 Graphs
Graph basics: G=(V,E); degree d(v); sum of degrees equals twice the number of edges (Theorem 9.2).
9.1 Parity: in any graph, the number of vertices of odd degree is even (hence even count of odd-degree vertices).
9.2 Paths, cycles, connectivity; complete graphs, paths, cycles; subgraphs and connected components; definition of connected vs. disconnected graphs.
Additional exercises guide counting edges, degree sums, and graph classifications.
10 Trees
Definition: a tree is a connected graph with no cycles; or equivalently, no cycles and minimally connected.
10.1–10.4 Properties: every tree with n≥2 nodes has at least two leaves (degree-1 nodes); tree-growing procedure preserves tree structure; any tree can be grown by adding a new leaf.
10.4 Cayley’s Theorem: number of labelled trees on n nodes is n^{n-2}.
10.11–10.12 Prüfer code and planar code: bijection between labelled trees and sequences of length n−2 over {0,…,n−1}; this gives a compact encoding and a constructive way to generate random trees; unlabelled trees have much more complex counting (Polya’s enumeration). Planar code encodes unlabelled trees with 2(n−1) bits (not optimal but useful).
11 Finding the optimum
Tree-based optimization: cheapest spanning tree (minimize total edge cost); optimal cycles (Travelling Salesman Problem, TSP) and relationships to spanning trees.
Greedy (optimistic) approach to build a cheap tree is optimal in this context; contrasting with a greedy approach to form a cycle (which need not be optimal).
Shortcutting a tour around a minimum spanning tree yields a tour with cost at most twice the MST, hence within factor 2 of the optimum tour under triangle inequality.
11.5–11.6 Basic questions about optimality and non-crossing tours under triangle inequality.
12 Matchings in graphs
12.1 A dancing problem and bipartite graphs: model dancers as bipartite graph A (e.g., boys) and B (e.g., girls); a perfect matching is a set of edges covering all vertices.
12.2 Other matching problems; general bipartite matching considerations.
12.3 Hall’s Marriage Theorem (The Marriage Theorem): A bipartite graph with |A|=|B| has a perfect matching iff for every subset S of A, the neighborhood N(S) has size |N(S)|≥|S|. (The converse argument applies by symmetry.)
12.4 Augmenting path algorithm: start from a (partial) matching; if an augmenting path exists, we can increase the matching size by 1; iterate until no augmenting path exists or a perfect matching is achieved.
12.5 Practical aspects: the algorithm yields a polynomial-time approach to bipartite matching; general non-bipartite cases require more advanced machinery.
13 Graph coloring
13.1 Regions formed by circles can be 2-colored; even lines create 2-colorings; parity arguments apply.
13.2 For lines, 2-colorability holds; color by parity of number of lines separating a region from the outside.
13.3–13.5 Briefly: 4-color theorem intuition; colorings of planar graphs; dual graphs and related results.
14 A Connecticut class in King Arthur’s court
NP vs P concepts; some problems have easy certificates (proofs) of infeasibility vs feasibility.
The story motivates the distinction between problems where existence can be efficiently verified (and sometimes found) vs. those where no efficient certificate is known (e.g., Hamiltonian cycles vs. perfect matchings in bigraphs).
Emphasizes the idea that some problems are NP-hard / NP-complete in nature.
15 A glimpse of cryptography
Classical cryptography: substitution codes; vulnerability via frequency analysis; need for stronger schemes.
One-time pads: perfectly secure if the key is random, as long as the message and never reused (the pad is as long as the message).
Public-key cryptography: RSA as a core example; relies on the hardness of factoring large numbers (product of two large primes).
RSA outline:
Choose large primes p and q; m=pq; choose e with gcd(e,(p−1)(q−1))=1; compute d such that ed ≡ 1 (mod (p−1)(q−1)).
Public key (m,e); private key d. Encryption: c ≡ x^e (mod m). Decryption: x ≡ c^d (mod m).
Security rests on the difficulty of factoring m; if one could factor m, one could derive the private key.
Practical notes: 100–200 digit primes used; RSA is widely used in SSL/TLS; large integer arithmetic with modular exponentiation via fast exponentiation (repeated squaring).
16 One-time pads and public-key cryptography (RSA) (continued)
16.1–16.3 Further cryptography topics: password verification without revealing the password; generating large primes; practical issues in choosing primes.
16.4 Public key cryptography (RSA) details: modular exponentiation, the importance of modular reduction, and fast exponentiation techniques; RSA security relies on factoring difficulty.
16.6–16.7 Practical security discussions and hypothetical attacks; if factoring becomes efficient, RSA becomes breakable; session-key strategies (hybrid cryptosystems) to balance speed and security.
Key formulas and concepts (quick reference)
Subsets: |\mathcal{P}(A)|=2^{|A|}
Strings from k symbols: k^n; ordered subsets: n(n-1)\cdots(n-k+1)
Binomial coefficients: \binom{n}{k}; binomial theorem: (x+y)^n=\sum_{k=0}^n\binom{n}{k}x^{n-k}y^{k}
Subset counts: \binom{n}{k} = \frac{n!}{k!(n-k)!}; total subsets: \sum_{k=0}^n\binom{n}{k}=2^n
Permutations: n!; Stirling (approx): n!\sim\sqrt{2\pi n}\left(\frac{n}{e}\right)^n
The Pascal triangle: symmetry \binom{n}{k}=\binom{n}{n-k}; convolution identity: \binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}
Fibonacci numbers: F1=F2=1; Fn+1=Fn+Fn−1; closed form (Binet):
F_n=\frac{\phi^n-\psi^n}{\sqrt{5}},\quad \phi=\frac{1+\sqrt{5}}{2},\ \psi=\frac{1-\sqrt{5}}{2}Probability (uniform space): if |A| outcomes in A and |S| total, then P(A)=|A|/|S|; Law of Large Numbers: deviations bounded by a function of m and t (e.g., P(|\text{Heads}-m|>t)\le \frac{m}{t^2} for 2m trials).
Graphs: sum of degrees equals twice the number of edges; number of odd-degree vertices is even; Hall’s marriage theorem (for bipartite graphs) for perfect matchings.
Trees: Cayley’s theorem \text{# labelled trees on }n\text{ nodes}=n^{n-2}; Prüfer code: a bijection between labelled trees on n nodes and sequences of length $n-2$ over {0,…,n−1}.
RSA (public-key cryptography): pick primes p,q; m=pq; public key (m,e); private key d with ed ≡ 1 (mod (p−1)(q−1)); encryption x^e mod m; decryption x^d mod m.
If you’d like, I can tailor the notes to a specific exam focus (e.g., only combinatorics, or only graph theory) or convert these into a printable one-page cheat-sheet with the essential theorems and formulas annotated for quick recall.