Combinatorics and Graph Theory
Year 2 · 5 sections · 52 concepts · 115 practice questions
What's covered
free1 · Counting10 concepts
- Overview 1 · The plan of this section
- Proposition 1.1 · Binomial identities by double counting
- Proposition 1.2 · Vandermonde's identity
- Proposition 1.3 · Stars and bars
- Theorem 1.4 · Inclusion–exclusion
- Corollary 1.5 · Derangements
- Proposition 1.6 · Counting surjections
- Definition 1.7 · Stirling numbers of the second kind
- Proposition 1.8 · The Stirling recurrence
- Check 1.9 · Check: counting problems
2 · Generating functions and recurrences9 concepts
- Overview 2 · The plan of this section
- Definition 2.1 · Ordinary generating functions
- Proposition 2.2 · Products of generating functions count combinations
- Theorem 2.3 · Solving linear recurrences with generating functions
- Example 2.4 · The Fibonacci numbers
- Proposition 2.5 · The Catalan recurrence
- Theorem 2.6 · Closed form of the Catalan numbers
- Example 2.7 · Things counted by Catalan numbers
- Check 2.8 · Check: generating-function calculations
3 · Graphs12 concepts
- Overview 3 · The plan of this section
- Definition 3.1 · Graphs and degrees
- Proposition 3.2 · The handshake lemma
- Definition 3.3 · Walks, paths, cycles and connectivity
- Proposition 3.4 · Bipartite graphs have no odd cycles
- Definition 3.5 · Trees and forests
- Theorem 3.6 · Characterisations of trees
- Corollary 3.7 · Spanning trees
- Theorem 3.8 · Cayley's formula
- Theorem 3.9 · Euler's theorem
- Theorem 3.10 · Dirac's theorem
- Check 3.11 · Check: basic graph arguments
4 · Colouring and planarity11 concepts
- Overview 4 · The plan of this section
- Definition 4.1 · Colourings and chromatic number
- Proposition 4.2 · The greedy colouring bound
- Definition 4.3 · Planar graphs and faces
- Theorem 4.4 · Euler's formula
- Corollary 4.5 · Edge bounds for planar graphs
- Example 4.6 · K₅ and K₃,₃ are not planar
- Theorem 4.7 · Kuratowski's theorem
- Corollary 4.8 · Planar graphs have a vertex of degree at most 5
- Theorem 4.9 · The five colour theorem
- Check 4.10 · Check: planarity and colouring
5 · Matchings and Ramsey theory10 concepts
- Overview 5 · The plan of this section
- Definition 5.1 · Matchings
- Theorem 5.2 · Hall's marriage theorem
- Corollary 5.3 · Regular bipartite graphs have perfect matchings
- Theorem 5.4 · Kőnig's theorem
- Definition 5.5 · Ramsey numbers
- Example 5.6 · R(3, 3) = 6
- Theorem 5.7 · Ramsey numbers exist (Erdős–Szekeres bound)
- Theorem 5.8 · Erdős's probabilistic lower bound
- Check 5.9 · Check: matching and Ramsey arguments
Try it: a free card from this module
This is exactly what studying looks like inside UniMaths.
Proposition 1.1 · Binomial identities by double counting
Symmetry, committee–chair, , alternating sum , hockey stick — all by double counting.
Proof
Learn all 52 concepts like this
Cards, step-by-step proofs, and 115 questions scheduled so you review right before you forget.