# Math Preliminaries

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.