Theorems and Proofs

Theorem 1

• Theorem: If $A ⊆ B$ and $B ⊆ C$, then $A ⊆ C$, where A, B, and C are sets.

• Proof:

  • Assumptions:

    • A, B, C are sets.

    • $A ⊆ B$ and $B ⊆ C$

  • Goal: Show that $A ⊆ C$, i.e., if $x ∈ A$ , then $x ∈ C$.

  • Proof Steps:

    • Since $A ⊆ B$, for all $x ∈ A$, then $x ∈ B$. So, $x ∈ B$.

    • Since $B ⊆ C$, for all $x ∈ B$, then $x ∈ C$. So, $x ∈ C$.

    • Thus, for all $x ∈ A$, we can say $x ∈ C$.

    • Therefore, we can state that $A ⊆ C$.

Theorem 2

• Some theorems with set operations, given sets A and B:

  1. $A ∪ B = B ∪ A$

  2. If $A ⊆ B$, then $A ∪ B = B$

     • $A ∪ A = A$

     • $∅ ∪ A = A$

  3. $A ∩ B = B ∩ A$

  4. If $A ⊆ B$, then $A ∩ B = A$

     • $A ∩ A = A$

     • $A ∩ ∅ = ∅$

  5. $(A ∩ B) ⊆ A$, $(A ∩ B) ⊆ B$

  6. $A ⊆ (A ∪ B)$, $B ⊆ (A ∪ B)$

Theorem 3

• Some laws with set operations:

  • Associative laws

    • $(A ∩ B) ∩ C = A ∩ (B ∩ C)$

    • $(A ∪ B) ∪ C = A ∪ (B ∪ C)$

  • Commutative laws

    • $A ∩ B = B ∩ A$

    • $A ∪ B = B ∪ A$

  • Identity laws

    • $A ∩ A = A$

    • $A ∪ ∅ = A$

  • Complement laws

    • $A ∩ A = ∅$

    • $A ∪ A = U$

Theorem 4

• Let S be a partition of X. Define a binary relation E on X. So we have the statement
  $x E y ⇐⇒ x, y ∈ A$ for some $A ∈ S$, then E is an equivalence relation.

Theorem 5

• E is an equivalence relation on X. The family of equivalence classes forms a partition.

• In other words, $S = {C | C = [x]_E}$ for some $x ∈ X$

Theorem 6

• Let $n ∈ Z^+$, then binary relation $E<em>n$ on Z defined by $x E</em>n y ⇐⇒ x \mod n ≡ y$. Show this is an equivalence relation.

Theorem 7

• Recall $P(X) = {S | S ⊆ X }$ is known as the power set of X.

• Let X be a finite set, with cardinality $|X| = n$. The cardinality of the power set is given by, $|P(x)| = 2^n$

Theorem 8

• Inclusion-Exclusion principle: If X and Y are finite sets, then
  $|X ∪ Y | = |X| + |Y | − |X ∩ Y |$

Theorem 9

• Let X and Y be finite sets.

• $|X| = |Y |$ if there is a bijection $f : X → Y$

Theorem 10

• $P(n, r) = \frac{n!}{(n − r)!}$

Theorem 11

• For $r ≤ n$, $\binom{n}{r} = \frac{n!}{(n − r)!r!}$

Theorem 12

• For any integer n, k with $k ≤ n$, $\binom{n + 1}{k} = \binom{n}{k − 1} + \binom{n}{k}$

Theorem 13

• If there are n pigeons and k pigeonholes, n > k, then at least one pigeon hole has more than 1 pigeon.

Theorem 14

• Pigeonhole Principle (formal): Let X and Y be finite sets. If |X| > |Y |, then there is no injective function $f : X → Y$.

Theorem 15

• Generalized Pigeonhole Principle: X and Y are finite sets. $|X| = n, |Y | = m$, and $k = \lceil \frac{n}{m} \rceil$

• For any function $f : X → Y$, there are at least K distinct elements of $x<em>1, …, x</em>k ∈ X$ such that $f(x<em>1) = f(x</em>2) = … = f(x_k)$, that all map to the same element.

Theorem 16

• Let $a<em>n = c</em>1 a<em>{n−1} + c</em>2 a<em>{n−2}$ with initial conditions $a</em>1 = K<em>1$ and $a</em>2 = K_2$.

