Discrete Mathematics: Week 1

Reference:
Johnsonbaugh, R., Discrete Mathematics, (6th edition), Pearson Prentice Hall, 2005.
The 5th edition of Johnsonbaugh may be used, but the 6th edition has some notation
changes and some different problem numbering.

Logic and Proofs

Propositions

Logic is the study of reasoning. We can look at examples involving everyday sentences,
and proceed to more formal mathematical approaches.
Consider the following sentences:

Adelaide is the capital of South Australia.

There are 30 hours in a day.

The square of 12 is 144.

Every even number greater than 2 can be expressed as the sum of two prime numbers
(Goldbach’s conjecture).

Each of the statements is either true or false. The first and third are obviously true, and
the second is obviously false. What do you think about the last?
A proposition is a statement that is either true or false (but not both). Whichever of
these (true or false) is the case is called the truth value of the proposition.
Some statements cannot be considered as propositions e.g.

Fred is a nerd.

The truth value is not well defined. However propositions in mathematics are well defined.

Definition. Let p and q be propositions.

The conjunction of p and q, denoted p ∧ q, is the proposition

p and q.

The disjunction of p and q, denoted p ∨ q, is the proposition

p or q.

1
Example 1. If

p: It is raining,
q: It is cold,

then the conjunction of p and q is

p∧q : It is raining and it is cold.

The disjunction of p and q is

p∨q : It is raining or it is cold.

A binary operator on a set X assigns to each pair of elements in X an element of X. The

operator ∧ assigns to each pair of propositions p and q the proposition p ∧ q. Thus, ∧ and
∨ are binary operators on propositions.

Definition. The truth value of the proposition p ∧ q is defined by the truth table

p q p∧q
T T T
T F F
F T F
F F F

In essence, p ∧ q is true provided that both p and q are true, and is false otherwise.

Definition. The truth value of the proposition p ∨ q is defined by the truth table

p q p∨q
T T T
T F T
F T T
F F F

In essence, p ∨ q is true provided that p or q (or both) are true, and is false otherwise.

Definition. The negation of p, denoted ¬ p, is the proposition

not p.

The truth value of the proposition ¬ p is defined by the truth table

p ¬p
T F
F T

In English, we sometimes write ¬ p as “It is not the case that p.”

2
Example 2. We have

p: The digit 1 occurs twice in the first 13 digits of π,

q: The digit 7 does not occur in the first 13 digits of π,
r: The first 13 digits of π sum to 60.

The compound proposition is

“Either 1 occurs twice in the first 13 digits of π and the digit 7 occurs at least once in
the first 13 digits of π or the first 13 digits of π sum to 60.”
The proposition can be written symbolically as

(p ∧ ¬ q) ∨ r.

The first digits of π are

π = 3.141592653589 79323864 . . . .

Then

(p ∧ ¬ q) ∨ r = (T ∧ ¬ T ) ∨ F
= (T ∧ F ) ∨ F
= F ∨F
= F,

and so the compound proposition is false.

Conditional Propositions and Logical Equivalence

Definition. If p and q are propositions, the proposition

if p then q

is called a conditional proposition and is denoted

p → q.

The proposition p is called the hypothesis (or antecedent) and the proposition q is called
the conclusion (or consequent).

Example 3. The lecturer states that if a student gets more than 50% then the student
will pass the course.

p: The student gets more than 50%,

q: The student passes the course.

If p and q are both true then p → q is true.

If p is true and q is false then p → q is false.

3
If p is false then p → q does not depend on the conclusion’s truth value, and so is regarded
as true.
This last often presents some difficulty in comprehending. We can think of it in this way.
If the student does not get more than 50%, we cannot regard p → q as false, and so it is
considered true. This gives the following truth table.
Definition. The truth value of the conditional proposition p → q is defined by the
following truth table:
p q p→q
T T T
T F F
F T T
F F T

Note that
p only if q
is considered logically the same as
if p then q.
An example of this is the two statements
“The student is eligible to take Maths 3 only if the student has passed Maths 2”
and
“If the student takes Maths 3 then the student has passed Maths 2,”
which are logically equivalent.
Definition. If p and q are propositions, the proposition
p if and only if q
is called a biconditional proposition and is denoted
p ↔ q.
The truth value of the proposition p ↔ q is defined by the following truth table:
p q p↔q
T T T
T F F
F T F
F F T

Note that p ↔ q means that p is a necessary and sufficient condition for q. The proposition
“p if and only if q” can be written “p iff q”.
Definition. Suppose that the propositions P and Q are made up of the propositions
p1 , . . . , pn . We say that P and Q are logically equivalent and write
P ≡ Q,
provided that, given any truth values p1 , . . . , pn , either P and Q are both true, or P and
Q are both false.

4
Example 4. Verify the first of De Morgan’s laws
¬ (p ∨ q) ≡ ¬ p ∧ ¬ q,
and the second,
¬ (p ∧ q) ≡ ¬ p ∨ ¬ q
will be a tutorial exercise.
P = ¬ (p ∧ q),
Q = ¬ p ∨ ¬ q.
p q p ∨ q ¬ p ¬ q ¬ (p ∨ q) ¬ p ∧ ¬ q
T T T F F F F
T F T F T F F
F T T T F F F
F F F T T T T
Thus P and Q are logically equivalent.
Definition. The converse of the conditional proposition p → q is the proposition q → p.
The contrapositive (or transposition) of the conditional proposition p → q is the proposi-
tion ¬ q → ¬ p.
Theorem 1. The conditional proposition p → q and its contrapositive ¬ q → ¬ p are
logically equivalent.
Proof:
The truth table
p q p → q ¬q ¬p ¬q → ¬p
T T T F F T
T F F T F F
F T T F T T
F F T T T T
shows that p → q and ¬ q → ¬ p are logically equivalent.
Some theorems in mathematics are best proved by using the contrapositive. It is likely
that you have seen some in matriculation mathematics or Engineering Mathematics 1 or
2E.
Exercise: Show that p → q ≡ ¬ p ∨ q.
Definition. A compound proposition is a tautology if it is true regardless of the truth
values of its component propositions.
A compound proposition is a contradiction if it is false regardless of the truth values of
its component propositions.
Example 5.
p ¬p p ∨ ¬p p ∧ ¬p
T F T F
F T T F
So p ∨ ¬ p is a tautology, and p ∧ ¬ p is a contradiction.

Exercise: Show that (p ∧ (p → q)) → q is a tautology.

5
Quantifiers

Consider the statement

p : n is a prime number.

The statement p is not a proposition, because a proposition is either true or false. We

have that p is true if n = 7, and false if n = 8.
Definition. Let P (x) be a statement involving the variable x and let D be a set. We call
P a propositional function or predicate (with respect to D) if for each x in D, P (x) is a
proposition. We call D the domain of discourse of P .
Example 6. Let P (n) be the statement

P (n) : n is a prime number,

and let D be the set of positive integers.

Then P is a propositional function with domain of discourse D since for each n in D,
P (n) is a proposition which is either true of false. P is true for n = 2, 3, 5, 7, . . . , and is
false for n = 1, 4, 6, 8, . . . .
A propositional function P by itself is neither true or false, but is true or false for each x
in its domain of discourse
Example 7. Let P (x) be the statement

P (x) : x2 − 5x + 6 = 0,

and let D be the set of positive integers.

Then P is a propositional function and is true for x = 2 or x = 3, and is false for all other
positive integers.
Definition. Let P be a propositional function with domain of discourse D. The statement

for every x, P (x)

is said to be a universally quantified statement. The symbol ∀ means “for every”. Thus
the statement
for every x, P (x)
may be written
∀x P (x).
The symbol ∀ is called a universal quantifier.
The statement
∀x P (x)
is true if P (x) is true for every x in D. The statement

∀x P (x)

is false if P (x) is false for at least one x in D.

6
Example 8. The universally quantified statement “for every positive integer n greater
than 1, 2n − 1 is prime” is false.

n=2 22 − 1 = 3
n=3 23 − 1 = 7
n=4 24 − 1 = 15.

We only need a counter example to prove a statement false. We need to prove for all x to
prove a statement true.

Definition. Let P be a propositional function with domain of discourse D. The statement

there exists x, P (x)

is said to be an existentially quantified statement. The symbol ∃ means “there exists”.

Thus the statement
there exists x, P (x)
may be written
∃x P (x).
The symbol ∀ is called an existential quantifier.
The statement
∃x P (x)
is true if P (x) is true for at least one x in D. The statement

∃x P (x)

is false if P (x) is false every x in D.

Example 9. The existentially quantified statement “for some positive integer n, 2n − 1

is divisible by 11” is true.

n=1 21 − 1 = 1
n=2 22 − 1 = 3
n=3 23 − 1 = 7
n=4 24 − 1 = 15
n=5 25 − 1 = 31
n=6 26 − 1 = 63
n=7 27 − 1 = 127
n=8 28 − 1 = 255
n=9 29 − 1 = 511
n = 10 210 − 1 = 1023.

The first case where 2n − 1 is divisible by 11 is for n = 10.

7
The variable x in the propositional function P (x) is called a free variable, that is x is
“free” to roam over the domain of discourse.
The variable x in the universally quantified statement

∀x P (x)

or in the existentially quantified statement

∃x P (x)

is a bound variable, in that x is “bound” by the quantifier.

Example 10. Verify that the existentially quantified statement “for some real number
1
x, 2 > 1” is false.
x +1
1
We must show that 2 > 1 is false for all real numbers x.
x +1
1 1
Now 2 > 1 is false when 2 ≤ 1 is true. Then
x +1 x +1
0 ≤ x2
1 ≤ x2 + 1
1
≤ 1,
x2 +1
1
and so ≤ 1 is true for all real numbers x.
x2 +1
Theorem 2. Generalised De Morgan Laws for Logic
If P is a propositional function, each pair of propositions in (a) and (b) has the same
truth values (i.e. either both are true or both are false).

(a) ¬ (∀x P (x)); ∃x ¬ P (x)

(b) ¬ (∃x P (x)); ∀x ¬ P (x)

Proof of (a):
If ¬ (∀x P (x)) is true, then ∀x P (x) is false.
Hence P (x) is false for at least one x in the domain of discourse, and ¬ P (x) is true for
at least one x in the domain of discourse. Hence ∃x ¬ P (x) is true.
Similarly, if ¬ (∀x P (x)) is false, then ∃x ¬ P (x) is false.

8
Example 10. (Continued)
1
We have that P (x) is the statement > 1, and aim to show that for all real numbers
x2 +1
x, P (x) is false i.e.
∃x P (x)
is false. We do this by verifying that for every real number x, ¬ P (x) is true i.e.
∀x ¬ P (x)
is true. Then
∀x ¬ P (x) is true
¬ (∀x ¬ P (x)) is false
∃x ¬ (¬ P (x)) is false (by De Morgan’s laws)
∃x P (x) is false
Example 11. Consider the well-known proverb
All that glitters is not gold.
This can be interpreted in English in two ways:

Every object that glitters is not gold.

Some object that glitters is not gold.

The intention is that the second is correct.

If we let P (x) be the propositional function “x glitters” and Q(x) be the propositional
function “x is gold”, then the first interpretation is represented as
∀x (P (x) → ¬ Q(x)),
and the second interpretation is represented as
∃x (P (x) ∧ ¬ Q(x)).
In a similar way in which the logical equivalence of the Exercise
p → q ≡ ¬p ∨ q
was shown, we can show that
¬ (p → q) ≡ p ∧ ¬ q.
Hence
∃x (P (x) ∧ ¬ Q(x)) ≡ ∃x ¬ (P (x) → Q(x))
≡ ¬ (∀x P (x) → Q(x))
by De Morgan’s laws.
We can read this last line as “it is not true that for all x, if x glitters then x is gold”.
This has been shown to be logically equivalent to “some object that glitters is not gold”.
The ambiguity comes from applying the negative to Q(x), rather than to the whole
statement.

9
Discrete Mathematics: Week 2
Nested Quantifiers

Example 1. Consider the statement

The sum of any two positive real numbers is positive.

This can be restated as: If x > 0 and y > 0, then x + y > 0. We need two universal
quantifiers, and can write the statement symbolically as

∀x∀y ((x > 0) ∧ (y > 0) → (x + y > 0)).

The domain of discourse is the set of all real numbers. Multiple quantifiers such as ∀x∀y
are said to be nested quantifiers.

The statement
∀x∀y P (x, y),
with domain of discourse D, is true if, for every x and for every y in D, P (x, y) is true.
The statement
∀x∀y P (x, y),
is false if there is at least one x and at least one y in D such that P (x, y) is false.

Example 2. Consider the statement

For any real number x, there is at least one real number y such that x + y = 0.

We know that this is true, as we can always choose y to be −x. We can write the statement
symbolically as
∀x ∈ R (∃y ∈ R, x + y = 0).
The domain of discourse is the set of all real numbers.

The statement
∀x∃y P (x, y),
with domain of discourse D, is true if, for every x in D, there is at least one y in D for
which P (x, y) is true.
The statement
∀x∃y P (x, y),
is false if there is at least one x in D such that P (x, y) is false for every y in D.

1
Example 3. Consider the nested quantifier

∃y ∈ R, (∀x ∈ R, x + y = 0).

This can be stated as

There is some real number y such that x + y = 0 for all real numbers x.

This is false, for example choose x to be 1 − y.

The statement
∃x∀y P (x, y),
with domain of discourse D, is true if there is at least one x in D such that P (x, y) is true
for every y in D.
The statement
∃x∀y P (x, y),
is false if, for every x in D, there is at least one y in D such that P (x, y) is false.

Example 4. Consider the statement

∃x∃y ((x > 1) ∧ (y > 1) ∧ (xy = 6)),

with domain of discourse the set of positive integers. This statement is true as there is at
least one positive integer x and at least one positive integer y, both greater than 1, such
that xy = 6 e.g. x = 2, y = 3.

The statement
∃x∃y P (x, y),
with domain of discourse D, is true if there is at least one x in D and at least one y in D
such that P (x, y) is true.
The statement
∃x∃y P (x, y),
is false if, for every x in D and for every y in D, P (x, y) is false.

Example 5. Using the generalized De Morgan laws for logic, the negation of

∀x∃y P (x, y)

is
¬ (∀x∃y P (x, y)) ≡ ∃x ¬ (∃y P (x, y)) ≡ ∃x∀y ¬ P (x, y).
Note that in the negation, ∀ and ∃ are interchanged.

2
Proofs

A mathematical system consists of

axioms which are assumed true;

definitions which are used to create new concepts in terms of existing one;

undefined terms which are not specifically defined but which are implicitly defined
by the axioms.

Within a mathematical system we can derive theorems.

A theorem is a proposition that has been proved to be true.

A lemma is a theorem that is not too interesting in its own right but is useful in
proving another theorem.

A corollary is a theorem that follows quickly from another theorem.

A proof is an argument that establishes the truth of a theorem.

Example 6. The real numbers furnish an example of a mathematical system. Among
the axioms are:

• For all real numbers x and y, xy = yx.

• There is a subset P of real numbers satisfying

(a) If x and y are in P , then x + y and xy are in P .

(b) If x is a real number, then exactly one of the following statements is true:

x is in P , x = 0, −x is in P .

Multiplication is implicitly defined by the first axiom.

The elements of P are called positive real numbers.
The absolute value |x| of a real number x is defined to be x if x is positive or 0, and −x
otherwise.
Example 7. Theorems about real numbers are

• x · 0 = 0 for every real number x.

