Appendix C List of Results
Section 1.1 Sets and Functions
Definition 1.1.1 Set Inclusion and Equality
Definition 1.1.4 Function
Definition 1.1.5 Injective, surjective, bijective
Definition 1.1.7 Composition
Theorem 1.1.8 Properties of Compositions
Definition 1.1.10 Cardinality Relations
Definition 1.1.12 Power Set
Section 1.2 Logic and Proof Techniques
Theorem 1.2.1 Principle of Mathematical Induction
Section 1.3 Integers and Divisibility
Definition 1.3.1 Divisibility and Primes
Theorem 1.3.2 Division Algorithm
Definition 1.3.4 GCD
Theorem 1.3.7 Bezout's Identity
Lemma 1.3.11 Euclid's Lemma
Section 2.1 The Basic Counting Principles
Definition 2.1.6 Partition
Definition 2.1.14 Factorial
Section 2.2 Permutations and Combinations
Definition 2.2.1 Permutation
Proposition 2.2.5 \(k\)-permutation of an \(n\)-set
Proposition 2.2.10 Permutations of a multiset
Definition 2.2.15 Combination
Proposition 2.2.16 \(k\)-combinations of an \(n\)-set
Section 2.3 Binomial Coefficients
Definition 2.3.1 Binomial Coefficient
Theorem 2.3.2 Pascal's Formula
Theorem 2.3.5 Binomial Theorem
Section 2.4 The Balls in Bins Formula
Proposition 2.4.2 Permutations with repetition
Theorem 2.4.5 Balls in Bins
Proposition 2.4.8 Nonnegative integer solutions
Section 2.5 Combinatorial Arguments
Theorem 2.5.2 Chairperson Identity
Section 3.1 The Pigeonhole Principle
Theorem 3.1.3 Pigeonhole Principle (PHP)
Corollary 3.1.5 Pigeonhole Principle with \(k=1\)
Section 3.2 Principle of Inclusion-Exclusion
Theorem 3.2.6 Principle of Inclusion-Exclusion
Section 3.3 Application: Derangements
Definition 3.3.1 Derangement
Theorem 3.3.3 Number \(D_n\) of Derangements
Section 4.1 Equivalence Relations
Definition 4.1.1 Relation
Definition 4.1.5 Equivalence Relation
Definition 4.1.7 Equivalence Class
Lemma 4.1.9 Equivalent Objects are in the Same Class
Theorem 4.1.10 Equivalence Relations induce Partitions
Section 4.2 Congruences and their Properties
Definition 4.2.1 Congruence
Definition 4.2.6 Congruence Class
Proposition 4.2.8 Modular Arithmetic
Definition 4.2.12 The Modulo Operation
Proposition 4.2.15 Dividing both sides of a Congruence
Section 4.3 Solving Congruences
Definition 4.3.5 Multiplicative Inverse
Definition 4.3.8 Unit Modulo \(n\)
Section 4.4 Euler's Theorem
Definition 4.4.1 Euler's Totient Function
Proposition 4.4.5 \(\phi(p)\)
Theorem 4.4.9 Euler's Theorem
Theorem 4.4.10 Fermat's Little Theorem (FLT)
Section 4.5 The Chinese Remainder Theorem
Theorem 4.5.2 Solution to a system of two congruences
Theorem 4.5.6 Solution to a general system of congruences
Section 5.2 Basic Definitions
Definition 5.2.1 Graph
Definition 5.2.2 Simple Graphs and Multigraphs
Definition 5.2.6 Degree of a vertex
Theorem 5.2.10 Degree-Sum Formula
Lemma 5.2.15 Handshake Lemma
Section 5.3 Eulerian Graphs
Definition 5.3.1 Trail
Definition 5.3.3 Eulerian Graph
Definition 5.3.5 Path
Definition 5.3.6 Connectedness
Theorem 5.3.8 When is a Graph Eulerian?
Definition 5.3.12 Cycle
Definition 5.3.13 Complete Graph
Section 5.4 Isomorphisms and Subgraphs
Definition 5.4.2 Graph Equality
Definition 5.4.3 Graph Isomorphism
Proposition 5.4.6 Isomorphic Graphs have the Same Number of Edges
Definition 5.4.10 Subgraph
Definition 5.4.15 Graph Complement
Proposition 5.4.17 Complements are Isomorphic
Section 5.5 Connectedness and Trees
Definition 5.5.1 Path Graph
Definition 5.5.3 Connected Component
Definition 5.5.8 Tree, Forest
Proposition 5.5.11 Tree Minus an Edge is Disconnected
Definition 5.5.12 Leaf
Lemma 5.5.13 A Tree must have at least Two Leaves
Theorem 5.5.18 Trees have \(|V|-1\) Edges
Theorem 5.5.19 Converse of Theorem 5.5.18
Theorem 5.5.20 Characterization of Trees
Section 5.6 Bipartite Graphs
Definition 5.6.1 Bipartite Graph
Theorem 5.6.5 Characterization of Bipartite Graphs
Definition 5.6.8 Complete Bipartite Graph
Section 5.7 Hamiltonian Graphs
Definition 5.7.1 Hamiltonian Cycle; Graph
Theorem 5.7.7 Sufficient Condition for Hamiltonicity (Dirac)
Section A.2 Reading Mathematics
Proposition A.2.5 Inverse of Strictly Increasing is Strictly Increasing