Index Index
additive principle. See sum principle
adjacent
edges, Item
alternating path, Exercise
ancestor (in a rooted tree), Paragraph
and (logical connective), Item
truth condition for, Item
antecedent. See hypothesis
antisymmetric, Paragraph
arbitrary, Paragraph
argument, Definition Definition
arithmetic sequence, Summary
summing, Subsection
atomic statement, Paragraph
augmenting path, Exercise
balls and bins. See sticks and stones
biconditional, Item
bijection, Subsection Paragraph Item
counting, Example
binary connective, Paragraph
binary digit. See bit
binary predicate, Exercise
binary relation, Paragraph
binary representation, Exercise
binomial coefficient, Subsection Paragraph Paragraph
closed formula for, Theorem
binomial identity, Paragraph
examples of, Paragraph
binomial theorem, Theorem
birthday paradox, Worksheet
bit, Paragraph
bit string, Subsection Paragraph Definition Exercise
combinatorial proof involving, Exercise
length, Paragraph Definition
weight, Paragraph Definition
Boolean variable. See propositional variable
breadth-first search, Paragraph
Brooks’ theorem, Theorem
Canadians, set of, Paragraphs
cannonball stacking, Exercise
of a set, Item
of power set, Exercise
cards, Investigate!
characteristic polynomial, Summary
characteristic roots, Subsection Summary Paragraph
repeated, Summary
chessboard
counting squares on, Paragraph
rook paths, Investigate!
tiling, Exercise
child (in a rooted tree), Paragraph
chordal graph, Paragraph
Christmas, Exercise
chromatic index, Paragraph
Euler, Section
clique, Paragraph
closed formula, Definition
for arithmetic sequence, Summary
for geometric sequence, Summary
coloring
edges, Subsection
vertices, Paragraph
vertices vs edges, Exercise
combination, Section
closed formula for, Theorem
common difference, Summary
common ratio, Summary
complement (of an event), Paragraph
complement, probability of, Theorem
complete bipartite graph, Paragraph Paragraphs Item
complete graph, Paragraph Paragraphs Item
complex numbers (as characteristic roots), Paragraph
composition of functions, Exercise
conclusion, Definition Definition Definition
conditional, Item Definition
conditional probability, Subsection Definition
congruence, Summary
arithmetic, Summary
divisibility, Summary
division, Summary
equality, Summary
equivalence relation, Summary
solving, Subsection
without solutions, Summary
conjunction, Item
connectives, Paragraph Definition
consequent. See conclusion
contradiction, Subsection
contrapositive, Definition
proof by, Subsection
converse, Definition
convex polyhedron, Paragraph
cookie, Example
corollary, Paragraph
counting, Chapter
divisors, Exercise
edges in a graph, Lemma
functions, Example
cover (vertex), Exercise
cube, Investigate!
type of graph, Paragraphs
De Morgan’s laws, Theorem
deduction rule, Paragraph
degree sequence, Paragraph
maximum, Paragraph
sum formula, Lemma
depth-first search, Paragraph
derangement, Paragraph
fraction of all permutations that are, Exercise
descendant (in a rooted tree), Paragraph
design, 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
discrete structures. See structures
disjoint, Paragraph
disjoint events, Paragraph
disjunction, Item
equivalent implication, Summary
with upper bound restriction, Paragraph
divisibility, Summary
divisibility relation, Subsection Summary
division with remainder. See division algorithm
dodecahedron, Subsection
domain of discourse. Paragraph; universe set
domino, Investigate! Exercise Exercise
double induction. See induction, double
double negation, Summary
edge, Paragraph Paragraph Definition Item
element chasing, Paragraph
element of a set, Paragraph
enumeration. See counting
equality of graphs, Example
Euclidean algorithm, Paragraph
Euler’s formula for planar graphs, Summary
event (counting), Paragraph
event (probability), Paragraph
exclusive or, Paragraph
existential quantifier, Definition
exists, Definition
face (planar graph), Investigate! Paragraph
factorial, Paragraph
differences, Item
identity, Exercise
recurrence relation, Paragraph
finite differences, Theorem
finite geometry, Paragraph
finite sequence, Paragraph
for all, Definition
forest, Item Definition
four color theorem, Theorem
free variable, Paragraph
counting, Example Paragraphs Subsection Paragraph Paragraph
how to describe, Subsection
increasing
counting, Exercise
non-decreasing
counting, Exercise
notation, Item
gcd. See greatest common divisor
generating function, Section
differencing, Subsection
multiplication and partial sums, Subsection
recurrence relation, Subsection
geometric sequence, Summary
summing, Subsection
girth, Paragraph
Goldbach, Paragraph
Goldbach conjecture, Paragraph
golden ratio, Paragraph
graph, Subsection Paragraph Definition Item
chordal, Paragraph
chromatic index, Paragraph
clique, Paragraph
coloring vertices vs edges, Exercise
complete, Paragraph Paragraphs Item
complete bipartite, Paragraphs Item
cycle, Paragraphs Item Item
degree sequence, Paragraph
drawing, Paragraph
edge, Paragraph Definition
equal vs isomorphic, Example
equality, Example
Euler circuit, Item
Euler trail, Item
forest, Item
girth, Paragraph
induced subgraph, Item
isomorphic (intuitive definition), Paragraph
isomorphic (precise definition), Definition
isomorphism class, Paragraph
leaf, Item
maximum degree, Paragraph
path, Paragraphs Item Item
Petersen, Exercise
planar, Item
simple, Paragraph
subgraph, Definition Item
trail, Item
tree, Item
vertex, Paragraph Definition
walk, Item
graph (of a function), Paragraph
greatest common divisor, Paragraph
Hall’s Marriage theorem, Theorem
in bipartite graph, Exercise
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
hypothesis, Definition
icosahedron, Subsection
if and only if (logical connective), Item
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
implication, Item Definition
equivalent disjunction, Summary
implicit quantifier, Paragraphs
implies (logical connective), Item
truth condition for, Item
inclusion/exclusion. See principle of inclusion/exclusion
inclusive or, Paragraph
independence, Definition
induced subgraph, Definition Item
base case, Item
for strong induction, Item
contrasting regular and strong, Paragraph
double, Exercise
incorrect use of, Paragraphs
inductive case, Item
for strong induction, Item
proof structure, Summary
strong, Summary
initial condition, Definition
for a function, Summary
injection, Item Subsection Paragraph Item
integer lattice, Paragraph
integer solutions to equation (counting), Example
intersection, Paragraph
inverse, Definition
inverse image, Subsection Paragraph Item
comparison to inverse function, Paragraph
of a subset, Item
irreflexive, Paragraph
isomorphic
intuitive definition, Paragraph
precise definition, Definition
isomorphism class, Paragraph
isomorphism of graphs, Definition
\(K_n\), Paragraph
knights and knaves, Investigate! Exercise Exercise
Kruskal’s algorithm, Paragraph
Königsberg, Seven Bridges of, Investigate! Paragraph
lattice path, Paragraph
length of, Paragraph
lattice, integer. See integer lattice
law of logic, Example
length of a bit string, Paragraph Definition
linear Diophantine equation. See Diophantine equation
logical connectives, Paragraph Definition
logical equivalence, Definition
logically valid. See law of logic
magic chocolate bunnies, Exercise
main connective, Example
marriage problem. See matching
partial, Exercise
mathematical induction. See induction; induction
maximum degree, Paragraph
minimal criminal, Paragraph
minimum spanning tree, Paragraph
mod, Paragraph
modular arithmetic, Summary
modulo \(n\), Summary
modus ponens, Paragraph
molecular statement, Paragraph
monochromatic, Paragraphs
Monty Hall problem, Paragraph
multiplicative principle. See product principle
multiset, Paragraph
counting, Exercise
relation to multigraph, Paragraph
multisets (counting), Section
natural numbers, set of, Item
necessary condition, Definition
negation, Item
interaction with quantifiers, Summary
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
outcome (counting), Paragraph
outcome (probability), Paragraph
parent (in a rooted tree), Paragraph
partial matching, Exercise
partial sums. See sequence of partial sums
partition, Paragraph
patterns in, Subsection
sum of row in, Exercise
alternating, Exercise
augmenting, Exercise
Euler (see Euler trail)
type of graph, Paragraphs
perfect matching. See matching
permutation, Paragraph Section Definition
of \(k\) elements chosen from \(n\) (see \(k\)-permutation of \(n\) elements)
of \(n\) elements, Theorem
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 Investigate!
regular, Investigate!
cardinality of, Exercise
predicate, Paragraph
binary, Exercise
premise, Definition
premises, Definition
Prim’s algorithm, Paragraph
principle of inclusion/exclusion, Section Subsection
for 2 sets, Theorem
for 3 sets, Theorem
for 4 or more sets, Paragraph
probability, Definition
proof, Definition
by contradiction, Subsection
by contrapositive, Subsection
by strong indcution, Section
proper vertex coloring, Item
puzzle, Exercise
birthday, Worksheet
cardinality, Exercise
chocolate bar, Worksheet Exercise
domino trail, Exercise
knights and knaves, Investigate! Exercise
seven bridges, Investigate!
square division, Exercise
Tower of Hanoi, Investigate!
Pythagorean theorem, Paragraph
racetrack principle, Paragraph
Ramsey theory, Paragraphs
random experiment, Paragraph
rational numbers, set of, Item
real numbers, set of, Item
recurrence relation, Definition
finding for sequence, Example
for a function, Summary
for number of bit strings, Paragraph
generating function, Subsection
recursive definition, Definition
for a function, Paragraph
for a sequence, Paragraph
for arithmetic sequence, Summary
for geometric sequence, Summary
recursively defined function, Summary
reference, self. See self reference; self reference
reflexive, Paragraph
region (graph). See face (planar graph)
regular polyhedron, Investigate!
relation, Subsection
remainder class, Subsection
residue class. See remainder class
rook paths, Investigate!
root (in a tree), Paragraph
rooted tree, Paragraph Subsection
rule of four, Paragraph
sample space, Paragraph
scope (of quantifier), Example
scope of a quantifier, Example
search
breadth-first, Paragraph
depth-first, Paragraph
self reference. See reference, self; reference, self
sentence (compared to statement), Paragraph
sentential variable. See propositional variable
sequence, Subsection Paragraph
as function, Paragraph
closed formula for, Definition Example
inductive definition for, Definition
notation for, Paragraph
recursive definition for, Definition Example
for Fibonacci sequence, Item
for triangular numbers, Paragraph
sequence, finite, Paragraph
set, Subsection Paragraph
cardinality, Item
complement, Item
intersection, Item
notation for, Subsection
of all subsets (see power set)
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
simple graph, Paragraph
six color theorem, Exercise
size of a set
see cardinality, Item
solitary number, Exercise
sound, Definition
spanning tree, Subsection Definition
minimum, Paragraph
square numbers, Summary
stars and bars. See sticks and stones
statement, Definition Paragraph
sticks and stones, Section
vs combination, Item
string
binary (see bit string)
strong induction, Section
structures, Paragraph
subgraph, Definition Item
subset, Subsection Paragraph
counting, Subsection
sudoku, Investigate! Definition
sufficient condition, Definition
using sets, Principle
sum principle (probability), Theorem
surjection, Item Subsection Paragraph Item
symmetric, Paragraph
term (of a sequence), Paragraph
tetrahedron, Subsection
tour, Euler. See Euler circuit
Tower of Hanoi, Investigate! Paragraph
trail, Item
transitive, Paragraph
transitive sets, Exercise
tree, Item Definition
number of edges and vertices, Proposition
rooted, Paragraph Subsection
spanning, Subsection Definition
truth condition, Definition
for and, Item
for if and only if, Item
for if…, then…, Item
for not, Item
for or, Item
truth table, Paragraph Subsection
tuple. See sequence, finite
The Twelve Days of Christmas, Exercise
unary connective, Paragraph
uniform probability distribution, Paragraph
union, Paragraph
cardinality of, Principle
universal generalization, Paragraphs Definition
universal quantifier, Definition
valid, Definition Definition
variable, propositional, Paragraph
Venn diagram, Subsection Paragraph
for counting, Subsection
intersection, Paragraph
set difference, Paragraph
vertex, Paragraph Paragraph Definition Item
vertex cover, Exercise
degree sequence, Paragraph
Vizing’s theorem, Theorem
zombies, Exercise
