MATH 239: Introduction to Combinatorics §

Combinatorial proof: To show A and B refer to the same set, show $A=S=B$

• Basically, show that they show the same set

Links:

• 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 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

Final Preparation

Things that i need to work on:

• Bijection proof, revisit tutorial 8-4
• Product lemma, string lemma, and sum lemma. When do you use these in proofs?
• Overlap case…?

Other things to practice:

• Hall’s theorem

Tip

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.

Final: I need to go through

• all the assignments again,
• as well as the practice final,
• as well as other sample finals
• as well as the tutorials

And then you should be good to go.

• Practice doing the Bipartite Matching Algorithm
• Practice applying Kuratowski Theorem
  • I think I got it, but gotta do a few more. I always just use $K_{3,3}$
• Really master all of the theorems

Practice Proofs:

• Prove that “Every tree is bipartite” (use 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: …