• For all real numbers x, y and z, if x ≤ y and y ≤ z, then x ≤ z.

Example 8. An example of a lemma about real numbers is

• If n is a positive integer, then either n − 1 is a positive integer or n − 1 = 0.

Not too interesting in its own right, but can be used to prove other results.

3
Theorems are often of the form

For all x1 , x2 , . . . , xn , if p(x1 , x2 , . . . , xn ), then q(x1 , x2 , . . . , xn ).

This universally quantified statement is true provided that the conditional proposition

if p(x1 , x2 , . . . , xn ), then q(x1 , x2 , . . . , xn )

is true for all x1 , x2 , . . . , xn in the domain of discourse.
A direct proof assumes that p(x1 , x2 , . . . , xn ) is true, and using this and other axioms,
definitions and previously derived theorems, show directly that q(x1 , x2 , . . . , xn ) is true.

Example 9. A particular lemma is

The product of two odd integers is odd.

Proof:
Let the two odd integers be 2m+ 1 and 2n+ 1, where m and n are integers. Their product
is

(2m + 1)(2n + 1) = 4mn + 2m + 2n + 1

= 2(2mn + m + n) + 1,

which is odd.

A second technique of proof is proof by contradiction.

A proof by contradiction establishes by assuming that the hypothesis p is true and that
the conclusion q is false, and then using p and ¬ q as well as axioms, definitions and
theorems, derives a contradiction. A contradiction is a proposition of the form r ∧ ¬ r.
This is sometimes called an indirect proof.
Proof by contradiction is justified by noting that the propositions

p→q and p ∧ ¬q → r ∧ ¬r

are equivalent. The truth table is

p q r p → q p ∧ ¬q r ∧ ¬r p ∧ ¬q → r ∧ ¬r
T T T T F F T
T T F T F F T
T F T F T F F
T F F F T F F
F T T T F F T
F T F T F F T
F F T T F F T
F F F T F F T

4
Example 10. Prove that the root mean square of two number a and b, a > 0 and b > 0,
is equal to or greater than the arithmentic mean i.e.
s
a2 + b2 a+b
≥ .
2 2

Proof:
s
a2 + b2 a+b
Assume < .
2 2
Since both sides are positive, we can square without changing the direction of the inequal-
ity.

a2 + b2 (a + b)2
<
2 4
2(a2 + b2 ) < a2 + 2ab + b2
a2 − 2ab + b2 < 0
(a − b)2 < 0.

This is a contradiction, and hence

s
a2 + b2 a+b
≥ .
2 2
Example 11.
√ √ m
Theorem: 2 is irrational, that is 2 cannot be represented as , where m and n are
n
integers.
m
The hypotheses are that rational numbers ( where m and n are integers with no common
n
factors, n 6= 0) and square root are defined.
Proof:
√ √ m
Assume that 2 is rational, so that 2 = , where m and n are integers with no common
n
factors and n 6= 0. Then
√ m
2 =
n
m2
2= 2
n
m = 2n2 .
2

It is an easily proved lemma that if m2 is is even, then m is even. Hence if m is even,

m = 2k, and m2 = 4k 2 . Then

4k 2 = 2n2
2k 2 = n2 ,

and so n is even. Hence

√ m and n have a common factor, namely 2, and so there is a
contradiction. Hence 2 is irrational.

5
Proof by contrapositive is based on the fact that

p → q ≡ ¬ q → ¬ p.

The idea is to show that the opposite of the conclusion implies the opposite of the hy-
pothesis.

Example 12.
Theorem: If x and y are real numbers and x + y ≥ 2, then either x ≥ 1 or y ≥ 1.
Proof:
Let p be “x + y ≥ 2” and q be “either x ≥ 1 or y ≥ 1”.
Assume ¬ q: x < 1 and y < 1.
Then x + y < 1 + 1, or x + y < 2, which is ¬ p. Proven.

Proof by cases is used when the original hypothesis naturally divides into various cases.

Example 13.
Theorem: |x + y ≤ |x| + |y| for all real x and y.
Proof:
Consider the four cases as follows, where each of x, y is nonnegative or negative.

1. x, y ≥ 0:
Then x + y ≥ 0, so |x + y| = x + y = |x| + |y|.

2. x, y < 0:
Then x + y < 0, so |x + y| = −(x + y) = −x − y = |x| + |y|.

3. x ≥ 0, y < 0:
Then x + y < x < |x| + |y|, and
−(x + y) = −x − y ≤ −y = |y| ≤ |x| + |y|.

4. x < 0, y ≥ 0:
The same as case 3, swapping the roles of x and y.

Another form of proof is called an existence proof. An example of this is if we wanted

to show that
∃x P (x)
is true. It is only necessary to find a member x in the domain of discourse for which P (x)
is true.

6
Definition. An argument is a sequence of propositions written

p1
p2
..
.
pn
... q

or
p1 , p2 , . . . , pn / ... q.
The propositions p1 , p2 , . . . , pn are called the hypotheses and the proposition q is called
the conclusion. The argument is valid provided that if p1 , p2 , . . . , pn are all true, then q
must be true; otherwise the argument is invalid (or a fallacy).
Example 14. Determine whether the argument

p→q
¬q
... ¬ p

is valid.

(a) Using a truth table:

p q p → q ¬q ¬p
T T T F F
T F F T F
F T T F T
F F T T T
Note that the important line is the last. Why?
(b) A verbal argument proceeds: ¬ q is true when q is false, so p → q is only true when
p is false (as q is false). Hence ¬ p is true.
Example 15. Is the following argument valid?
If I don’t study hard, then I don’t get high distinctions.
I study hard
... I get high distinctions
Let p be “I study hard”, and let q be “I get high distinctions”. Then the argument is

¬p → ¬q
p
.
.. q

(a) The truth table is

p q ¬p → ¬q p q
T T T T T
T F T T F
F T F F T
F F T F F

7
 The first two lines are the important ones. The second line implies that it is an
invalid argument.

(b) Alternatively, assume that p is true and q is false. Then p → ¬ q ≡ F → T ≡ T, so

that both hypotheses can be true with a false conclusion.

Mathematical Induction

Example 16. An arithmetic teacher sets his class the problem of adding up all the
integers from 1 to 100. Can this be done in under 10 seconds? There is a piece of folklore
relating this to the mathematician Karl Friedrich Gauss (1777–1855) as a boy.
If we pair the numbers

1 + 2 + 3 + · · · + 49 + 50
100 + 99 + 98 + · · · + 52 + 51

we can see that each vertical pair adds to 101. Since there are 50 pairs, the sum is
50 × 101 = 5050.
The general case, the sum of all integers from 1 to n, is

n(n + 1)
1+2+3+ ··· +n = , n = 1, 2, 3, . . . .
2

The Principle of Mathematical Induction is a process by which a set of theorems

corresponding to the non-negative integers can be proven.

Definition. Suppose that we have a propositional function S(n) whose domain of dis-
course is the set of positive integers. Suppose that

S(1) is true;

for all n ≥ 1, if S(n) is true, then S(n + 1) is true.

The S(n) is true for every positive integer n.

The first part, S(1) is true, is called the Basis Step, and the second part is called the
Inductive Step. It is not necessary to start with n = 1, sometimes n = 0, 2, 3, . . . will
occur.

Example 16. (Continued)

Basis step: For n = 1, LHS = 1 and RHS = 1×2
2 = 1. True.
Inductive step: Assume that

n(n + 1)
1+2+3+ ··· +n = .
2

8
Then
n(n + 1)
1 + 2 + 3 + · · · + n + (n + 1) = + (n + 1), by the assumption
2
= 12 (n + 1)(n + 2), factorise whenever possible
(n + 1)(n + 2)
= , correct form.
2
Hence, by the Principle of Mathematical Induction, S(n) is true for all n ≥ 1.

Example 17. Show that

n(3n − 1)
1 + 4 + 7 + 10 + · · · + (3n − 2) = , n ≥ 1.
2

Basis step: For n = 1, LHS = 1 and RHS = 1×2

2 = 1. True.
Inductive step: Assume that

n(3n − 1)
1 + 4 + 7 + · · · + (3n − 2) = .
2
Then
n(3n − 1)
1 + 4 + 7 + · · · + (3n − 2) + (3n + 1) = + (3n + 1), by the assumption
 2
= 21 3n2 − n + 6n + 2 ,

can’t factorise here
= 12 3n2 + 5n + 2
 

(n + 1)(3n + 2)
=
2
(n + 1)(3(n + 1) − 1)
= , correct form.
2
Hence, by the Principle of Mathematical Induction, S(n) is true for all n ≥ 1.

9
Discrete Mathematics: Week 3
Mathematical Induction (Continued)

Correct formulae are given in advance. How do we know the correct formula?
Experiment to find a pattern e.g. sum of the odd integers.

S2n−1 = 1 + 3 + 5 + 7 + · · · + (2n − 1).

n S2n−1
1 1
2 4
3 9
4 16
.. ..
. .

It appears that S2n−1 = n2 .

Example 1. Show that

n(n + 1)(2n + 1)
S(n) : 12 + 22 + 32 + · · · + n2 = , n ≥ 1,
6
is true.
1×2×3
Basis Step: For n = 1, LHS = 1 and RHS = = 1. True.
6
Inductive Step: Assume that

n(n + 1)(2n + 1)
12 + 22 + 32 + · · · + n2 = .
6
Then

12 + 22 + 32 + · · · + n2 + (n + 1)2
n(n + 1)(2n + 1)
= + (n + 1)2 , by the assumption
6
1

= 6 (n + 1) 2n2 + n + 6(n + 1) , factorize whenever possible
= 16 (n + 1) 2n2 + 7n + 6
 

(n + 1)(n + 2)(2n + 3)
=
6
(n + 1)(n + 2)[2(n + 1) + 1]
= , correct form.
6
Since the Basis Step and Inductive Step have been verified, by the Principle of Mathe-
matical Induction, S(n) is true for all n ≥ 1.

1
Example 2. Show that
1 1 1 1 n
S(n) : + + + ··· + = , n ≥ 1,
1·2 2·3 3·4 n(n + 1) (n + 1)
is true.
Work a few terms:
1 1
=
1·2 2
1 1 1 1
+ = +
1·2 2·3 2 6
2
=
3
1 1 1 1 1 1
+ + = + +
1·2 2·3 3·4 2 6 12
3
=
4
1 1 1
Basis Step: For n = 1, LHS = = and RHS = . True.
1·2 2 2
Inductive Step: Assume that
1 1 1 1 n
+ + + ··· + = .
1·2 2·3 3·4 n(n + 1) (n + 1)
Then
1 1 1 1 1
+ + + ··· + +
1·2 2·3 3·4 n(n + 1) (n + 1)(n + 2)
n 1
= + , by the assumption
(n + 1) (n + 1)(n + 2)
1
= [n(n + 2) + 1] , factorize whenever possible
(n + 1)(n + 2)
1
= (n + 1)2
(n + 1)(n + 2)
n+1
= , correct form.
n+2
Since the Basis Step and Inductive Step have been verified, by the Principle of Mathe-
matical Induction, S(n) is true for all n ≥ 1.
Example 3. Divisibility example, Johnsonbaugh 1.7.5.
Show that 5n − 1 is divisible by 4 for all n ≥ 1.
Basis Step: For n = 1, 51 − 1 = 4 is divisible by 4. True.
Inductive Step: Assume that 5n − 1 is divisible by 4.
Then we wish to prove that 5n+1 − 1 is divisible by 4.
5n+1 − 1 = 5 × 5n − 1
= (5n − 1) + 4 × 5n .

2
The first part is divisible by 4 by the assumption, and 4 × 5n is divisible by 4, hence true.
Alternatively, put 5n − 1 = 4m, where m is an integer. Then

5n+1 − 1 = 5 × 5n − 1
= 5 × (4m + 1) − 1, by the assumption
= 4(5m) + 4,

which is divisible by 4.
Since the Basis Step and Inductive Step have been verified, by the Principle of Mathe-
matical Induction, S(n) is true for all n ≥ 1.

Example 4. Geometric sum, Johnsonbaugh 1.7.4.

Use induction to show that, if r 6= 1,

a(r n+1 − 1)
a + ar 1 + ar 2 + · · · + ar n =
r−1
for all n ≥ 0.
a(r − 1)
Basis Step: For n = 0, LHS = a and RHS = = a. True.
r−1
Inductive Step: Assume that

a(r n+1 − 1)
a + ar 1 + ar 2 + · · · + ar n = .
r−1
Then

a + ar 1 + ar 2 + · · · + ar n + ar n+1
a(r n+1 − 1)
= + ar n+1 , by the assumption
r−1
a(r n+1 − 1) + ar n+1 (r − 1)
=
r−1
a(r n+1
− 1 + r n+2 − r n+1 )
=
r−1
a(r n+2
− 1)
= .
r−1

Since the Basis Step and Inductive Step have been verified, by the Principle of Mathe-
matical Induction, S(n) is true for all n ≥ 0.

Example 5. Show that

S(n) : 4n > 5n2 , n ≥ 3,
is true.
This time the formula is true for n ≥ 3. For n = 1 we have 41 6> 5 and for n = 2,
42 6> 5 × 22 .
Basis Step: For n = 3, LHS = 43 = 64 and RHS = 5 × 32 = 45. True.

3
Inductive Step: Assume that 4n > 5n2 , n ≥ 3.
We want to show that 4n+1 > 5(n + 1)2 . Then

4n+1 = 4 (4n )
 
> 4 5n2 , by the assumption
 
= 5 n2 + 2n2 + n2
 
> 5 n2 + 2n + 1 , since n ≥ 3
= 5(n + 1)2 .

Since the Basis Step and Inductive Step have been verified, by the Principle of Mathe-
matical Induction, S(n) is true for all n ≥ 3.

Example 6. Tiling with trominos.

Solomon W. Golomb introduced polyominos in 1954. They can be used in tiling problems.
For example, the tetris game uses tetrominos, which will not tile a rectangle but which
can tile the plane. There are five free tetrominos, and seven if they are considered to be
one-sided (see figure).

The Dutch artist M.C. Escher produced many woodcut and lithograph art works of tiling
problems.
There are two trominos, the right and straight trominos. We will henceforth refer to the
right tromino just as a tromino.

4
Trominos can tile a deficient board, that is an n × n board with one square missing,
providing n 6= 3k. We can see that if n = 3k + 1, then
n2 − 1 = (3k + 1)2 − 1
= 9k 2 + 6k,
and is divisible by 3.
If n = 3k + 2, then
n2 − 1 = (3k + 2)2 − 1
= 9k 2 + 12k + 3,
and is divisible by 3.
We can tile all deficient boards with n 6= 3k, except for some deficient 5 × 5 boards – see
the figure below. Here we will prove by mathematical induction that all 2n × 2n deficient
boards can be tiled with trominos.

Basis Step: For n = 1, the 2 × 2 deficient board is a tromino and can be tiled.
Inductive Step: Assume that any 2n × 2n deficient board can be tiled.
Then we can divide the 2n+1 × 2n+1 deficient board into four 2n × 2n deficient boards,
with one board having the missing square anywhere, the other three boards having missing
squares in the corners by placement of one tromino as shown in the figure.

5
We can tile all four 2n × 2n deficient boards by the hypothesis, and can hence tile the
2n+1 × 2n+1 deficient board.
Since the Basis Step and Inductive Step have been verified, by the Principle of Mathe-
matical Induction, we can tile any 2n × 2n deficient board.

