2B SE

MATH 239: Introduction to Combinatorics

Course that teaches counting and graph theory.

Link to course notes here.

Resources:

• Some nice notes https://www.richardwu.ca/notes/math239-final-notes.pdf by Richard Wu

Chapter 1: Enumeration

• Generating Series
• Sum Lemma, Product Lemma, String Lemma
• Regular Expression
• Combinatorial Proof Chapter 2: Graph Theory
• Handshaking Lemma
• Hamiltonian Cycle
• Bipartite Graph
• Hypercube Graph
• Connectedness
• Graph Cut
• Eulerian Circuit
• Tree
  • Spanning Tree
• Planar Graph
  • Euler’s Formula
  • Kuratowski’s Theorem
• Graph Colouring
• Graph Matching
  • Alternating Path and Augmenting Path
  • Bipartite Matching Algorithm
  • Konig’s Theorem
  • Hall’s Theorem

Tip for final

I believe the key to mastering this final is being able to problem solve SUPER quickly. I struggled with the midterm for that. This is why you need to do lots of problems and just time yourself. Know the different theorems like the back of your hand, and when to use them. Build strong Intuition.

Get good at induction. It seems that a lot of the proof require the use of induction.

Template for strong induction

• Inductive Hypothesis: Assume that $X$ holds for any tree/graph with less than $m$ edges.
• Base Case: When $m=0$, …, so the result holds
• Inductive Step: …