This section will be about some math preliminaries that you will be using throughout the course. You can get the notes for these videos here.

Set Theory

Definitions and properties

Sets will be everywhere in this course. I introduce basic notions related to sets such as their definition as well as some of their properties.

Set operations

Now that you know what sets are, I introduce operations that you can use on sets such as the union, intersection and set difference. Exercises at the end of the video for you to practice!

Graph Theory

Along with sets, graphs will be another fundamental mathematical object you’ll be seeing throughout this course. I review some definitions of sets and talk about the different ways of “walking” and “cycling” through graphs.

(Some) Proof Techniques

Finally, proofs will be another big part of the material in this course. I provide a review of some fundamental proof techniques.

Proving that two sets are equal

How do you prove that two sets are equal? I discuss this and provide an example to make things a little more concrete.

The Pigeonhole Principle

The Pigeonhole Principle (PHP) is a simple yet powerful concept that you will find in multiple proofs for this course. I discuss the principle and how it can used to prove a property about simple graphs.

Using the PHP to prove a statement about graphs

Proof by contradiction

If you took any type of discrete math class, you used this technique to prove that \(\sqrt{2}\) is irrational! I discuss the general idea of proving something by contradiction and then provide a proof by contradiction for a statement on graphs.

Proof by induction

Used to prove statements on integers (among other things), the proof by induction is a powerful proof technique that I review with another graph theory proof.

The Principle of Mathematical Induction

Using induction to prove a statement about trees

Proof by construction

Last but not least, the proof by construction, in which you construct a mathematical object to prove its existence, is the one that you will be seeing the most in this course.

Exercises

Exercise. Let \(T=(V, E)\) be a tree with \(|V| \geq 2\), show that \(T\) must have at least 2 vertices with degree 1. I used this fact in the proof by induction video. In fact, I used a weaker statement that said that there must be at least 1 vertex of degree 1.