All examples so far have involved the Weak Form of Mathematical Induction, where if
S(n), then S(n + 1) is true. The Strong Form of Mathematical Induction allows us
to assume the truth of all of the preceeding statements.

Definition. Strong Form of Mathematical Induction

Suppose that we have a propositional function S(n) whose domain of discourse is the set
of integers greater than or equal to n0 . Suppose that

S(n0 ) is true;

for all n > n0 , if S(k) is true for all k, n0 ≤ k < n, then S(n) is true.

Then S(n) is true for every integer n ≥ n0 .

Example 7. Recurrence relation example.

Consider the sequence a1 , a2 , a3 , . . . with a1 = 1, a2 = 3 and an+1 = 3an − 2an−1 . Then

a3 = 3×3−2×1
= 7
a4 = 3×7−2×3
= 15
a5 = 3 × 15 − 2 × 7
= 31.

It would seem that an = 2n − 1.

Basis Steps: For n = 1, 2, a1 = 1 = 21 − 1 and a2 = 3 = 22 − 1. We require the two
preceding statements to be true.
Inductive Step: Assume that ai = 2i − 1 for 2 ≤ i ≤ n.

6
We want to prove that an+1 = 2n+1 − 1. Now

an+1 = 3an − 2an−1 , using the definition

 
= 3 (2n − 1) − 2 2n−1 − 1 , using the assumption
= 2n (3 − 1) − 3 + 2
= 2n+1 − 1.

Since the Basis Steps and Inductive Step have been verified, by the Principle of Mathe-
matical Induction, the formula an = 2n − 1 is true for all n ≥ 1.

Example 8. Show that postage of six cents or more can be achieved by using only 2-cent
and 7-cent stamps.
Basis Steps: For n = 6, 7. For six cent postage, use three 2-cent stamps and for seven
cent postage, use one 7-cent stamp.
Inductive Step: Assume n ≥ 8 and assume that postage of k cents or more can be achieved
by using only 2-cent and 7-cent stamps for 6 ≤ k < n.
By the assumption, we can make postage of n − 2 cents. Then add a 2-cent stamp to
make postage of n cents. The inductive step is complete.
Since the Basis Steps and Inductive Step have been verified, by the Principle of Mathe-
matical Induction we can make postage for all n ≥ 6.

Example 9. Prime numbers example.

S(n) : Every positive integer greater than 1 is the product of primes.
Basis Step: For n = 2, 2 is prime, and is the product of one number, itself.
Inductive Step: Assume that i is the product of primes for 2 ≤ i ≤ n.
If n + 1 is prime, it is the product of one prime.
If n + 1 is not prime, then n + 1 = pq where p and q are integers,

2 ≤ p ≤ q ≤ n.

Since by the assumption, p and q are the product of primes, then n+1 = pq is the product
of primes.
Since the Basis Step and Inductive Step have been verified, by the Principle of Mathe-
matical Induction S(n) is true for all n ≥ 2.

7
The Language of Mathematics
Sets

A set is a collection of objects, known as elements. It is described by listing the elements

in parentheses e.g.
A = { 1, 2, 3, 4 } .
Order does not matter e.g.

A = { 1, 2, 3, 4 } = { 2, 1, 4, 3 } .

Elements are assumed different e.g.

A = { 1, 2, 3, 4 } = { 1, 2, 2, 3, 4 } .

A large or infinite set can be defined by a property e.g.

B = { 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 } ,

or
B = { x | x is a positive odd integer less than 20 } ,
and
C = { x | x is a positive integer divisible by 3 } .
Read the symbol | as “such that”.
If X is a finite set, we let

|X| = the number of elements of X.

e.g. |A| = 4, |B| = 10.

If x is an element of A, we write x ∈ A. If not, we write x 6∈ A. e.g.

4 ∈ A, 4 6∈ B, 4 6∈ C.

The empty set is the set with no elements, denoted ∅. Hence ∅ = { }, |∅| = 0. e.g.
n o
x | x ∈ R and x2 + 1 = 0 .

What is |{ ∅ }|?
Two sets X and Y are equal if they have the same elements.
X = Y if for every x, if x ∈ X then x ∈ Y and for every x, if x ∈ Y then x ∈ X, i.e.

X = Y if ∀x ((x ∈ X → x ∈ Y ) ∧ (x ∈ Y → x ∈ X)).

8
Example 1. n o
X= x | x2 + x − 6 = 0 , Y = { 2, −3 } .
If x ∈ X, then

x2 + x − 6 = 0
(x − 2)(x + 3) = 0
x = 2, −3
x ∈ Y.

If x ∈ Y , then if x = 2,

x2 + x − 6 = 0
x ∈ X,

and if x = −3, then

x2 + x − 6 = 0
x ∈ X.

X is a subset of Y if every element of X is an element of Y . We write X ⊆ Y .

In symbols, X is a subset of Y if

∀x (x ∈ X → x ∈ Y ),

e.g.
{ 1, 2 } ⊆ { 1, 2, 3, 4 } .
We have

X ⊆ X
∅ ⊆ X
i.e. ∀x (x ∈ ∅ → x ∈ X)

x ∈ ∅ is false, hence x ∈ ∅ → x ∈ X is true.

If X ⊆ Y and X 6= Y , then X is a proper subset of Y , denoted X ⊂ Y . We have

If X ⊆ Y and Y ⊆ X, then X = Y .
If X ⊆ Y and Y is finite, then |X| ≤ |Y |.
If X ⊆ Y , Y is finite, and |X| = |Y |, then X = Y .

9
Discrete Mathematics: Week 4
Sets (Continued)

The power set of the set X, denoted P(X), is the set of all subsets of X.

Example 2. B = { a, b }, A = { a, b, c }.
P(B) = { ∅, { a }, { b }, { a, b } }, |P(B)| = 4.
P(A) = { ∅, { a }, { b }, { c }, { a, b }, { a, c }, { b, c }, { a, b, c } }, |P(A)| = 8.

Theorem. If |X| = n, then |P(X)| = 2n .

Proof: Johnsonbaugh uses a proof by Mathematical Induction. The idea is that exactly
half of the subsets of X contain a particular element of X. This can be seen by pairing
the subsets e.g. for the set A in Example 2.

∅ {a}
{b} { a, b }
{c} { a, c }
{ b, c } { a, b, c }

Basis Step: If n = 0, we have the empty set which has only one subset, itself. Then
|∅| = 0, and 20 = 1. True.
Inductive Step: Assume that a set with n elements has a power set of size 2n .
Let X be a set with n + 1 elements. Remove one element, x, from X to form a set Y .
Then Y has n elements, and by the assumption

|P(Y )| = 2n .

But since by the pairing argument

|P(X)| = 2 |P(Y )| ,

then
|P(X)| = 2n+1 .

Since the Basis Step and Inductive Step have been verified, by the Principle of Mathe-
matical Induction, if |X| = n, then |P(X)| = 2n is true for all n ≥ 0.
An alternative proof is to suppose that a 1 represents the presence of an element in a
subset, and a 0 represents its absence.
Then all subsets of X can be represented by a binary string of length |X| = n, and there
are 2n such strings.

1
Set Operations
Given two sets X and Y :
Their union is X ∪ Y = { x | x ∈ X or x ∈ Y }.
Their intersection is X ∩ Y = { x | x ∈ X and x ∈ Y }.
Their difference is X − Y = { x | x ∈ X and x 6∈ Y }.
Example 3. A = { a, b, c, d, e } and B = { 1, 2, 3, 4, a, b }.
A ∪ B = { a, b, c, d, e, 1, 2, 3, 4 }
A ∩ B = { a, b }
A − B = { c, d, e }
B − A = { 1, 2, 3, 4 }

Sets X and Y are disjoint if X ∩ Y = ∅. For example,

X = { 1, 2, 3 } and Y = { 4, 5 }
are disjoint.
A collection of sets S is pairwise disjoint if X and Y are disjoint for distinct X, Y in S.
For example,
S = { { a, b }, { c, d }, { e, f } }
is pairwise disjoint.
If we deal with sets which are subsets of a set U, then U is called the universal set.
The set U − X is the complement of X, denoted X.
Example 4. U = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
A = { 1, 3, 5, 7, 9 }, B = { 1, 2, 3, 8 }, C = { 3, 6, 8, 9 }
Then
A ∪ B = { 1, 2, 3, 5, 7, 8, 9 }
(A ∪ B) = { 0, 4, 6 }
A ∪ B ∪ C = { 1, 2, 3, 5, 6, 7, 8, 9 }
(A ∪ B ∪ C) = { 0, 4 }
C ∩ (A ∪ B) = { 6 }

Venn diagrams provide a pictorial view of sets. U, the universal set, is depicted as a
rectangle. Sets A, B, C, contained in U, are drawn as circles.

U U U
A B A B A B

A∪B A∩B A−B

2
 U
U A B
A

C
A
C ∩ (A ∪ B)

In Example 4, we have

A B
1
5, 7 2
3
9 8

6
C

0, 4

Theorem 2.1.12 Let U be a universal set and let A, B, and C be subsets of U. The
following properties hold.

(a) Associative laws:

(A ∪ B) ∪ C = A ∪ (B ∪ C), (A ∩ B) ∩ C = A ∩ (B ∩ C)

(b) Commutative laws:

A ∪ B = B ∪ A, A∩B = B∩A

(c) Distributive laws:

A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C), A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)

(d) Identity laws:

A ∪ ∅ = A, A∩U =A

(e) Complement laws:

A ∪ A = U, A∩A= ∅

(f) Idempotent laws:

A ∪ A = A, A∩A= A

3
 (g) Bound laws:
A ∪ U = U, A∩∅=∅

(h) Absorption laws:

A ∪ (A ∩ B) = A, A ∩ (A ∪ B) = A

(i) Involution law:

A=A

(j) 0/1 laws:

∅ = U, U =∅

(k) De Morgan’s laws for sets:

(A ∪ B) = A ∩ B, (A ∩ B) = A ∪ B

Proof: Of the first distributive law.

We have the Venn diagrams:

U U
A B A B

C C

B∪C A ∩ (B ∪ C)

U U
A B A B

C C

A∩B A∩C

Mathematically, the proof is as follows. Let

x ∈ A ∩ (B ∪ C).

Then

x∈A and x∈ B∪C

x∈A and x ∈ B or x ∈ C
x∈A∩B or x ∈ A ∩ C,

so that
x ∈ (A ∩ B) ∪ (A ∩ C).

4
This only proves that
A ∩ (B ∪ C) ⊆ (A ∩ B) ∪ (A ∩ C).
Let
x ∈ (A ∩ B) ∪ (A ∩ C).

Then

x∈A∩B or x∈A∩C
x ∈ A and x ∈ B or x ∈ A and x ∈ C
x∈A and x ∈ B or x ∈ C
x∈A and x ∈ B ∪ C,

so that
x ∈ A ∩ (B ∪ C).

Proof of the first De Morgan law.

We have the Venn diagrams:

U U
A B A B

A∪B (A ∪ B) = A ∩ B

U U
A B A B

A B

Mathematically, the proof is as follows. Let

x ∈ (A ∪ B).

Then

x 6 ∈ A∪B
x 6∈ A and x 6∈ B
x∈A and x∈B
x ∈ A ∩ B.

This only proves that

(A ∪ B) ⊆ A ∩ B.

5
Let
x ∈ A ∩ B.
Then

x∈A and x∈B

x 6∈ A and x 6∈ B
x 6∈ A∪B
x ∈ (A ∪ B).

If S = { A1 , A2 , . . . , An }, then the union of many sets is

