## Index Index

using sets, Summary

adjacent

edges, Item

alternating path, Exercise

ancestor (in a rooted tree), Paragraph

and (logical connective), Item

truth condition for, Item

antecedent.

*See*hypothesisargument, Summary

arithmetic sequence, Summary

summing, Subsubsection

atomic statement, Paragraph

augmenting path, Exercise

balls and bins.

*See*stars and barsbijection, Subsection Paragraph Item

counting, Example

binary connective, Paragraph

binary digit.

*See*bitbinary 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

bit, Paragraph

bit string, Subsection Paragraph Summary Exercise

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 variablebreadth first search, Paragraph

Brooks’ Theorem, Theorem

Canadians, set of, Paragraphs

cannonball stacking, Exercise

cardinality, Paragraph

of a set, Item

of Cartesian product, Summary

of power set, Exercise

cardinality of, Summary

cases, Subsection

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, Summary

for a function, Paragraph

for a sequence, Summary

for arithmetic sequence, Summary

for geometric sequence, Summary

coloring

edges, Subsection

vertices, Paragraph

vertices vs edges, Exercise

combination, Section

closed formula for, Summary

common difference, Summary

common ratio, Summary

complete bipartite graph, Paragraph Paragraphs Item

complete graph, Paragraph Paragraphs Item

complex numbers (as characteristic roots), Paragraph

composition of functions, Exercise

congruence, Summary

arithmetic, Summary

divisibility, Summary

division, Summary

equality, Summary

equivalence relation, Summary

solving, Subsection

without solutions, Summary

conjunction, Item

consequent.

*See*conclusioncontradiction, 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

cube, Investigate!

type of graph, Paragraphs

De Morgan’s laws, Summary

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

difference equation.

*See*recurrence relationdifferences 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

with upper bound restriction, Paragraph

divisibility, Summary

divisibility relation, Subsection Summary

division with remainder.

*See*division algorithmdodecahedron, Subsection

domain of discourse.

*See*universe setdomino, Investigate! Exercise Exercise

double induction.

*See*induction, doubledouble negation, Summary

element of a set, Paragraph

empty set, Item

enumeration.

*See*countingequality of graphs, Example

Euclidean algorithm, Paragraph

Euler’s formula for planar graphs, Summary

exclusive or, Paragraph

existential quantifier, Summary

face (planar graph), Investigate! Paragraph

factorial, Paragraph

differences, Item

identity, Exercise

finite differences, Summary

football (American), Exercise

for all (quantifier), Summary

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 divisorgenerating 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

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

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

path, Paragraphs Item Item

Petersen, Exercise

planar, Item

simple, Paragraph

trail, Item

tree, Item

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

houses and utilities puzzle, Example

hypothesis, Summary

icosahedron, Subsection

truth condition for, Item

iff.

*See*if and only ifif…, then… (logical connective), Item

truth condition for, Item

image, Subsection

of a set, Paragraph

of a subset, Item

direct proof for, Summary

equivalent disjunction, Summary

implicit quantifier, Paragraphs

implies (logical connective), Item

truth condition for, Item

inclusion/exclusion.

*See*principle of inclusion/exclusioninclusive or, Paragraph

for strong induction, Item

double, Exercise

incorrect use of, Paragraphs

for strong induction, Item

proof structure, Summary

strong, Subsection Summary

strong, Paragraph

initial condition, Summary

for a function, Summary

injection, Item Subsection Paragraph Item

integer lattice, Paragraph

integer solutions to equation (counting), Example

interior angles, Exercise

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

\(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 latticelaw of logic, Example

linear Diophantine equation.

*See*Diophantine equationlogical equivalence, Summary

logically valid.

*See*law of logicmagic chocolate bunnies, Exercise

marriage problem.

*See*matchingpartial, Exercise

mathematical induction.

*See*induction; inductionmaximum degree, Paragraph

minimum spanning tree, Paragraph

mod, Paragraph

modular arithmetic, Summary

modulo \(n\), Summary

*modus ponens*, Paragraph

molecular statement, Paragraph

monochromatic, Paragraphs

using sets, Summary

multiset

counting, Exercise

relation to multigraph, Paragraph

\(n\) choose \(k\).

*See*binomial coefficientnatural numbers, set of, Item

necessary condition, Summary

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*injectiononto function.

*See*surjectionoperations 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 sumspartition, Paragraph

Pascal’s triangle, Subsection Paragraph Item Item

patterns in, Subsection

sum of row in, Exercise

alternating, Exercise

augmenting, Exercise

type of graph, Paragraphs

perfect matching.

*See*matchingof \(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/exclusionpigeonhole 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 polyhedronplaying cards, Exercise

regular, Investigate!

polynomial fitting, Section

cardinality of, Exercise

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 principleproof

by cases, Subsection

by contradiction, Subsection

by contrapositive, Subsection

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

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 referenceregion (graph).

*See*face (planar graph)regular polyhedron, Investigate!

remainder class, Subsection

residue class.

*See*remainder classrook 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, selfsentence (compared to statement), Paragraph

sentential variable.

*See*propositional variablesequence, Paragraph

as function, Paragraph

inductive definition for, Summary

notation for, Paragraph

sequence of partial sums, Paragraphs Example Exercise Exercise

for Fibonacci sequence, Item

for triangular numbers, Paragraph

set, 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

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 barsstring

binary (

*see*bit string)strong induction.

*See*induction, strongsubset, Subsection Paragraph

counting, Subsection

encoding as bit string, Paragraph

sufficient condition, Summary

sum principle.

*See*additive principlesummation notation, Example Paragraphs Exercise Exercise

surjection, Item Subsection Paragraph Item

tautology, Paragraph

telescoping, Paragraph

tetrahedron, Subsection

there exists (quantifier), Summary

tour, Euler.

*See*Euler circuitTower of Hanoi, Investigate! Paragraph

trail, Item

Euler (

*see*Euler path)transitive sets, Exercise

number of edges and vertices, Proposition

rooted, Paragraph Subsection

spanning, Subsection Summary

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

*The Twelve Days of Christmas*, Exercise

valid, Summary

variable, propositional, Paragraph

Venn diagram, Subsection Paragraph

for counting, Paragraph

intersection, Paragraph

set difference, Paragraph

vertex cover, Exercise

degree sequence, Paragraph

Vizing’s Theorem, Theorem

Euler (

*see*Euler path)weight (bit string), Item

zombies, Exercise