• If the polynomial $t^2 − c<em>1 t − c</em>2 = 0$ has distinct roots, $r<em>1 \neq r</em>2$, then d, b exist such that
  $b + d = k<em>1$ $b r</em>1 + d r<em>2 = k</em>2$

• And we get the closed form solution for $a<em>n$ $a</em>n = b r<em>1^n + d r</em>2^n$

Theorem 17

• Let $\begin{Bmatrix} b<em>n \end{Bmatrix}</em>{n=0}^\infty$ be a particular solution to $a<em>n = c</em>1 a<em>{n−1} + c</em>2 a_{n−2} + f(n)$.

• Any solution is of the form $\begin{Bmatrix} u<em>n \end{Bmatrix}$, $u</em>n = v<em>n + b</em>n$ where $v<em>n$ is a solution to the homogeneous component, $a</em>n = c<em>1 a</em>{n−1} + c<em>2 a</em>{n−2}$.

• $u<em>n$ is called the general solution of $a</em>n$.

Theorem 18

• A finite graph, G, has an Eulerian cycle iff G is connected and every vertex has even degree.

Theorem 19

• Given graph G(V, E) is a finite graph, with $V = {v<em>1, …, v</em>n}$

• $\sum<em>{i=1}^n δ(v</em>i) = 2m$ for some $m ∈ Z^{≥0}$.

• Restating, the sum of the degrees of all the vertices are even.

Theorem 20

• Let G(V, E) be a finite graph. Define two vertices $v, w ∈ V$.

• G has a path from v to w with no repeated edges, and visits all vertices/edges iff G is connected and v and w are the only edges with odd degree.

Theorem 21

• Graph G(V, U), and v is a vertex in V.

• If G as a cycle from V to V, then G has a simple cycle from V to V.

Theorem 22

• Let G be a graph and A is an adjacency matrix.

• For an integer $n ≥ 1$ the ijth entry of $A^n$ is equal to the number of paths from i to j with length n.

Theorem 23

• Define $G = (V, E)$ and $G′ = (V ′, E′)$.

• G and G′ are isomorphic iff there are ordering of their respective vertex sets st their adjacency matrices are the same.

Theorem 24

• Let G and G′ be graphs.

• If there is an invariance P st G has property P but G′ does not have property P, then G and G′ are not isomorphic.

Theorem 25

• Fix an integer $k ≥ 1$.

• Property of “having a simple cycle of length k” is invariant.

Theorem 26

• Euler's formula for graphs: G be a connected planar graph with e edges, v vertices, and f faces.

• $f = e − v + 2$

Theorem 27

• A graph is planar iff G does not have a subgraph that is homeomorphic to $K<em>5$ or $K</em>{33}$.

Theorem 28

• Let G be a graph. x, y are connected.

• The path denoted with d(x, y), is the path from x to y, that does not visit any vertex more than once.

Theorem 29

• Let G be a graph. The following are equivalent.

  1. G is 2-colorable.

  2. G is a bipartite graph.

  3. G has no cycles of odd length.

Theorem 30

• Four color theorem: every planar graph is 4-colorable.

Theorem 31

• For any n, “$χ(G) = n$” is invariant.

Theorem 32

• G is a finite graph with n-vertices.

• $n \alpha(G) ≤ χ(G)$

• Where $α(G)$ is the independence number and $χ(G)$ is the chromatic number.

Theorem 33

• Every tree is connected and acyclic.

Theorem 34

• Every tree with at least 2 vertices has a vertex of degree 1.

• $δ(v_i) = 1$ for some i.

Theorem 35

• Every tree is bipartite (hence 2-colorable).

Theorem 36

• Let T = (V, E) be a finite graph with $|V | = n$. The following are equivalent.

  1. T is a tree.

  2. T is connected and acyclic.

  3. T is connected and $|E| = n − 1$.

  4. T is acyclic and $|E| = n − 1$.

Theorem 37

• If T is a full binary tree, i internal vertices, then T has i + 1 leaves and 2i + 1 total vertices.

Theorem 38

• If a binary tree T has height of h with t leaves.

• $t ≤ 2^h$

• $\log_2 t ≤ h$

Theorem 39

• There are exactly 3 non-isomorphic trees with 5 vertices.

Theorem 40

• There are exactly 4 rooted trees with 4 vertices.

Theorem 41

• If T and T′ are not tree isomorphic, they are not rooted tree isomorphic.

Theorem 42

• A graph G has a spanning tree iff it is connected.