[
S = { x | x ∈ Ai for some Ai ∈ S }.

The intersection of many sets is

\
S = { x | x ∈ Ai for all Ai ∈ S }.

We write n n
[ [ \ \
S= Ai , S= Ai .
i=1 i=1

For infinitely many sets

S = { A1 , A2 , A3 , . . . }
this becomes ∞ ∞
[ [ \ \
S= Ai , S= Ai .
i=1 i=1

Example 5. Let
S = { A1 , A2 , A3 , . . . }
where
An = { n, n + 1, n + 2, . . . }.
That is,

A1 = { 1, 2, 3, . . . }
A2 = { 2, 3, 4, . . . }
A3 = { 3, 4, 5, . . . },

etc.
Obviously [
S = { 1, 2, 3, . . . } = A1 ,
and \
S = ∅,
as
\
1∈
/ S as 1 ∈
/ A2 , A3 , . . .
\
2∈
/ S as 2 ∈
/ A3 , A4 , . . .

etc.

6
A collection S of non-empty subsets of X is a partition of X if each element of X belongs
to exactly one member of X. That is, S is pairwise disjoint and S = X.
S

Example 6.

(a) X = { 1, 2, 3, 4, 5, 6, 7, 8 }
Then
S = { {2, 4, 8 }, { 1, 3, 5, 7 }, { 6 } }
is a partition of S.

(b) X = { x | x ∈ R }

S = { { x | x is rational }, { x | x is real } }
is not a partition of X.

T = { { x | x is rational }, { x | x is irrational } }

is a partition of X.

Sets are unordered collections of elements. Sometimes order is important.

An ordered pair of elements, written (a, b), is different from the ordered pair (b, a) (unless
a = b).
Alternatively, (a, b) = (c, d) if and only if a = c and b = d.
If X and Y are sets, we let X × Y denote the set of all ordered pairs (x, y) where x ∈ X
and y ∈ Y .
We call X × Y the Cartesian product of X and Y .

Example 7. The Last Duck Vietnamese Restaurant and Takeaway sells

Entrees (set E)

a: Chicken Cold Roll

b: Vietnamese Spring Roll
c: Steamed Pork Dumplings

Mains (set M)

1: Twice Cooked Duck Leg Curry

2: Char-grilled Lemongrass Pork
3: Steamed Ginger Infused Chicken
4: Whole Prawns with Fanta Fish Sauce

7
Then E = { a, b, c } and M = { 1, 2, 3, 4 }.
The Cartesian product lists the 12 possible dinners consisting of one entree and one main
course. So

E × M = { (a, 1), (a, 2), (a, 3), (a, 4), (b, 1), (b, 2), (b, 3), (b, 4), (c, 1), (c, 2), (c, 3), (c, 4) } .

This is actually a cut-down version of the menu. In fact, there are 5 entrees and 8 main
courses. How many dinners are possible?

For the general case,

|X × Y | = |X| · |Y |.

8
Relations
Relations Johnsonbaugh 3.1

We can consider a relation as a table linking the elements of two sets e.g. product vs price.

Definition. A (binary) relation R from a set X to a set Y is a subset of the Cartesian

product X × Y .
If (x, y) ∈ R, we write x R y and say that x is related to y. If X = Y , we call R a (binary)
relation on X.
The set
{ x ∈ X | (x, y) ∈ R for some y ∈ Y }
is called the domain of R.
The set
{ y ∈ Y | (x, y) ∈ R for some x ∈ X }
is called the range of R.

In simpler terms, a (binary) relation R connects elements in X to elements in Y . For

example, we have pictorially

X
1 Y
a
2
b
3
c
4

R = { (1, a), (2, c), (3, b) }.

This is called an arrow diagram.
The domain is all elements of X that occur in R i.e. { 1, 2, 3 }.
The range is all elements of Y that occur in R i.e. { a, b, c }.

Example 1. Johnsonbaugh 3.1.3

X = { 2, 3, 4 } and Y = { 3, 4, 5, 6, 7 }

Define a relation from X to Y by (x, y) ∈ R if x divides y (with 0 remainder). Therefore

R = { (2, 4), (2, 6), (3, 3), (3, 6), (4, 4) }.

9
We could write R as a table:

X Y
2 4
2 6
3 3
3 6
4 4

The domain of R is { 2, 3, 4 }, and the range of R is { 3, 4, 6 }.

Example 2. Johnsonbaugh 3.1.4
Let R be a relation on X = { 1, 2, 3, 4 } defined by (x, y) ∈ R if x ≤ y, x, y ∈ X.
R = { (1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4) }.
The domain and range of R are both X.

A relation on a set can be described by its digraph.

Draw dots or vertices as elements of X. If (x, y) ∈ R, draw an arrow from x to y – a
directed edge.
An element (x, x) is called a loop.
The diagraph of Example 2 is:

1 2

3 4

Example 3. The relation R on X = { a, b, c, d } is

R = { (a, a), (b, c), (c, b), (d, d) }.
The digraph is:

a b

c d

10
Definition. A relation R on a set X is called reflexive if (x, x) ∈ R for every x ∈ X.

Example 2 is reflexive. There is a loop on every vertex.

Example 3 is not reflexive.

Definition. A relation R on a set X is called symmetric if for all x, y ∈ X, if (x, y) ∈ R

then (y, x) ∈ R.

Example 3 is symmetric. Directed edges go both ways between vertices.

Definition. A relation R on a set X is called antisymmetric if for all x, y ∈ X, if (x, y) ∈ R

and x 6= y, then (y, x) 6∈ R.

Example 2 is antisymmetric. Between any two distinct vertices there is at most one
directed edge.
Can a relation R be both symmetric and antisymmetric?

Definition. A relation R on a set X is called transitive if for all x, y, z ∈ X, if (x, y) ∈ R

and (y, z) ∈ R, then (x, z) ∈ R.

Example 2 is transitive. We need to list all pairs to verify.

(x, y) (y, z) (x, z)

(1, 1) (1, 1) (1, 1)
(1, 1) (1, 2) (1, 2)
(1, 1) (1, 3) (1, 3)
(1, 1) (1, 4) (1, 4)
(1, 2) (2, 2) (1, 2)
(1, 2) (2, 3) (1, 3)
etc.

Do we really need to list all pairs? If x = y, and (x, y), (y, z) ∈ R, then (x, z) ∈ R is
automatically true. Hence the table need be only

(x, y) (y, z) (x, z)

(1, 2) (2, 3) (1, 3)
(1, 2) (2, 4) (1, 4)
(1, 3) (3, 4) (1, 4)
(2, 3) (3, 4) (2, 4)

Example 3 is not transitive e.g. (b, c), (c, b) ∈ R, but (b, b) 6∈ R.

The digraph of a transitive relation has the property that whenever there are directed
edges from x to y and from y to z, there is a directed edge from x to z.

11
Discrete Mathematics: Week 5
Relations (Continued)

Relations can be used to order elements of a set. For example, the relation R on the
positive integers defined by
(x, y) ∈ R if x ≤ y
orders the integers, and is reflexive, antisymmetric and transitive i.e.

reflexive : x≤x
antisymmetric : if x ≤ y and x 6= y, then y 6≤ x
transitive : if x ≤ y and y ≤ z, then x ≤ z.

Definition. A relation R on a set X is called a partial order if R is reflexive, antisymmetric

and transitive.

Example 4. X = { 2, 3, 4, 5, 6 }
R is the relation defined by (x, y) ∈ R if y is larger than x by an even number or zero.
Hence
R = { (2, 2), (2, 4), (2, 6), (3, 3), (3, 5), (4, 4), (4, 6), (5, 5), (6, 6) }.
The digraph is

3 5

2 4

This is

reflexive : loops on all vertices

antisymmetric : at most one directed arc between each pair of vertices
transitive : need only check (2, 4), (4, 6), and (2, 6) ∈ R.

If R is a partial order on X, we often write x  y when (x, y) ∈ R.

If x, y ∈ X and either x  y or y  x, then we say x and y are comparable.
If x, y ∈ X, x 6 y and y 6 x, then we say x and y are incomparable.

1
If every pair of elements in X is comparable, we call R a total order.
Example 2 is a total order. Either (x, y) ∈ R or (y, x) ∈ R for all x, y = 1, 2, 3, 4.
More generally, the less than or equals relation on the positive integers is a total order,
since either x ≤ y or y ≤ x (or both if x = y).
Example 4 is not a total order. Why?
Partial orders can be used in task scheduling.
Example 5. Johnsonbaugh 3.1.21
The set T of tasks in taking an indoor flash photograph is as follows.

1. Remove lens cap.

2. Focus camera.

3. Turn off safety lock.

4. Turn on flash unit.

5. Push photo button.

Some tasks must be done before others, some can be done in either order.
Define the relation R on T by

iRj if i = j or task i must be done before task j.

Then

R = { (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (1, 2), (1, 5), (2, 5), (3, 5), (4, 5) } .

R is reflexive, antisymmetric and transitive, and is a partial order. Why is R not a total
order?
Possible solutions are 1, 2, 3, 4, 5 or 3, 4, 1, 2, 5.
Definition. Let R be a relation from X to Y . The inverse of R, denoted R−1 , is the
relation from X to Y defined by

R−1 = { (y, x) | (x, y) ∈ R } .

Example 1. (Continued)

X = { 2, 3, 4 } and Y = { 3, 4, 5, 6, 7 }

We have (x, y) ∈ R if x divides y, so

R = { (2, 4), (2, 6), (3, 3), (3, 6), (4, 4) },

then
R−1 = { (4, 2), (6, 2), (3, 3), (6, 3), (4, 4) }
and might be described as (y, x) ∈ R−1 if y is divisible by x.

2
Definition. Let R1 be a relation from X to Y and R2 be a relation from Y to Z. The
composition of R1 and R2 , denoted R2 ◦ R1 , is the relation from X to Z defined by

R2 ◦ R1 = { (x, z) | (x, y) ∈ R1 and (y, z) ∈ R2 for some y ∈ Y } .

Example 6.
A = { 1, 2, 3, 4 } B = { a, b, c, d } C = { x, y, z }

R = { (1, a), (2, d), (3, a), (3, b), (3, d) }

S = { (b, x), (b, z), (c, y), (d, z) }

The arrow diagram represents this as:

1 2 3 4
A

a b c d B

C
x y z

The composition of the relations is

S ◦ R = { (2, z), (3, x), (3, z) }.

3
Matrices of Relations

For a quick revision on matrices, read Johnsonbaugh Appendix A.

A matrix is a convenient way to represent a relation R from X to Y .
Label the rows with the elements of X, label the columns with the elements of Y , and
make the entry in row x column y a 1 if x R y and a 0 otherwise.
This is the matrix of the relation R.

Example 2. (from §3.1, revisited)

X = { 1, 2, 3, 4 } and (x, y) ∈ R if x ≤ y.
R = { (1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4) } .
Then the matrix is
1 2 3 4
1 1 1 1 1
 

2 
 0 1 1 1 

3 0 0 1 1
 
 
4 0 0 0 1

The matrices depend on the ordering of the elements in the sets X and Y .
A relation R on X has a square matrix.
The relation R on a set X which has a matrix A is

• reflexive if and only if (iff) A has 1’s on the main diagonal. Recall

(x, x) ∈ R for all x ∈ X.

• symmetric if and only if A is symmetric. Recall

If (x, y) ∈ R then (y, x) ∈ R.

If the (i, j) th element of A is 1, so is the (j, i) th element.

• antisymmetric if and only if any 1 in the (i, j) th entry of A is matched by a 0 in

the (j, i) th entry in any position off the main diagonal. Recall

If (x, y) ∈ R then (y, x) 6∈ R for x 6= y.

Example 6. (from §3.1, revisited)

A = { 1, 2, 3, 4 } B = { a, b, c, d } C = { x, y, z }

R = { (1, a), (2, d), (3, a), (3, b), (3, d) }

S = { (b, x), (b, z), (c, y), (d, z) }

4
 a b c d
1 1 0 0 0
 

A1 = matrix of R = 2 
 0 0 0 1 

3 1 1 0 1
 
 
4 0 0 0 0
x y z
a 0 0 0
 

A2 = matrix of S = b 
 1 0 1 

c 0 1 0
 
 
d 0 0 1

x y z
1 0 0 0 0 0 0 1 0 0 0
     

A1 A2 = 
 0 0 0 1 


 1 0 1 
 = 2 
 0 0 1 

1 1 0 1 0 1 0 3 1 0 2
     
     
0 0 0 0 0 0 1 4 0 0 0
What does the 2 in (A1 A2 )(3,3) mean?
The composition of the relations is
S ◦ R = { (2, z), (3, x), (3, z) }.
So if we convert the ‘2’ to a ‘1’, we have the matrix of S ◦ R.

Theorem 3.3.6 Johnsonbaugh

Let R1 be a relation from X to Y and let R2 be a relation from Y to Z. Choose the
orderings of X, Y , and Z. Let A1 be the matrix of R1 and let A2 be the matrix of R2
with respect to the orderings selected. The matrix of the relation R2 ◦ R1 with respect to
the orderings selected is obtained by replacing each nonzero term in the matrix product
A1 A2 by 1.
Discussion: Suppose that the (i, j) th entry in A1 A2 is nonzero. We obtain this entry by
multiplying the i th row of A1 by the j th column of A2 . Therefore there must be at least
one element (i, k) in the i th row of A1 and at least one element (k, j) in the j th column
of A2 which are both 1.
Then (i, k) ∈ R1 and (k, j) ∈ R2 , so (i, j) ∈ R2 ◦ R1 .
Note that the matrix sizes are automatically correct for matrix multiplication, since the
number of columns of A1 and the number of rows in A2 are equal to the number of
elements of Y .
Matrix Test for Transitivity
The theorem gives a test for a relation R on a set X being transitive.
Compute A2 and compare A and A2 . The relation R is transitive if and only if whenever
entry (i, j) in A2 is nonzero, entry (i, j) in A is also nonzero.
Suppose that the entry (i, j) in A2 is nonzero. Then there is at least one element (i, k) in
the i th row of A and at least one element (k, j) in the j th column of A which are both
1. Hence (i, k) ∈ R and (k, j) ∈ R. If the (i, j) th entry of A is zero, then (i, j) 6∈ R.

5
Example 2. (from §3.1, revisited)
R is a relation on X = { 1, 2, 3, 4 } defined by (x, y) ∈ R if x ≤ y, for x, y ∈ X.

R = { (1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4) }.

1 2 3 4
1 1 1 1 1
 

A= 2 
 0 1 1 1 

3 0 0 1 1
 
 
4 0 0 0 1
1 2 3 4
1 1 2 3 4
 

A2 = 2 
 0 1 2 3 

3 0 0 1 2
 
 
4 0 0 0 1
Then A2 has 1’s only in positions where A has 1’s, and the relation is transitive.

Example 3. (from §3.1, revisited)

R = { (a, a), (b, c), (c, d), (d, d) }

a b c d
a 1 0 0 0
 

A= b 
 0 0 1 0 

c 0 1 0 0
 
 
d 0 0 0 1
a b c d
a 1 0 0 0
 

A2 = b 
 0 1 0 0 

c 0 0 1 0
 
 
d 0 0 0 1
Then A2 has 1’s in the (b, b) and (c, c) positions, whereas A does not. The relation is not
transitive i.e. (b, c) ∈ R and (c, b) ∈ R, but (b, b) 6∈ R and (c, c) 6∈ R.

6
Functions Johnsonbaugh 2.2

Definition. Let X and Y be sets. A function f from X to Y is a subset of the Cartesian

product X × Y having the property that for each x ∈ X, there is exactly one y ∈ Y with
(x, y) ∈ f . We sometimes denote a function f from X to Y as f : X → Y . (Can also
write y = f (x).)
The set X is called the domain of f . The set

{ y | (x, y) ∈ f }

(which is a subset of Y ) is called the range of f .

Example 1. The relation f = { (1, a), (2, b), (3, a) } from X = { 1, 2, 3 } to Y = { a, b, c }

is a function. Why?
The relation R = { (1, a), (2, b), (3, c) } from X = { 1, 2, 3, 4 } to Y = { a, b, c } is not a
function. Why?
The relation R = { (1, a), (1, b), (2, b), (3, c) } from X = { 1, 2, 3 } to Y = { a, b, c } is not a
function. Why?
We can depict the situations using arrow diagrams. For the three cases we have:

X Y
1 a

2 b

3 c

X
1 Y
a
2
b
3
c
4

X Y
1 a

2 b

3 c

7
There must be exactly one arrow from every element in the domain. There cannot be no
arrow, or more than one arrow.

Some Useful Functions

Definition. If x is an integer and y is a positive integer, we define x mod y to be the

remainder when x is divided by y.

Some simple examples:

6 mod 3 = ?
9 mod 10 = ?
14 mod 3 = ?
365 mod 7 = ?

This last result tells us that 29th March next year will be a Thursday.

Definition. The floor of x, denoted ⌊ x ⌋, is the greatest integer less than or equal to x.
The ceiling of x, denoted ⌈ x ⌉, is the least integer greater than or equal to x.

Some simple examples:

⌊ 1.4 ⌋ = ? ⌈ 1.4 ⌉ = ?
⌊6⌋ = ? ⌈6⌉ = ?
⌊ −5.7 ⌋ = ? ⌈ −5.7 ⌉ = ?

The graphs of the floor and ceiling functions are shown below.

y
Floor function 2 [ )

1 [ )

[ )
−3 −2 −1 0 1 2 3 x

[ ) −1

[ ) −2

8
 y
Ceiling function 2 ( ]

1( ]

( ]
−3 −2 −1 0 1 2 3 x

( ] −1

( ] −2

Example 2. Hash Functions Johnsonbaugh Example 2.2.14

We wish to store nonnegative integers in computer memory cells. A hash function com-
putes the location from the data item.
For example, if the cells are labelled 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, we might use

h(n) = n mod 11.

Store the numbers 15, 558, 32, 132, 102, 5 in the eleven cells.

15 = 1 × 11 + 4 so 15 mod 11 = 4
558 = 50 × 11 + 8 so 558 mod 11 = 8
32 = 2 × 11 + 10 so 32 mod 11 = 10
132 = 12 × 11 + 0 so 132 mod 11 = 0
102 = 9 × 11 + 3 so 102 mod 11 = 3
5 = 0 × 11 + 5 so 5 mod 11 = 5

These all store in the appropriate cells as shown in the diagram below.

132 102 15 5 558 32

0 1 2 3 4 5 6 7 8 9 10

Now store 257 = 23 × 11 + 4.

But location 4 is occupied. A collision has occurred.
The collision resolution policy is to use the next highest unoccupied cell. But if all higher
numbered cells are occupied, start looking at the lowest numbered cell. In this case,
10 → 0.
To find the data item n, compute m = h(n) and look at location m. If n is not there,
look at higher numbered cells.

9
Definition. A function f from X to Y is said to be one-to-one (or injective) if for each
y ∈ Y , there is at most one x ∈ X with f (x) = y.
Example 3. f = { (1, a), (2, b), (3, c) } from X = { 1, 2, 3 } to Y = { a, b, c, d } is a one-
to-one function.
f = { (1, a), (2, b), (3, a) } from X = { 1, 2, 3 } to Y = { a, b, c, d } is a function, but not
one-to-one.
The arrow diagrams illustrate this.

Y Y
X a X a
1 1
b b
2 2
c c
3 3
d d

Definition. If f is a function from X to Y and the range of f is Y , f is said to be onto

Y (or an onto function or a surjective function).
Example 4. f = { (1, a), (2, b), (3, c) } from X = { 1, 2, 3 } to Y = { a, b, c } is onto. The
arrow diagram is:

X Y
1 a

2 b

3 c

If Y = { a, b, c, d }, f is not onto.
Definition. A function that is both one-to-one and onto is called a bijection.

In the preceding example, the function

f = { (1, a), (2, b), (3, c) }

is a bijection.
Inverse Function
Suppose that f is a one-to-one, onto function from X to Y . The inverse relation

{ (y, x) | (x, y) ∈ f }

is a one-to-one, onto function from Y to X, the inverse function f −1 .

10
Since f is onto, the range of f is Y , and hence the domain of f −1 is Y .
Since f is one-to-one, there is only one x ∈ X for which (y, x) ∈ f −1 , so f −1 is a function.
We can obtain the arrow diagram for f −1 by reversing the directions of the arrows for f .
Since f is one-to-one, f −1 is one-to-one. Since f is a function, the domain of f is X and
hence f −1 is onto.
Example 5. R1 = { (1, b), (2, a), (3, c) } from X = { 1, 2, 3 } to Y = { a, b, c, d }.
Or we could say
R1 = { (1, b), (2, a), (3, c) } ⊆ { 1, 2, 3 } × { a, b, c, d }.
R1 is a function, is one-to-one, but is not onto. This is evident also from the arrow
diagram.

Y
X a
1
b
2
c
3
d

R1−1 = { (a, 2), (b, 1), (c, 3) } ⊆ { a, b, c, d } × { 1, 2, 3 }

is not a function. Why?
R2 = { (1, b), (2, c), (3, a), (4, d) } ⊆ { 1, 2, 3, 4 } × { a, b, c, d }.
The arrow diagram is

X Y
1 a

2 b

3 c

4 d

R2 is a function, is one-to-one, and is onto.

R2−1 = { (a, 3), (b, 1), (c, 2), (d, 4) } ⊆ { a, b, c, d } × { 1, 2, 3, 4 }.
R2−1 is a function, is one-to-one, and is onto.

11
Discrete Mathematics: Week 6

Algorithms
Introduction

An algorithm is a step by step method of solving a problem i.e. a recipe.

Algorithms typically have the following characteristics.

• Input The algorithm receives input.

• Output The algorithm produces output.

• Precision The steps are precisely stated.

• Determinism The intermediate results of each step of execution are unique

and are determined only by the inputs and the results of the preceding steps.

• Finiteness The algorithm terminates; that is, it stops after finitely many
instructions have been executed.

• Correctness The output produced by the algorithm is correct; that is, the
algorithm correctly solves the problem.

• Generality The algorithm applies to a set of inputs.

Algorithms are written in pseudocode, which resembles real computer code. Johnsonbaugh
in the 6th edition has rewritten algorithms to be more like Java.
Algorithm 4.1.1 Finding the Maximum of Three Numbers
This algorithm finds the largest of the numbers a, b, and c.
Input: a, b, c
Output: large (the largest of a, b, and c)

1. max3 (a, b, c) {

2. large = a

3. if (b > large) // if b is larger then large, update large

4. large = b

5. if (c > large) // if c is larger then large, update large

6. large = c

7. return large

8. }

1
 Algorithms consist of a title, a brief description of the algorithm, the input to and output
from the algorithm, and functions containing the instructions of the algorithm. This
algorithm has one function.
Sometimes lines are numbered to make it convenient to refer to them.

line 1 max3 is the name of the function, and a, b, c are input parameters or variables.

line 2 = is the assignment operator. Testing equality uses ==. large is assigned the value
of a.

line 3 This introduces the if statement. The structure is

if (condition)
action
If condition is true, action is executed and control passes to the statement following
action.
If condition is false, action is not executed and control passes immediately to the
statement following action. For example,
if (x == 0)
y=0
z =x+y
If action consists of multiple statements, enclose them in braces.
if (x ≥ 0) {
y=0
z =x+3
}
We can use

arithmetic operators +, −, ∗, /, ( , )
relational operators ==, ¬ =, <, >, ≤, ≥
logical operators ∧, ∨, ¬

The Matlab equivalent command is

if expression
commands
end
There is also the if else statement, which has the structure
if (condition)
action 1
else
action 2

2
 The notation // signals that the rest of the line is a comment. A more common
notation is to use %, which is used, for example, by Matlab and postscript. The
Matlab equivalent command is
if expression
commands if true
else
commands if false
end
Matlab can extend the if structure further with elseif.

line 4 This assigns large the value of b if b > large.

line 6 This assigns large the value of c if c > large.

line 7 The return statement simply terminates the function.

The return large statement terminates the function and returns the value of large.
If there is no return statement, the closing brace terminates the function.

We can assign values to the input variables and use a simulation called a trace to evaluate
the operation of the algorithm. For example, we set

a = 6, b = 1, c = 9.

Then

line 2 Set large to a, namely 6.

line 3 The if statement b > large is false, so line 4 is not executed.

line 5 The if statement c > large is true, so at line 6 large is set to the value of c, namely 9.

Algorithm 4.1.2 Finding the Maximum Value in a Sequence

This algorithm finds the largest of the numbers s1 , . . . sn .
Input: s, n
Output: large (the largest value in the sequence s)
max (s, n) {
large = s1
for i = 2 to n
if (si > large)
large = si
return large
}

3
The structure of the for loop is
for var = init to limit
action
If action consists of multiple statements, enclose them in braces.
The for loop specifies the initial and final integer values between which the operations are
processed. Alternatively, we can use a while loop.
while (condition)
action
action is repeated as long as condition is true.
The Matlab equivalent command is
for i = m:n
commands
end
Using a while loop, Algorithm 4.1.2 would become
max (s, n) {
large = s1
i=2
while i ≤ n {
if (si > large)
large = si
i=i+1
}
return large
}
The Matlab equivalent command is
while expression
commands
end

4
Examples of Algorithms

Algorithm 4.2.1 Text Search

This algorithm searches for an occurrence of the pattern p in text t. It returns the smallest
index i such that p occurs in t starting at index i. If p does not occur in t, it returns 0.
Input: p (indexed from 1 to m), m, t (indexed from 1 to n), n
Output: i
text search(p, m, t, n) {
for i = 1 to n − m + 1 {
j=1

// i is the index in t of the first character of the substring

// to compare with p, and j is the index in p

// the while loop compares ti · · · ti+m−1 and p1 · · · pm

while (ti+j−1 == pj ) {
j =j+1
if (j > m)
return i
}
}
return 0
}
The algorithm indexes the characters in the text with i and those in the pattern with j.
The search starts with the first character in the text, and if the pattern is not found,
finishes with character n − m + 1 in the text, when the last characters in the pattern and
text coincide.
If there is a match for the first indices in the pattern and text, then the pattern index j
is incremented by 1, and the next characters compared. This continues until either the
pattern is found, or there is not a match. In the latter case, the text index i is incremented
by 1, the pattern index j is reset to 1, and the match process repeats.

5
Example 1. This shows the operation of the text search algorithm in a search for the
string “001” in the string “010001”.

j=1 j=2 j=1

↓ ↓ ↓
0 0 1 0 0 1 0 0 1
0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1
↑ ↑ ↑
i=1 Y i=1 N i=2 N

j=1 j=2 j=3

↓ ↓ ↓
0 0 1 0 0 1 0 0 1
0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1
↑ ↑ ↑
i=3 Y i=3 Y i=3 N
j=1 j=2 j=3
↓ ↓ ↓
0 0 1 0 0 1 0 0 1
0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1
↑ ↑ ↑
i=4 Y i=4 Y i=4 Y

1. The text index i and the pattern index j are initially set to 1, and the first characters
compared. There is a match.

2. The pattern index j is incremented to 2, and the pattern and text characters j and
i + j − 1 compared. There is not a match.

3. The text index i is incremented to 2 and the pattern index j reset to 1. There is
not a match in the corresponding characters.

4. The text index i is incremented to 3 and the pattern index j left at 1. There is a
match.

5. The pattern index j is incremented to 2, and the pattern and text characters j and
i + j − 1 compared. There is a match.

6. The pattern index j is incremented to 3, and the pattern and text characters j and
i + j − 1 compared. There is not a match.

7. The text index i is incremented to 4 and the pattern index j reset to 1. There is a
match.

8. The pattern index j is incremented to 2, and the pattern and text characters j and
i + j − 1 compared. There is a match.

9. The pattern index j is incremented to 3, and the pattern and text characters j and
i + j − 1 compared. There is a match, and the pattern is found.

6
Example 2. Algorithm Testing Whether a Positive Integer is Prime
This algorithm finds whether a positive integer is prime or composite.
Input: m, a positive integer
Output: true, if m is prime; false, if m is not prime
is prime(m) {
√
for i = 2 to m
if (m mod i == 0)
return false
return true
}
√
Note that the modulus operation need √ only go up to m, since if m is not prime, one
factor will be less than or equal to m and one factor will be greater than or equal to
√
m. If i mod m is 0, then i divides m, false is returned, and function is terminated. If
the for loop runs to its conclusion, control passes to the fifth line and true is returned.

Example 3. Algorithm Finding a Prime Larger Than a Given Integer

This algorithm finds the first prime larger than a given positive integer.
Input: n, a positive integer
Output: m, the smallest prime greater than n
large prime(n) {
m=n+1
while (¬ is prime(m) )
m=m+1
return m
}
The algorithm starts with m = n + 1, calls the function is prime to test if m is prime,
and continually increments m in a while loop as long as m is not prime. If the function
is prime returns false, then ¬ false is true, and the while loop continues. If the function
is prime returns true, then ¬ true is false, the while loop terminates, and m is returned.

7
Analysis of Algorithms

Analysis of an algorithm involves deriving estimates or storage space to execute an algo-

rithm. Time is more crucial. The following table shows how time varies in the execution
of an algorithm with the size of the input and the complexity of the algorithm. Note that
lg n means the logarithm to the base 2 of n. We can see from the table, for example, that
with an input of size n = 106 , the time to execute is 20 seconds if the algorithm behaves
as n lg n, and twelve days if the algorithm behaves as n2 .
This has real implications. Cooley and Tukey derived the Fast Fourier Transform algo-
rithm in the 1960’s, which reduced the time for a numerical discrete Fourier transform
from behaving as n2 to behaving as n lg n.
Real-life algorithms are checked for the amount of time to execute. For example, it is
pointless to have an air traffic control algorithm that takes two hours to run if an update
is required every 15 minutes.
Suppose that we measure the size of the “input” as n.
Best-case time
The minimum time needed to execute the algorithm among all inputs of size n.
Worst-case time
The maximum time needed to execute the algorithm among all inputs of size n.
Average-case time
The average time needed to execute the algorithm among all inputs of size n.
Example 1.
(a) The algorithm is to find the largest element in a sequence.
The number of iterations of a while loop (or comparisons) is n − 1 for input of size
n in all three cases.
(b) Search for a key word in a list of size n.
The best-case time is 1 if the key word is first in the list.
The worst-case time is n if the key word is last in the list, or not there at all.
The average-case time is the sum of all n + 1 cases, where the key word is in position
i, i = 1, 2, . . . , n in the list or not there at all. This is
1+2+3+ ··· +n+n n(n + 1)/2 + n
=
n+1 n+1
2
n + 3n
= .
2(n + 1)

(c) A set X contains red items and black items. Count all subsets that contain at least
one red item. Since there are 2n subsets, the time taken behaves as 2n .
(d) In the travelling salesperson problem, the salesperson visits n towns in some order.
There are 12 (n − 1)! possible tours of n towns.
Question: Which grows the faster, 2n or 21 (n − 1)! .

8
 Number of Steps
for Input Time to Execute if n =
of Size n 3 6 9 12
1 10 sec
−6
10 sec
−6
10 sec
−6
10 sec
−6

lg lg n 10−6 sec 10 sec

−6
2 × 10−6 sec 2 × 10−6 sec
lg n 2 × 10−6 sec 3 × 10 sec
−6
3 × 10−6 sec 4 × 10−6 sec
n 3 × 10−6 sec 6 × 10−6 sec 9 × 10−6 sec 10−5 sec
n lg n 5 × 10−6 sec 2 × 10 sec
−5
3 × 10−5 sec 4 × 10−5 sec
n2 9 × 10−6 sec 4 × 10−5 sec 8 × 10−5 sec 10−4 sec
n3 3 × 10−5 sec 2 × 10−4 sec 7 × 10−4 sec 2 × 10−3 sec
2n 8 × 10−6 sec 6 × 10 sec
−5
5 × 10−4 sec 4 × 10−3 sec

Number of Steps
for Input Time to Execute if n =
of Size n 50 100 1000
1 10 sec
−6
10 sec
−6
10 sec
−6

lg lg n 2 × 10−6 sec 3 × 10−6 sec 3 × 10−6 sec

lg n 6 × 10−6 sec 7 × 10−6 sec 10−5 sec
n 5 × 10−5 sec 10−4 sec 10−3 sec
n lg n 3 × 10−4 sec 7 × 10−4 sec 10−2 sec
n2 3 × 10−3 sec 0.01 sec 1 sec
n3 0.13 sec 1 sec 16.7 min
2n 36 yr 4 × 1016 yr 3 × 10287 yr

Number of Steps
for Input Time to Execute if n =
5
of Size n 10 106
1 10−6 sec 10−6 sec
lg lg n 4 × 10−6 sec 4 × 10−6 sec
lg n 2 × 10−5 sec 2 × 10−5 sec
n 0.1 sec 1 sec
n lg n 2 sec 20 sec
n2 3 hr 12 days
n3 32 yr 31, 710 yr
2n 3 × 1030089 yr 3 × 10301016 yr

TABLE 4.3.1 Time to execute an algorithm if one step takes 1 microsecond to execute.

9
Often we are less interested in the best- or worst-case times for an algorithm to execute
than in how the times grow as n increases.

Example 2. Suppose the worst-case time is

n3 n
t(n) = + n2 − .
3 3
Then for n = 10, 100, 1, 000, 10, 000 we have the table

n n3 /3 + n2 − n/3 n3 /3
10 430 333
100 343, 300 333, 333
1, 000 334, 333, 000 333, 333, 333
10, 000 3.334 × 1011 3.333 × 1011

For large n,
n3
t(n) ≈ .
3
Hence t(n) is of order n3 , ignoring the constant 31 .

Definition. Let f and g be functions with domain { 1, 2, 3, . . . }.

We write
f (n) = O(g(n))
and say that f (n) is of order at most g(n) or f (n) is big oh of g(n) if there exists a
positive constant C1 such that
|f (n)| ≤ C1 |g(n)|
for all but finitely many positive integers n.
We write
f (n) = Ω(g(n))
and say that f (n) is of order at least g(n) or f (n) is omega of g(n) if there exists a positive
constant C2 such that
|f (n)| ≥ C2 |g(n)|
for all but finitely many positive integers n.
We write
f (n) = Θ(g(n))
and say that f (n) is of order g(n) or f (n) is theta of g(n) if f (n) = O(g(n)) and f (n) =
Ω(g(n)).

10
Example 3. f (n) = 4n + 3. Then

f (n) ≤ 4n + 3n
= 7n,

so f (n) = O(n). Also

f (n) ≥ 4n,

so f (n) = Ω(n).
Therefore f (n) = Θ(n).

Example 4. f (n) = 2n2 + 3n + 1. Then

f (n) ≤ 2n2 + 3n2 + n2

= 6n2 ,

so f (n) = O (n2 ). Also

f (n) ≥ 2n2 ,

so f (n) = Ω (n2 ).
Therefore f (n) = Θ (n2 ).
n3 n
Example 2. (Continued) t(n) = + n2 − .
3 3
n3
t(n) ≤ + n2
3
n3
≤ + n3
3
4 3
= n,
3
so t(n) = O (n3 ). Also

n3 n2
t(n) ≥ + n2 −
3 3
3
n 2
= + n2
3 3
n3
≥ ,
3
so t(n) = Ω (n3 ).
Therefore t(n) = Θ (n3 ).

Exercise: Try f (n) = 4n3 − n2 + 2n.

11
Theorem 4.3.4 Let

p(n) = ak nk + ak−1 nk−1 + · · · + a1 n + a0

be a polynomial in n of degreee k, where each ai is nonnegative (and ak 6= 0). Then

 
p(n) = Θ nk .

Proof:
p(n) = ak nk + ak−1 nk−1 + · · · + a1 n + a0
≤ ak nk + ak−1 nk + · · · + a1 nk + a0 nk
= (ak + ak−1 + · · · + a1 + a0 ) nk
= C1 nk ,
 
so p(n) = O nk . Also

p(n) ≥ ak nk ,
 
so p(n) = Ω nk .
 
Therefore t(n) = Θ nk .

y
y = 2n
256
y = n2
128

64 y = n lg n

32

16 y=n

8
y = lg n
4

2
y=1
1

1 2 3 4 5 6 7 8 9 10 11 12 13 n

Figure 4.3.1 Growth of some common functions.

12
Example 5. f (n) = 2n + 3 lg n.
Remember that lg n represents log2 n.
Does your calculator have an lg button? If not,

y = lg n
n = 2y
ln n = ln (2y )
= y ln 2, so
ln n
y = .
ln 2
Now lg n < n for all n ≥ 1. (See the preceding graph). Therefore

f (n) = 2n + 3 lg n
< 2n + 3n
= 5n,

so f (n) = O (n). Also

f (n) ≥ 2n,

so f (n) = Ω (n).
Therefore f (n) = Θ (n).
Example 6. f (n) = 1 + 2 + 3 + · · · + (n − 1) + n.
n(n + 1)
This example assumes that we don’t know that the sum is .
2
1 + 2 + 3 + · · · + (n − 1) + n ≤ n + n + n + · · · + n + n
= n2 ,

so f (n) = O (n).
Also

1 + 2 + 3 + · · · + (n − 1) + n ≤ 1 + 1 + 1 + · · · + 1 + 1
= n,

so f (n) = Ω (n).
This seems to be too low an estimate. We can do better. Let’s be trickier, and throw
away approximately the first half of the series.
n n
   
1 + 2 + 3 + · · · + (n − 1) + n ≥ + + 1 + · · · + (n − 1) + n
2 2
n n n
     
≥ + + ··· + .
2 2 2

How many terms are there?

13
 n+1
 
If n = 8 4 + 5 + 6 + 7 + 8 = 5 terms i.e. .
2
n+1
 
If n = 9 5 + 6 + 7 + 8 + 9 = 5 terms i.e. .
2
If n = 2k k + (k + 1) + · · · + 2k = 2k − (k − 1) = k + 1 terms.
If n = 2k + 1 (k + 1) + (k + 2) + · · · + (2k + 1) = (2k + 1) − k = k + 1 terms.
n+1
 
Hence there are terms. Therefore
2
n+1 n
   
f (n) ≥
2 2
n n
≥ ·
2 2
n2
= ,
4
so f (n) = Ω (n2 ).
Therefore f (n) = Θ (n).
n(n + 1)
If we know that f (n) = , then
2

f (n) = 12 n2 + 1
2n
≤ 12 n2 + 1 2
2n
= n2 ,

so f (n) = O (n2 ).
Also

f (n) ≥ 12 n2 ,

so f (n) = Ω (n2 ).
Therefore f (n) = Θ (n2 ).

14
Discrete Mathematics: Week 7
Analysis of Algorithms (Continued)

Example 7. We can generalize Example 6 to nk .

f (n) = 1k + 2k + 3k + · · · + (n − 1)k + nk .
Now

f (n) = 1k + 2k + 3k + · · · + (n − 1)k + nk
≤ nk + nk + nk + · · · + nk + nk
= n × nk
= nk+1 .
 
So f (n) = O nk+1 .

n k n k
   
f (n) ≥ + + 1 + · · · + (n − 1)k + nk
2 2
n n n
 k  k  k
≥ + + ··· +
2 2 2
n+1 n
   k
=
2 2
n+1 n
   k
≥
2 2
1 h i
= (n + 1)n k
2k+1
1  k+1 
= n + nk
2k+1
1 k+1
≥ n .
2 k+1

 
So f (n) = Ω nk+1 .
 
.·. f (n) = Θ nk+1 .

Example 8. What is the order of n! ?

What is n! ? The basic definition is

n! = n × (n − 1) × (n − 2) × · · · × 3 × 2 × 1.

Hence 1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
1
etc.
My calculator runs out at 69! , as 70! > 10100 . What is the limit on your calculator?
Then 0! is defined to be 1. What is 1 12 ! ?
Stirling’s formula gives an approximation for n! :
√ n
 n
n! ≈ 2πn .
e
Hence
ln n! ≈ 12 ln 2π + 21 ln n + n ln n − n.
So we suspect that
lg n! = Θ (n lg n) .
Then, taking lg of n! ,

lg n! = lg n + lg (n − 1) + · · · + lg 2 + lg 1
≤ lg n + lg n + · · · + lg n + lg n
= n lg n.

So n! = O (n lg n). Finding a lower limit,

n
 
lg n! ≥ lg n + lg (n − 1) + · · · + lg
2
n n n
     
≥ lg + lg + · · · + lg
2 2 2
n+1 n
   
= lg
2  2
n n
≥ lg
2 2
n
= (lg n − lg 2)
2" #
n lg n lg n
= + −1
2 2 2
n
≥ lg n, as for n ≥ 4, lg n ≥ 2.
4
So lg n! = Ω (n lg n).
.·. lg n! = Θ (n lg n).

Definition. If an algorithm requires t(n) units of time to terminate in the best case for
an input of size n, and
t(n) = O (g(n)) ,
we say that the best-case time required by the algorithm is of order at most g(n) or that
the best-case time required by the algorithm is O (g(n)).
If an algorithm requires t(n) units of time to terminate in the worst case for an input of
size n, and
t(n) = O (g(n)) ,

2
we say that the worst-case time required by the algorithm is of order at most g(n) or that
the worst-case time required by the algorithm is O (g(n)).
If an algorithm requires t(n) units of time to terminate in the average case for an input
of size n, and
t(n) = O (g(n)) ,
we say that the average-case time required by the algorithm is of order at most g(n) or
that the average-case time required by the algorithm is O (g(n)).
Replace O by Ω and “at most” by “at least” to obtain the definition of what it means
for the best-case, worst-case or average-case time of an algorithm to be of order at least
g(n).
If the best case time is O (g(n)) and Ω (g(n)), then the best-case time required by the
algorithm is Θ (g(n)).
Similar definitions apply for the worst-case and average-case times.
Example 1. (b) (Continued)
Johnsonbaugh Algorithm 4.3.17. Searching for a key in an unordered sequence.
The best-case time is 1 i.e. Θ(1).
The worst-case time is n i.e. Θ(n).
The average-case time is
(1 + 2 + 3 + · · · + n) + n n2 + 3n
=
n+1 2(n + 1)
i.e. Θ(n).
Example 9. Consider the pseudocode
for i = 1 to n
for j = 1 to i
x=x+1
Find a theta notation for the number of times the statement x = x + 1 is executed.
The number of times is
1 + 2 + 3 + · · · + n = 12 n2 + 12 n,
which is Θ(n2 ).
Example 10. Consider the pseudocode
i=n
while (i ≥ 1) {
x=x+1
i = ⌊ i/2 ⌋
}
Find a theta notation for the number of times the statement x = x + 1 is executed.

3
Suppose that n = 8. Then for
i=8 x=x+1 is executed
i=4 x=x+1 is executed
i=2 x=x+1 is executed
i=1 x=x+1 is executed
i=0 x=x+1 is not executed.

So the statement is executed 4 times.

Suppose n = 2k . Then the statement is executed for
i = 2k , 2k−1, 2k−2, . . . , 2, 20 = 1,
i.e. k + 1 = 1 + lg n times.
If
2k ≤ n < 2k+1 ,
then after k iterations
n
 
1≤i= < 2.
2k
So for all n, x = x + 1 is executed 1 + lg n times, which is Θ(lg n).
Example 11. Find a theta notation for the number of times the statement x = x + 1 is
executed in the following pseudocode.
j=n
while (j ≥ 1) {
for i = 1 to j
x=x+1
j = ⌊ j/2 ⌋
}
Let t(n) denote the number of times the statement x = x + 1 is executed.
The first time in the while loop, it is executed n times.
.·. t(n) ≥ n, and t(n) = Ω(n).
The second time in the while loop, the statement is executed j = ⌊ j/2 ⌋ times, and so
on. Hence
n n n n
t(n) ≤ n + + + + · · · + k−1 ,
2 4 8 2
n
where k < 1. So
2
n 1 − 21k
 

t(n) ≤
1 − 21
= 2n 1 − 21k
 

≤ 2n.

4
.·. t(n) = O(n).
.·. t(n) = Θ(n).

A “good” algorithm has a worst-case polynomial time, and such problems are called
feasible or tractable problems. Exponential or factorial worst-case time problems are
called intractable, and require a long time to execute even for reletively small n.
There are problems for which there is no algorithm. These are called unsolvable. Such a
problem is the halting problem: given an arbitrary program and a set of inputs, will the
program ever halt?
A large number of solvable problems have an undetermined status. They are thought to
be intractable, but none have ever been proved to be intractable. Such a problem is the
travelling salesperson problem.

5
Recursive Algorithms

A recursive function invokes itself. A recursive algorithm is an algorithm that contains a

recursive function.

Example 1. Factorials. Johnsonbaugh Example 4.4.1

We know that n! = n(n − 1)!, and that 0! is defined as 1. We can resolve the problem
of computing n! into the simpler problem of computing (n − 1)!, then into computing
(n − 2)! and so on, until we get to 0! which is known i.e.

Problem Simplified Problem

5! 5 · 4!
4! 4 · 3!
3! 3 · 2!
2! 2 · 1!
1! 1 · 0!
0! None
Table 1: Decomposing the factorial problem.

Problem Solution
0! 1
1! 1 · 0! = 1
2! 2 · 1! = 2
3! 3 · 2! = 6
4! 4 · 3! = 24
5! 5 · 4! = 120

Table 2: Combining subproblems of the factorial problem.

Algorithm 4.4.2 Computing n Factorial

This recursive algorithm computes n!.
Input: n, an integer greater than or equal to 0
Output: n!

1. factorial (n) {

2. if (n == 0)

3. return 1

4. return n∗factorial (n − 1)

5. }

6
We can see how the algorithm computes n!.
If n = 1, proceed to line 4 since n 6= 0, and compute

n · (n − 1)! = 1 · 0! = 1 · 1 = 1.

If n = 2, proceed to line 4 since n 6= 0, and compute

n · (n − 1)! = 2 · 1! = 2 · 1 = 2,

and so on.

Theorem: Algorithm 4.4.2 returns the value of n! , n ≥ 0.

Proof: Basis Step: For n = 0, the algorithm correctly returns 1.
Inductive Step: Assume that the algorithm correctly returns the value of (n − 1)! , n > 0.
Suppose n is input to the algorithm. Since n > 0, proceed to line 4. By the assumption,
the algorithm correctly computes (n − 1)! . Hence the algorithm correctly computes n! =
n · (n − 1)! .
Recursive algorithms and their proof go hand-in-hand with mathematical induction.

Example 2. This algorithm recursively finds the smallest of a finite sequence of numbers.
Algorithm Recursively Finding the Minimum Value in a Sequence
This algorithm finds the smallest of the numbers s1 , s2 , . . . , sn .
Input: s, n
Output: small, (the smallest value in the sequence s)
min(s, n) {
if (n == 1) {
small = s1
return small
}
else {
small = min(s, n − 1)
if small ≤ sn
return small
else {
small = sn
return small
}
}
}

7
If n = 1, there is only one number in the sequence, and it is returned.
If n = 2, then min(s, 1) is recursively called, and this returns s1 . This is compared with
s2 , and the smaller returned.
If n = 3, then min(s, 2) is recursively called, and this recursively calls min(s, 1), which
returns s1 . Then min(s, 2) returns the smaller of s1 and s2 , and this is compared with s3
and the smaller returned.

Theorem: This algorithm correctly returns the value of the smallest of a finite sequence
of numbers.
Proof: Basis Step: For n = 1, the algorithm returns the only number in the sequence.
Inductive Step: Assume that the algorithm correctly returns the smallest value in sequence
of length n − 1.
Then for a sequence of length n, n > 1, the algorithm correctly computes the smallest of
s1 , s2 , . . . , sn−1 , compares this with sn , and returns the smaller.
Therefore the algorithm correctly returns the smallest number in a sequence of length n.

Example 3. Robot walk. Johnsonbaugh Example 4.4.5

A robot can take steps of 1 metre or 2 metres. In how many ways can the robot walk n
metres? Let walk (n) denote the number of ways. Then walk (1) = 1 and walk (2) = 2.

Distance Sequence of Steps Number of Ways to Walk

1 1 1
2 1, 1 or 2 2
3 1, 1, 1 or 1, 2 or 2, 1 3
4 1, 1, 1, 1 or 1, 1, 2 5
or 1, 2, 1 or 2, 1, 1 or 2, 2

Suppose n > 2. Then

walk (n) = walk (n − 1) + walk (n − 2).

Algorithm 4.4.6 Robot Walking

This algorithm computes the function defined by


 1, n=1
walk (n) = 2, n=2
walk (n − 1) + walk (n − 2), n > 2.



Input: n
Output: walk (n)
walk (n) {
if (n == 1 ∨ n == 2)

8
 return n
return walk (n − 1) + walk (n − 2)
}
We can see that the sequence generated is

1, 2, 3, 5, 8, 13, 21, 34, 55, . . . .

This is the Fibonacci sequence {fn }, and is defined by the equations

f1 = 1
f2 = 1
fn = fn−1 + fn−2 , for all n ≥ 3.

The Fibonacci sequences arises in many natural situations, as well as mathematical ones.
For example, a pine cone can have 13 clockwise spirals and 8 counterclockwise spirals.
The ratio of successive terms in the Fibonacci sequence has a limit of the golden ratio,
√
lim fn 1 + 5
n → ∞ fn−1 = φ = 2
= 1.6180339887498 . . . .

55
For example, = 1.6176 . . . .
34
A classical formula for the Fibonacci numbers is
" √ !n √ !n #
1 1+ 5 1− 5
√ − .
5 2 2
√
All those 5 occurrences, and the answer is an integer!

9
Discrete Mathematics: Week 8

Graph Theory
Introduction to Graphs

Graph theory was introduced by Leonhard Euler in 1736, as a means of solving the
Königsberg bridge problem. There was a revival of graph theory in the 1920’s, with the
first text produced in 1936. Graph theory involves a lot of terminology, as will be seen.
A graph is drawn with dots and lines, the dots being vertices and the lines are edges. The
important information in the graph is the connections, not the positions of the vertices
and edges.

Example 1. The following two graphs contain the same information.

v1

v1 e1 v2
e2 e1 v3 e6
e3
e6 e4 v3 e2
e5
v4
e3 e4
v5 v4 v2 e5 v5

A path starts at one vertex v1 , travels along an edge to vertex v2 , and so on, arriving at
vn .
For a path to traverse every edge exactly once, and return to the original vertex, an even
number of edges must touch each vertex, for example, the graph in Example 1. In the
graph shown below, a path can traverse each edge exactly once, but will not return to the
original vertex.

v1 v2

v4 v3

Definition 8.1.1
A graph (or undirected graph) G consists of a set V of vertices (or nodes) and a set E of
edges (or arcs) such that each edge e ∈ E is associated with an unordered pair of vertices.
If there is a unique edge e associated with the vertices v and w, we write e = (v, w) or

1
e = (w, v). In this context, (v, w) denotes an edge between v and w in an undirected
graph and not an ordered pair.
A directed graph (or digraph) G consists of a set V of vertices (or nodes) and a set E of
edges (or arcs) such that each edge e ∈ E is associated with an ordered pair of vertices. If
there is a unique edge e associated with ordered pair (v, w) of vertices, we write e = (v, w),
which denotes an edge from v to w.
An edge e in a graph (undirected or directed) that is associated with the pair of vertices
v and w is said to be incident on v and w, and v and w are said to be incident on e and
to be adjacent vertices.
If G is a graph (undirected or directed) with vertices V and edges E, we write G = (V, E).
Unless specified otherwise, the sets E and V are assumed to be finite and V is assumed
to be nonempty.
Example 1. (Continued)
V = { v1 , v2 , v3 , v4 , v5 }
E = { e1 , e2 , e3 , e4 , e5 , e6 }
e2 = (v2 , v3 ) = (v3 , v2 )
Edge e4 is incident on vertices v2 and v4 , and vertices v2 and v4 are adjacent.
Example 2. The graph shown below is a directed graph.

v1

e1
e3
v2 v3
e4
v4
e2 e5
e6
v6
v5
e7
v7

Directed edges are indicated by arrows.

Edge e1 is associated with the ordered pair (v2 , v1 ) of vertices.
Distinct edges can be associated with the same pair of vertices e.g. e3 and e4 . These are
parallel edges, and can also occur in undirected graphs.

e1

v1 v2
e2

2
An edge incident on a single vertex is called a loop e.g. e7 .
A vertex not incident to any edge is called isolated e.g. v7 .
A graph with neither loops nor parallel edges is called a simple graph.

Example 3. Johnsonbaugh 8.1.5

Holes are being bored in a sheet of metal by a drill press, and these can be considered
as the vertices of a graph. There is a travel time associated with every edge between
vertices, so that we have a weighted graph. This is shown in the diagram below.

b
8
a 8 b
a
6
6
2
6 9 2 6 9
4
c
3
4 12
d 5
e 5 c
4
e
4 3
12
d

If an edge e is labelled k, we say that the weight of edge e is k.

The length of a path is the sum of the weighted edges in a path. A path of minimum
length that visits each vertex exactly once represents the optimum path for the drill press.
For example, for a path starting at b and finishing at e, we have path lengths:

Path Length
b, a, c, d, e 17
b, a, d, c, e 20
b, c, a, d, e 16
b, c, d, a, e 19
b, d, a, c, e 23
b, d, c, a, e 23

Additionally, all starting and finishing vertices need to be checked:

(a, b), (a, c), (a, d), (a, e), (b, c), (b, d), (b, e), (c, d), (c, e), (d, e).

It is expected that the reverse path will be of the same length.

3
Example 4. Johnsonbaugh Example 8.1.7: Similarity Graphs.
A particular algorithm in C++ is implemented by a number of persons. We wish to group
“like” programs into classes based on program properties. The properties are:

1. The number of lines in the program

2. The number of return statements in the program

3. The number of function calls in the program.

Number of Number of Number of

Program program lines return statements function calls
1 66 20 1
2 41 10 2
3 68 5 8
4 90 34 5
5 75 12 14

A similarity graph is constructed with vertices corresponding to the programs. A vertex

is denoted (p1 , p2 , p3 ) where pi is the value of property i.
A dissimilarity function s is defined as follows. For each pair of vertices v = (p1 , p2 , p3 )
and w = (q1 , q2 , q3 ) set

s(v, w) = |p1 − q1 | + |p2 − q2 | + |p3 − q3 | .

In this example, we have

s (v1 , v2 ) = 36 s (v2 , v3 ) = 38 s (v3 , v4 ) = 54

s (v1 , v3 ) = 24 s (v2 , v4 ) = 76 s (v3 , v5 ) = 20
s (v1 , v4 ) = 42 s (v2 , v5 ) = 48 s (v4 , v5 ) = 46
s (v1 , v5 ) = 30

For a fixed number S, inset an edge between vertices v and w if s(v, w) < S. For example,
if S = 25 we have the graph:

v1 v2

v3

v4 v5

We say that v and w are in the same class if v = w or if there is a path from v to w. Here
the classes are { 1, 3, 5 }, { 2 } and { 4 }. What are the classes if S = 40?

4
Definition 8.1.9
The complete graph on n vertices, denoted Kn , is the simple graph with n vertices in
which there is an edge between each pair of distinct vertices.

Example 5. The complete graph, K4 , on 4 vertices is:

Definition 8.1.11
A graph G = (V, E) is bipartite if there exist subsets V1 and V2 (either possibly empty)
of V such that V1 ∩ V2 = ∅, V1 ∪ V2 = V , and each edge in E is incident on one vertex in
V1 and one vertex in V2 .

Example 6. The graph in the figure below is bipartite for

V1 = { v1 , v2 , v3 } and V2 = { v4 , v5 } .

v1
v4
v2
v5
v3

Note that it is not required that there is an edge between every vertex in V1 and every
vertex in V2 .

Example 7. The graph in the following figure is not bipartite.

v1 v2

v3 v7
v4

v5 v6

v8 v9

5
It is often easier to prove that a graph is not bipartite by arguing a contradiction.
Suppose the graph is bipartite. Then we can partition the set of vertices into two subsets
V1 and V2 .
Consider v4 , v5 and v6 . Since v4 and v5 are adjacent, v4 is in V1 (say) and v5 is in V2 .
Since v5 and v6 are adjacent, v6 is in V1 .
But v4 and v6 are adjacent and both are in V1 . Contradiction. Hence the graph is not
bipartite.

Definition 8.1.15
The complete bipartite graph on m and n vertices, denoted Km,n , is the simple graph
whose vertex set is partitioned into sets V1 with m vertices and V2 with n vertices in
which the edge set consists of all edges of the form (v1 , v2 ) with v1 ∈ V1 and v2 ∈ V2 .

Example 8. The complete bipartite graph on two and four vertices, K2,4 , is:

6
Paths and Cycles

Definition 8.2.1
Let v0 and vn be vertices in a graph. A path from v0 to vn of length n is an alternating
sequence of n + 1 vertices and n edges beginning with vertex v0 and ending with vertex
vn ,
(v0 , e1 , v1 , e2 , v2 , . . . vn−1 , en , vn ),
in which edge ei is incident on vertices vi−1 and vi for i = 1, . . . , n.
The formalism in Definition 8.2.1 means: Start at vertex v0 ; go along edge e1 to v1 ; go
along edge e2 to v2 ; and so on.
Definition 8.2.4
A graph G is connected if given any vertices v and w in G, there is a path from v to w.
Example 1. Consider the following graph.
v2
e11
v1
e10 v7
e2

e1 e12
v4 e9
v6
v3 e3 e5
e4
e6

v5
e8 v9
e7
v8

Paths joining v1 and v2 are (v1 , v4 , v2 ) of length 2 and (v1 , v4 , v5 , v6 , v7 , v2 ) of length 5.

The graph is connected.
The graph
e1
v1 v4
v2 e2
v5
v3 e3

is not connected.

A connected graph consists of one “piece”, and a graph that is not connected consists of
two or more “pieces”. These “pieces” are subgraphs of the original graph called compo-
nents.

7
Definition 8.2.8
Let G = (V, E) be a graph. We call (V ′ , E ′ ) a subgraph of G if

(a) V ′ ⊆ V and E ′ ⊆ E.

(b) For every edge e′ ∈ E ′ , if e′ is incident on v ′ and w ′ , then v ′ , w ′ ∈ V ′ .

Example 1. (Continued) A subgraph is

v2
e11
v1
v7
e2

e1 v4

v3 e3
e4

v5

Definition 8.2.11
Let G be a graph and let v be a vertex in G. The subgraph G′ of G consisting of all edges
and vertices in G that are contained in some path beginning at v is called the component
of G containing v.
A connected graph, such as Example 1, has only one component, itself.
A graph such as
e1
G1 : v1 v4
e1
v1 v4 and
has two
G: v2 e2 components G2 : v2 e2
v5 v5
v3 e3 v3 e3

has two components G1 and G2 .

We describe G2 as G2 = (V2 , E2 ) with V2 = { v2 , v3 , v5 } and E2 = { e2 , e3 }.
Definition 8.2.14
Let v and w be vertices in a graph G.

A simple path from v to w is a path from v to w with no repeated vertices.

A cycle (or circuit) is a path of nonzero length from v to v with no repeated edges.

8
 A simple cycle is a cycle from v to v, in which, except for the beginning and ending
vertices that are both equal to v, there are no repeated vertices.
Example 1. (Continued)

Path Simple Path? Cycle? Simple Cycle?

(v1 , v4 , v5 , v6 , v5 )
(v1 , v4 , v6 , v7 , v2 )
(v4 , v1 , v3 , v5 , v4 , v6 , v7 , v2 , v4 )
(v4 , v5 , v6 , v7 , v2 , v4 )
(v4 )

The Königsberg Bridge Problem

Two islands in the Pregel River in Königsberg (now Kaliningrad in Russia) were connected
to each other and the river banks by seven bridges, as shown in the diagram below.

Pregel
B C
River

The problem is to start at any location, walk over each bridge exactly once, and finish at
the starting location.
Leonhard Euler solved the problem in 1736. The problem can be represented as the
following graph, where the vertices represent the locations and the edges represent the
bridges.

B C

9
Euler showed that there is no solution, as all vertices have an odd number of incident
edges.
A cycle in graph G that includes all of the edges and all of the vertices of G is called an
Euler cycle, in honour of Euler.
We introduce the idea of the degree of a vertex v, δ(v). This is the number of edges
incident on v.
Theorem 8.2.17
If a graph G has an Euler cycle, then G is connected and every vertex has even degree.
Proof: Suppose that G has an Euler cycle.
We have seen the argument that during the cycle, the path leaves each vertex for every
time that it is entered, and so all vertices must be of even degree.
If v and w are vertices of G, then the portion of the Euler cycle between v and w is a
path from v to w, and so G is connected.
Theorem 8.2.18
If G is a connected graph and every vertex has even degree, then G has an Euler cycle.
Proof: Johnsonbaugh gives a mathematical induction proof. See the text.
Example 2. For the Königsberg bridge problem,
δ(A) = 3, δ(B) = 5, δ(C) = 3, δ(D) = 3,
so there is not an Euler cycle.
If the graph G is as shown below, then G is connected an every vertex has even degree.
δ (v1 ) = δ (v2 ) = δ (v3 ) = δ (v5 ) = 4, δ (v4 ) = 6, δ (v6 ) = δ (v7 ) = 2.
v1

v2

v4
v3 v5

v6 v7

Hence an Euler cycle exists. By inspection, one is

(v6 , v4 , v7 , v5 , v1 , v3 , v4 , v1 , v2 , v5 , v4 , v2 , v3 , v6 ) .

10
Theorem 8.2.21
If G is a graph with m edges and vertices {v1 , v2 , . . . , vn }, then
n
X
δ(vi ) = 2m.
i=1

In particular, the sum of degrees of all of the vertices of the graph is even.
Proof: Each edge is counted twice, once from vi to vj , and once from vj to vi .
Corollary 8.2.22
In any graph, there are an even number of vertices of odd degree.
Theorem 8.2.23
A graph has a path with no repeated edges from v to w (v 6= w) containing all the edges
and vertices if and only if it is connected and v and w are the only vertices of odd degree.
For example, the graph below.

v1

v2 v5

v3 v4

Proof: Add an edge from v to w. Now thare is an Euler cycle as all vertices are of even
degree.
Theorem 8.2.24
If a graph G contains a cycle from v to v, G contains a simple cycle from v to v.
Proof: If C is a cycle from v0 to vn (v0 = vn ), and C is not a simple cycle, then there
must be vertices vi = vj in the path where i < j < n. Remove the portion of the path
between vi and vj , and repeat the procedure if necessary. The cycle is eventually reduced
to a simple cycle.

11
Discrete Mathematics: Week 9

Trees
Introduction

Example 1. Johnsonbaugh example on the draw for the semifinals and finals at Wim-
bledon (many years ago).

Seles
Seles
Navratilova
Graf
Sabatini
Graf WIMBLEDON
CHAMPION
Graf
FINALS
SEMIFINALS

The draw can be represented as a graph called a tree. It is rotated clockwise through 90◦
so as to appear as is shown on the right. If it is rotated through 90◦ the other way then
it would appear as a natural tree.

v4 height = 2
v2
v1
v5 level 0
v1 v2 v3
v6 level 1

v3 level 2
v7 v4 v5 v6 v7

Definition 9.1.1
A (free) tree T is a simple graph satisfying the following: If v and w are vertices in T ,
then there is a unique simple path from v to w.
A rooted tree is a tree in which a particular vertex is designated the root.
The level of a vertex v is the length of the simple path from the root to v.
The height of a rooted tree is the maximum level number that occurs.

1
PSfrag replacemen
Example 2. Johnsonbaugh 9.1.4 The tree T shown below will become the rooted tree T ′
if we designate vertex e as the root.

i e
d
a b g
g
d f
b j
e i
a c h
h
f
c j

Huffman Codes
Character representation is often by fixed-length bit strings e.g. ASCII where eight bit
strings are used for the 256 extended character set.
Huffman codes represent characters by variable-length bit strings. Short bit strings are
used to represent the most frequently used characters.
A Huffman code is most easily defined by a rooted tree. To decode a bit string, begin at
the root and move down the tree until a character is encountered. The bit, 0 or 1, means
move right or left. When a character is encountered, begin again at the root.
Given a tree that defines a Huffman code, any bit string can be uniquely decoded even
though the characters are represented by variable-length bit strings.

Example 3. Decode the string 010101110110 from the following tree.

Root
1 0

A 1 0
O
1 0
R
1 0

T S

The string decodes as:

010 1 0111 0110

R A T S

2
 Algorithm 9.1.9 Constructing an Optimal Huffman Code
This algorithm constructs an optimal Huffman code from a table giving the frequency
of occurrence of the characters to be represented. The output is a rooted tree with the
vertices at the lowest levels labelled with the frequencies and with the edges labelled with
bits. The coding tree is obtained by replacing each frequency by a character having that
frequency.

Input: A sequence of n frequencies, n ≥ 2

Output: A rooted tree that defines an optimal Huffman code

huffman(f, n) {
if (n == 2) {
let f1 and f2 denote the frequencies
let T be as in the figure (on the left)
return T
}
let fi and fj denote the smallest frequencies
replace fi and fj in the list by fi + fj
T ′ = huffman(f, n − 1)
replace a vertex in T ′ labelled fi + fj by the
tree shown in the figure (on the right) to obtain the tree T
return T
}

1 0 1 0

f1 f2 fi fj
Example 4. We have the following table of frequencies.

Letter Frequency
A 10
B 12
C 17
D 8
E 22

3
The algorithm begins by repeatedly replacing the two smallest frequencies with the sum
until a two element sequence is obtained.

10, 12, 17, 8, 22 −→ 18, 12, 17, 22

A, B, C, D, E A + D, B, C, E

12, 17, 18, 22 −→ 29, 18, 22

B, C, A + D, E B + C, A + D, E

18, 22, 29 −→ 40, 29

A + D, E, B + C A + D + E, B + C

The algorithm then constructs trees working backward, beginning with the two element
sequence 29, 40.

1 0 1 0 1 0 1 0

29 40 29 1 0 1 0 1 0 1 0 1 0

18 22 12 17 18 22 12 17 1 0 22

8 10

Now replace each frequency by a character having that frequency.

1 0

1 0 1 0

B C 1 0 E

D A

Then BED is coded as 11 | 00 | 011.

4
Terminology and Characterizations of Trees

Definition 9.2.1
Let T be a tree with root v0 . Suppose that x, y and z are vertices in T and that
(v0 , v1 , . . . , vn ) is a simple path in T . Then

(a) vn−1 is the parent of vn .

(b) v0 , . . . , vn−1 are ancestors of vn .

(c) vn is a child of vn−1 .

(d) if x is an ancestor of y, y is a descendant of x.

(e) If x and y are children of z, x and y are siblings.

(f) If x has no children, x is a terminal vertex (or a leaf ).

(g) If x is not a terminal vertex, x is an internal (or branch) vertex .

(h) The subtree of T rooted at x is the graph with vertex set V and edge set E, where
V is x with the descendants of x and

E = {e | e is an edge on a simple path from x to some vertex in V }.

Example 1. consider the following tree.

g

e i
h
b
d f j

a c

The parent of b is: e

The ancestors of a are: b, e, g
The children of b are: a, c
The descendants of e are: d, f, b, a, c
The siblings of d are: f, b
The terminal vertices are: d, f, a, c, h, j
The internal vertices are: g, e, i, b

5
The subtree rooted at e is:
e

b
d f

a c

Example 2. Greek gods. Johnsonbaugh Example 9.2.2

Uranus

Aphrodite Kronos Atlas Prometheus

Eros Zeus Poseidon Hades Ares

Apollo Athena Hermes Heracles

The parent of Eros is:

The ancesters of Hermes are:
The children of Zeus are:
The descendants of Kronos are:
The siblings of Atlas are:
The terminal vertices are:
The internal vertices are:
The subtree rooted at Kronos is:

Kronos

Zeus Poseidon Hades Ares

Apollo Athena Hermes Heracles

6
Theorem 9.2.3
Let T be a graph with n vertices. The following are equivalent.

(a) T is a tree.

(b) T is connected and acyclic.

(c) T is connected and has n − 1 edges.

(d) T is acyclic and has n − 1 edges.

Partial proof: The proof is as follows. We show

if (a), then (b); if (b), then (c); if (c), then (d); if (d), then (a),

and so all must be equivalent.

We will show:
If (a), then (b).
Let T be a tree. Then T is connected as there is a simple path from any vertex to any
other vertex.
Suppose T contains a cycle. Then by a previous theorem, Theorem 8.2.24, T contains a
simple cycle i.e.
C = ( v0 , v1 , . . . , vn )
with v0 = vn .
C cannot be a loop since T is a simple graph (no loops or parallel edges). Hence C
contains at least two distinct vertices vi and vj with i < j.
The paths
( vi , vi+1 , . . . , vj ) and ( vi , vi−1 , . . . , v0 , vn−1 , . . . , vj )
are distinct simple paths from vi to vj , contradicting the definition of a tree.
Therefore, a tree cannot contain a cycle.

7
Spanning Trees Johnsonbaugh 9.3

Definition 9.3.1
A tree T is a spanning tree of a graph G if T is a subgraph of G that contains all of the
vertices of G.

Example 1. Johnsonbaugh Example 9.3.2

The spanning tree of the graph below is shown in black. Other spanning trees are possible.

a b

c d

e f

h
g

Theorem 9.3.4
A graph G has a spanning tree if and only if G is connected.
Proof:
If G has a spanning tree, G is connected.
If G is connected, progressively remove edges from cycles until G is acyclic.
This procedure is inefficient in practice.
Algorithm 9.3.6 Breadth-First Search for a Spanning Tree
This algorithm is formally given in Johnsonbaugh, but a more informal description of the
procedure is as follows.
Select an ordering, e.g. abcdef gh of the vertices of G.
Select the first vertex as the root e.g. a.
The tree T initially consists of the single vertex a and no edges.
Add to T all edges (a, x) and the vertices on which they are incident, x = b to h, that do
not produce a cycle when added to T . This gives all level 1 vertices.
Repeat with the vertices on level 1, then level 2, and so on, until no further edges can be
added.

8
Example 1. (Continued)
Select the ordering abcdef gh.
Select a as the root.
Add edges (a, b), (a, c), (a, g).

Add edges for vertices on level 1: b add (b, d)

c add (c, e)
g none

Add edges for vertices on level 2: d add (d, f )

e none

Add edges for vertices on level 3: f add (f, h)

Add edges for vertices on level 4: h none

The spanning tree is shown in the previous diagram.

Algorithm 9.3.7 Depth-First Search for a Spanning Tree

This algorithm is formally given in Johnsonbaugh, but a more informal description of the
procedure is as follows.
Select an ordering, e.g. abcdef gh of the vertices of G.
Select the first vertex as the root e.g. a, the current vertex.
At each step, add to the tree an edge incident to the current vertex that doesn’t create a
cycle, using the vertex order to prioritize. Make the new vertex the current vertex.
If an edge can’t be added, backtrack by making the parent the current vertex.
Continue until the current vertex is again the root.
Example 1. (Continued)

a b

c d

e f

h
g

9
Select the ordering abcdef gh.
Select a as the root.
Add edges (a, b), (b, d), (d, c), (c, e), (e, f ), (f, h).
Backtrack to f , then e. Add (e, g).
Backtrack to e, c, d, b, a. Ends.

Minimal Spanning Trees Johnsonbaugh 9.4

Definition 9.4.1
Let G be a weighted graph. A minimal spanning tree of G is a spanning tree of G with
minimum weight.

Example 1. There are six cities 1–6, and the costs of building roads between certain
pairs of them are shown on the following graph.

1 4 2

3 2 5

1
4
3
5 6
3
6
2
6

Breadth-First Search Select the order 123456.

Select 1 as the root.
Add edges (1, 2), (1, 3), (1, 5).

Add edges for vertices on level 1: 2 add (2, 4)

3 add (3, 6)
5 none

Add edges for vertices on level 2: 4 none

6 none

The weight is 17, and the spanning tree is as shown below.

10
 1 4 2

3 2 5

4
3
5
3

Prim’s Algorithm Johnsonbaugh Algorithm 9.4.3

This algorithm is formally given in Johnsonbaugh, but a more informal description of the
procedure is as follows.
The algorithm begins with a single vertex. At each iteration, add to the current tree a
minimum weight edge that does not complete a cycle.

Example 1. (Continued)
Begin with vertex 1. Edges with one vertex in the tree and one vertex not in the tree are:
Edge Weight
(1, 2) 4
Select edge (1, 3)
(1, 3) 2
with minimum weight.
(1, 5) 3
Edges with one vertex in the tree and one vertex not in the tree are:
Edge Weight
(1, 2) 4
(1, 5) 3
Select edge (3, 4)
(3, 4) 1
with minimum weight.
(3, 5) 6
(3, 6) 3
Edges with one vertex in the tree and one vertex not in the tree are:
Edge Weight The minimum spanning tree
(1, 2) 4 will be constructed when
(1, 5) 3 either (1, 5) or (3, 6)
(3, 5) 6 is selected.
(3, 6) 3 Select edge (1, 5).
(4, 2) 5 with minimum weight.
(4, 6) 6

11
Edges with one vertex in the tree and one vertex not in the tree are:
Edge Weight
(1, 2) 4
(3, 6) 3
Select edge (5, 6)
(4, 2) 5
with minimum weight.
(4, 6) 6
(5, 6) 2
Edges with one vertex in the tree and one vertex not in the tree are:
Edge Weight
(1, 2) 4 Select edge (1, 2)
(4, 2) 5 with minimum weight.
The minimal spanning tree, shown below, has weight 12.

1 4 2

3 2

1
4
3
5

2
6

12
Discrete Mathematics: Week 10
Binary Trees

Definition 9.5.1
A binary tree is a rooted tree in which each vertex has either no children, one child, or
two children. If a vertex has one child, that child is designated as either a left child or
a right child (but not both). If a vertex has two children, one child is designated a left
child and the other child is designated a right child.

Example 1. Johnsonbaugh Example 9.5.2

In the binary tree below, b is the left child of vertex a, and c is the right child of vertex a.
Vertex d is the right child of vertex b; vertex b has no left child.
Vertex e is the left child of vertex c; vertex c has no right child.

b c

e
d

f g

A full binary tree is a binary tree in which each vertex has either two children or zero
children.
Theorem 9.5.4
If T is a full binary tree with i internal vertices, then T has i + 1 terminal vertices and
2i + 1 total vertices.
Proof:
The i internal vertices each have two children, so there are 2i children.
Only the root is a nonchild.
Therefore the total number of vertices is 2i + 1, and the number of terminal vertices is
(2i + 1) − i = i + 1.

Example 2. In a single elimination tournament, each contestant is eliminated after one

loss. The tree structure is as shown below. Winners progress to the right, and there is a
single winner eventually at the root.
Some contestants receive byes if there are not initially 2n contestants.

1
 Contestant 1

Contestant 2

Contestant 3

Contestant 4
Winner
Contestant 5

Contestant 6

Contestant 7

Theorem 9.5.6
If a binary tree of height h has t terminal vertices, then

lg t ≤ h.

(Or equivalently, t ≤ 2h .)
Proof: We will prove t ≤ 2h by mathematical induction.
Basis Step: If h = 0, the binary tree has a single vertex, and t = 1. Then t = 2h = 20 = 1.
Inductive Step: Assume true for a binary tree with height less than h.
Let T be a binary tree of height t > 0 with t terminal vertices. Suppose that the root of
T has one child. Eliminate the root and edge incident on the root. The remaining tree
has height h − 1 and t terminal vertices. By the assumption,

t ≤ 2h−1 < 2h

and case h is true.

Suppose the root of T has children v1 and v2 , and subtrees rooted at v1 and v2 have
heights h1 and h2 and terminal vertices number t1 and t2 respectively. Then

h1 ≤ h − 1 and h2 ≤ h − 1,

and
t = t1 + t2 ≤ 2h1 + 2h2 ≤ 2h−1 + ≤ 2h−1 = 2h .
Hence the inductive step is verified.
Since the Basis Step and Inductive Step have been verified, the Principle of Mathematical
Induction tells us that the theorem is true.

2
Definition 9.5.8
A binary search tree is a binary tree T in which data are associated with the vertices.
The data are arranged so that, for each vertex v in T , each data item in the left subtree
of v is less than the data item in v, and each data item in the right subtree of v is greater
than the data item in v.
Algorithm 9.5.10 in Johnsonbaugh gives a formal approach for constructing a binary
search tree. A less formal approach is as follows.

• Start with an empty tree (no vertices or edges).

• Inspect the items in order.

• Place the first item in the root.

• Compare each following item in turn with the current vertex, beginning with the
root.

• If item < vertex, move to the left child.

• If item > vertex, move to the right child.

• Continue to compare with each new vertex.

• If there is no child in that position, place the item there.

• Move to the next item and start over, comparing with the root.

Example 3. Build a binary search tree for items in order

o, n, p, d, u, j, t, l, m,

using lexicographic order.

n p

d u

j t

3
Example 4. Build a binary search tree for the words
“by nineteen ninety no Australian child will be living in poverty”.

by

Australian nineteen

be child ninety

living no

in will

poverty

Searching a Binary Search Tree

The algorithm is as follows.

• Given a data item D.

• Begin at the root as the current vertex.
• If D < vertex, go to the left child.
• If D > vertex, go to the right child.
• If D = vertex, the data item is found.
• If the child to move to is missing, D is not in the tree.

Worst-case Search Time

The worst-case search is to search the longest path from the root when the item is not
present.
Suppose that there are n internal vertices, or data items. The terminal vertices would
correspond to missing children. So if the item is not in the tree, we need to check down
to the appropriate terminal vertex.
For a full binary tree with n internal vertices, the number of terminal vertices is t = n + 1.
We know that lg t ≤ h, where h is the height of the tree. Hence the worst-case search
time is
⌈ lg t ⌉ = ⌈ lg (n + 1) ⌉.

4
For example, if a tree contains a million items, then

⌈ lg 1, 000, 000 ⌉ = 20,

so that a search will find an item, or determine if it is not present, in at most 20 steps.
There are algorithms to minimize the height of a binary search tree.

Tree Traversals Johnsonbaugh 9.6

Bread-first search and depth-first search are ways to traverse a tree in a systematic way
such that each vertex is visited exactly once. This section considers three other tree-
traversal methods, which are defined recursively. Johnsonbaugh gives formal algorithms
for each of these, we will consider simpler formulations.
Preorder Traversal Recursive algorithm 9.6.1
Preorder the root: process the root, preorder the left child, preorder the right child.
Inorder Traversal Recursive algorithm 9.6.3
Inorder the root: inorder the left child, process the root, inorder the right child.
Postorder Traversal Recursive algorithm 9.6.5
Postorder the root: postorder the left child, postorder the right child, process the root.

Example 5. Consider the following tree.

B F

C D G

E H

I J

Preorder: A B F
ABC D F G
ABCDEFG H
ABCDEFGHIJ

5
Inorder: B A F
CB D AF G
CBDEAF H G
CBDEAFIHJG

Postorder: B F A
C D B G FA
CEDB H GFA
CEDBIJHGFA

Arithmetic Expressions
The operators +, −, × and ÷ ( or +, −, ∗, / ) operate on pairs of operands or expressions,
where the operator appears between its operands. An example is

(A + B) × C − D ÷ E.

This is the infix form of an expression.

An arithmetic expression can be represented as a binary tree.
The terminal vertices correspond to the operands.
The internal vertices correspond to the operators.
An operator operates on its left and right subtrees.
Example 6. The expression (A + B) × C − D ÷ E can be represented as the tree in the
diagram below.

× ÷

+ C D E

A B

For inorder traversal, parentheses are put around each operation. The parentheses dictate
the order of the operations, and the hierarchy of the operators need not be specified. Some
pairs of pararentheses may not be necessary.
 
Inorder: × − ÷
  
+ ×C − (D ÷ E )
(((A + B ) × C ) − (D ÷ E ))

6
The preorder traversal is as follows. This is known as the prefix form of the expression or
Polish notation. No parentheses are required for unambiguous evaluation.

Preorder: − × ÷
− × + C ÷ DE
− × +ABC ÷ DE

The postorder traversal is as follows. This is known as the postfix form of the expression or
reverse Polish notation. Again, no parentheses are required for unambiguous evaluation.

Postorder: × ÷ −
+ C × DE ÷ −
AB + C × DE ÷ −