Skip to main content
Logo image

Index Index

additive principle, Section Summary
using sets, Summary
adjacent
edges, Item
vertices, Paragraph Item
alternating path, Exercise
ancestor (in a rooted tree), Paragraph
and (logical connective), Item
truth condition for, Item
antecedent. See hypothesis
argument, Summary
arithmetic sequence, Summary
summing, Subsubsection
atomic statement, Paragraph
augmenting path, Exercise
balls and bins. See stars and bars
base case, Paragraph Item Item
biconditional, Item Summary
counting, Example
binary connective, Paragraph
binary digit. See bit
binary predicate, Exercise
binary representation, Exercise
binomial coefficient, Subsection Paragraph Paragraph Summary
closed formula for, Summary
objects counted by, Summary
recurrence relation for, Summary
binomial identity, Paragraph
examples of, Paragraph
bipartite graph, Paragraph Item
bit, Paragraph
as code for a subset, Paragraph
combinatorial proof involving, Exercise
correspondence with lattice path, Paragraph
relation to stars and bars, Paragraph
Boolean variable. See propositional variable
breadth first search, Paragraph
Brooks’ Theorem, Theorem
Canadians, set of, Paragraphs
cannonball stacking, Exercise
cardinality, Paragraph
of a set, Item
of a union, Summary Summary Summary
of Cartesian product, Summary
of power set, Exercise
Cartesian product, Item Paragraph Summary
cardinality of, Summary
cases, Subsection
characteristic equation, Paragraph Summary
characteristic polynomial, Summary
characteristic roots, Subsection Summary Paragraph
repeated, Summary
chessboard
counting squares on, Paragraph
missing squares, Exercise Exercise
rook paths, Investigate!
tiling, Exercise
child (in a rooted tree), Paragraph
chordal graph, Paragraph
Christmas, Exercise
chromatic index, Paragraph
chromatic number, Item Paragraph
circuit, Paragraph Summary
Euler, Section
clique, Paragraph
closed formula, Summary
for a function, Paragraph
for a sequence, Summary
for arithmetic sequence, Summary
for geometric sequence, Summary
codomain, Paragraph Item
coloring
edges, Subsection
vertices, Paragraph
vertices vs edges, Exercise
combination, Section
closed formula for, Summary
combinatorial proof, Section Paragraph
common difference, Summary
common ratio, Summary
complement of a set, Item Paragraph
complete bipartite graph, Paragraph Paragraphs Item
complete graph, Paragraph Paragraphs Item
complete inverse image, Paragraph Item
complex numbers (as characteristic roots), Paragraph
composition of functions, Exercise
conclusion, Summary Summary
conditional, Item Summary
congruence, Summary
arithmetic, Summary
divisibility, Summary
division, Summary
equality, Summary
equivalence relation, Summary
solving, Subsection
without solutions, Summary
conjunction, Item
connected graph, Paragraph Item
connectives, Paragraph Summary
consequent. See conclusion
contradiction, Subsection
contrapositive, Item
proof by, Subsection
converse, Item
convex polyhedron, Paragraph
counterexample, Subsection
counting, Chapter
divisors, Exercise
edges in a graph, Lemma
functions, Example
cover (vertex), Exercise
cycle, Item Item
Hamilton, Section Paragraph
type of graph, Paragraphs
De Morgan’s laws, Summary
deduction rule, Paragraph
degree, Paragraph Item
degree sequence, Paragraph
maximum, Paragraph
sum formula, Lemma
\(\Delta^k\)-constant, Paragraph Summary
depth first search, Paragraph
derangement, Paragraph
fraction of all permutations that are, Exercise
descendant (in a rooted tree), Paragraph
difference equation. See recurrence relation
difference of sets, Item Paragraph
differences of a sequence, Paragraph
differentiable functions
generalized product rule, Exercise
generalized sum rule, Exercise
Diophantine equation, Subsection Paragraph Summary
solution, Summary
direct proof, Subsection
for implication, Summary
disjoint events, Paragraph
disjunction, Item
equivalent implication, Summary
distribution (counting), Section Example
with upper bound restriction, Paragraph
divides, Paragraph Summary
divisibility, Summary
divisibility relation, Subsection Summary
division algorithm, Paragraph Summary
division with remainder. See division algorithm
Doctor Who, Paragraph Exercise
dodecahedron, Subsection
domain, Paragraph Item
domain of discourse. See universe set
double induction. See induction, double
double negation, Summary
element of a set, Paragraph
empty set, Item
enumeration. See counting
equality of graphs, Example
equivalence relation, Paragraph Summary
Euclidean algorithm, Paragraph
Euler circuit, Item Section Paragraph Summary
Euler’s formula for planar graphs, Summary
exclusive or, Paragraph
existential quantifier, Summary
face (planar graph), Investigate! Paragraph
factorial, Paragraph
Fibonacci sequence, Example Summary Exercise
differences, Item
identity, Exercise
recurrence relation, Paragraph Paragraph
finite differences, Summary
football (American), Exercise
for all (quantifier), Summary
forest, Item Summary
Four Color Theorem, Theorem
free variable, Paragraph
function, Paragraph Item
how to describe, Subsection
increasing
counting, Exercise
non-decreasing
counting, Exercise
notation, Item
two-line notation, Paragraph Item
gcd. See greatest common divisor
generating function, Section
differencing, Subsection
multiplication and partial sums, Subsection
recurrence relation, Subsection
geometric sequence, Summary
summing, Subsubsection
girth, Paragraph
Goldbach conjecture, Paragraph
golden ratio, Paragraph
adjacent, Paragraph Item
bipartite, Paragraph Item
chordal, Paragraph
chromatic index, Paragraph
chromatic number, Item Paragraph Theorem
clique, Paragraph
coloring vertices vs edges, Exercise
complete bipartite, Paragraphs Item
connected, Paragraph Item
degree, Paragraph Item
degree sequence, Paragraph
drawing, Paragraph
equal vs isomorphic, Example
equality, Example
Euler circuit, Item
Euler path, Item
forest, Item
girth, Paragraph
induced subgraph, Item
isomorphic (intuitive definition), Paragraph
isomorphic (precise definition), Summary
isomorphism class, Paragraph
leaf, Item
maximum degree, Paragraph
multigraph, Paragraph Item
Petersen, Exercise
planar, Item
simple, Paragraph
subgraph, Summary Item
trail, Item
tree, Item
vertex coloring, Item Paragraph
walk, Item
graph (of a function), Paragraph
greatest common divisor, Paragraph
Hall’s Marriage Theorem, Theorem
Hamilton cycle, Section Paragraph
in bipartite graph, Exercise
Hamilton path, Section Paragraph
in bipartite graph, Exercise
handshake lemma, Lemma
handshakes, Exercise
connection to graphs, Exercise
Hanoi, Investigate!
hat check problem, Example
hockey stick theorem, Exercise
homogeneous
recurrence relation, Paragraph
houses and utilities puzzle, Example
hypothesis, Summary
icosahedron, Subsection
if and only if (logical connective), Item Summary
truth condition for, Item
iff. See if and only if
if…, then… (logical connective), Item
truth condition for, Item
image, Subsection
of a set, Paragraph
of a subset, Item
of an element, Paragraph Item Item
implication, Item Summary
direct proof for, Summary
equivalent disjunction, Summary
implicit quantifier, Paragraphs
implies (logical connective), Item
truth condition for, Item
inclusion/exclusion. See principle of inclusion/exclusion
inclusive or, Paragraph
induced subgraph, Summary Item
base case, Paragraph Item
for strong induction, Item
contrasting regular and strong, Paragraph Paragraph
double, Exercise
incorrect use of, Paragraphs
inductive case, Paragraph Item
for strong induction, Item
proof structure, Summary
inductive case, Paragraph Item Item
inductive hypothesis, Item Paragraph
strong, Paragraph
initial condition, Summary
for a function, Summary
counting, Example Paragraph
integer lattice, Paragraph
integer solutions to equation (counting), Example
integers, set of, Item Item
interior angles, Exercise
intersection of sets, Item Paragraph
inverse image, Subsection Paragraph Item
comparison to inverse function, Paragraph
of a subset, Item
isomorphic
intuitive definition, Paragraph
precise definition, Summary
isomorphism class, Paragraph
isomorphism of graphs, Summary
iteration, Paragraph Paragraph
\(k\)-permutation of \(n\) elements, Summary Paragraph
\(K_n\), Paragraph
knights and knaves, Investigate! Investigate! Exercise
Kruskal’s algorithm, Paragraph
Königsberg, Seven Bridges of, Investigate! Paragraph
lattice path, Paragraph
correspondence with bit string, Paragraph
length of, Paragraph
lattice, integer. See integer lattice
law of logic, Example
length of a bit string, Paragraph Summary
linear Diophantine equation. See Diophantine equation
logical connectives, Paragraph Summary
logical equivalence, Summary
logically valid. See law of logic
magic chocolate bunnies, Exercise
marriage problem. See matching
matching, Section Paragraph
partial, Exercise
matching condition, Summary Theorem
mathematical induction. See induction; induction
maximum degree, Paragraph
minimum spanning tree, Paragraph
mod, Paragraph
modular arithmetic, Summary
modulo \(n\), Summary
modus ponens, Paragraph
molecular statement, Paragraph
monochromatic, Paragraphs
multigraph, Paragraph Item
multiplicative principle, Section Summary
using sets, Summary
multiset
counting, Exercise
relation to multigraph, Paragraph
\(n\) choose \(k\). See binomial coefficient
natural numbers, set of, Item
necessary condition, Summary
negation, Item
interaction with quantifiers, Summary
neighbors of vertices, Exercise Paragraph Theorem
neighbors of verties, Summary
non-planar graph, Subsection
\(K_{3,3}\), Theorem
\(K_5\), Theorem
Petersen graph, Exercise
not (logical connective), Item
truth condition for, Item
NP-complete, Paragraph
number theory, Section
octahedron, Subsection
one-to-one function. See injection
onto function. See surjection
operations on sets, Subsection
or (logical connective), Item
inclusive vs exclusive, Paragraph
truth condition for, Item
parent (in a rooted tree), Paragraph
partial matching, Exercise
partial sums. See sequence of partial sums
partition, Paragraph
Pascal’s triangle, Subsection Paragraph Item Item
patterns in, Subsection
sum of row in, Exercise
path, Item Item
alternating, Exercise
augmenting, Exercise
Hamilton, Section Paragraph
type of graph, Paragraphs
perfect graph, Paragraph Exercise
perfect matching. See matching
permutation, Paragraph Section Summary
of \(k\) elements chosen from \(n\) (see \(k\)-permutation of \(n\) elements)
of \(n\) elements, Summary
to count functions, Example
to count words, Example
Petersen graph, Exercise
PIE. See principle of inclusion/exclusion
pigeonhole principle, Example
planar graph, Item Investigate! Paragraph
chromatic number of, Theorem
non-planar graph, Subsection
\(K_{3,3}\), Theorem
\(K_5\), Theorem
Petersen graph, Exercise
planar region. See face (planar graph)
planar representation, Paragraph
Platonic solid. See regular polyhedron
playing cards, Exercise
polyhedron, Paragraph Paragraph
regular, Investigate!
polynomial fitting, Section
power set, Item Item Paragraph
cardinality of, Exercise
powers of 2, Summary Example
predicate, Paragraph
binary, Exercise
premises, Summary
Prim’s algorithm, Paragraph
principle of inclusion/exclusion, Section Subsection
for 2 sets, Summary
for 3 sets, Summary
for 4 or more sets, Paragraph
product notation, Paragraphs Exercise Exercise
product principle. See multiplicative principle
proof
by cases, Subsection
by contradiction, Subsection
by contrapositive, Subsection
by indcution, Section Summary
combinatorial, Section Paragraph
proper vertex coloring, Item
proposition, Paragraph
propositional variable, Paragraph
puzzle, Exercise
cardinality, Exercise
chocolate bar, Quotation
domino path, Exercise
houses and utilities, Example
knights and knaves, Investigate! Investigate!
seven bridges, Investigate!
square division, Exercise
Tower of Hanoi, Investigate!
Pythagorean theorem, Paragraph
Pythagorean triple, Paragraph
quantifier, Summary
for all, Summary
implicit, Paragraphs
interaction with negation, Summary
there exists, Summary
racetrack principle, Paragraph
Ramsey theory, Paragraphs
range of a function, Paragraph Item
rational numbers, set of, Item
real numbers, set of, Item
recurrence relation, Summary
finding for sequence, Example
for a function, Summary
for binomial coefficient, Summary
for number of bit strings, Paragraph
for number of lattice paths, Paragraph
generating function, Subsection
verifying solution to, Example
recursive definition, Summary
for arithmetic sequence, Summary
for geometric sequence, Summary
recursively defined function, Summary
reference, self. See self reference
region (graph). See face (planar graph)
regular polyhedron, Investigate!
remainder class, Subsection
residue class. See remainder class
rook paths, Investigate!
root (in a tree), Paragraph
rooted tree, Paragraph Subsection
rule of four, Paragraph
search
breadth first, Paragraph
depth first, Paragraph
self reference. See reference, self
sentence (compared to statement), Paragraph
sentential variable. See propositional variable
sequence, Paragraph
as function, Paragraph
closed formula for, Summary Example
inductive definition for, Summary
notation for, Paragraph
recursive definition for, Summary Example
sequence of partial sums, Paragraphs Example Exercise Exercise
for Fibonacci sequence, Item
for triangular numbers, Paragraph
set, Paragraph
cardinality, Item
complement, Item
difference, Item Paragraph
intersection, Item
notation for, Subsection
of all subsets (see power set)
of integers, Item Item
of natural numbers, Item
of rational numbers, Item
of real numbers, Item
operations, Subsection
product (see Cartesian product)
relationships between, Subsection
union, Item
Venn diagram, Subsection
set builder notation, Paragraph
Seven Bridges of Königsberg, Investigate! Paragraph
sibling (in a rooted tree), Paragraph
Sigma notation, Example Paragraphs
simple graph, Paragraph
six color theorem, Exercise
size of a set
see cardinality, Item
solitary number, Exercise
spanning tree, Subsection Summary
minimum, Paragraph
square numbers, Summary
stars and bars, Section
chart, Paragraph
vs combination, Item
statement, Paragraph
sticks and stones. See stars and bars
string
binary (see bit string)
ternary, Exercise Exercise
strong induction. See induction, strong
subgraph, Summary Item
counting, Subsection
encoding as bit string, Paragraph
sufficient condition, Summary
sum principle. See additive principle
summation notation, Example Paragraphs Exercise Exercise
tautology, Paragraph
telescoping, Paragraph
ternary string, Exercise Exercise
tetrahedron, Subsection
there exists (quantifier), Summary
tour, Euler. See Euler circuit
Tower of Hanoi, Investigate! Paragraph
trail, Item
Euler (see Euler path)
transitive sets, Exercise
tree, Item Summary
number of edges and vertices, Proposition
spanning, Subsection Summary
triangular numbers, Summary Example Paragraph Example
truth condition, Summary
for and, Item
for if and only if, Item
for if…, then…, Item
for not, Item
for or, Item
truth table, Subsection
truth value, Paragraph Paragraph
The Twelve Days of Christmas, Exercise
two-line notation, Paragraph Item
unary connective, Paragraph
union of sets, Item Paragraph
cardinality of, Summary
universal quantifier, Summary
universe set, Item Paragraph
valid, Summary
variable, propositional, Paragraph
Venn diagram, Subsection Paragraph
for counting, Paragraph
intersection, Paragraph
set difference, Paragraph
vertex coloring, Item Paragraph
vertex cover, Exercise
vertex degree, Paragraph Item
degree sequence, Paragraph
Vizing’s Theorem, Theorem
Euler (see Euler path)
weight (bit string), Item
weight of a bit string, Paragraph Summary
word (counting), Example Example
zombies, Exercise