 # Discrete Mathematics: An Open Introduction, 3rd edition

## IndexIndex

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