Math 236: David. J. Erwin and Henda C. Swart School of Mathematical Sciences University of Kwazulu-Natal
Math 236: David. J. Erwin and Henda C. Swart School of Mathematical Sciences University of Kwazulu-Natal
Math 236: David. J. Erwin and Henda C. Swart School of Mathematical Sciences University of Kwazulu-Natal
DISCRETE MATHEMATICS
WITH APPLICATIONS
by
2 How to count 21
2.1 Basic counting principles . . . . . . . . . . . . . . . . . . . . . 21
2.2 The Pigeonhole Principle . . . . . . . . . . . . . . . . . . . . . 25
2.3 One-to-one functions and permutations . . . . . . . . . . . . . 28
2.4 Counting permutations . . . . . . . . . . . . . . . . . . . . . . 30
2.5 Combinations . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.6 The Inclusion-Exclusion Principle . . . . . . . . . . . . . . . . 39
2.7 Infinite sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3
4
4 Fundamentals of cryptology 81
4.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
4.2 Monoalphabetic and polyalphabetic ciphers . . . . . . . . . . . 83
4.2.1 Monoalphabetic ciphers . . . . . . . . . . . . . . . . . 84
4.2.2 Polyalphabetic ciphers . . . . . . . . . . . . . . . . . . 86
4.2.3 Modular arithmetic . . . . . . . . . . . . . . . . . . . . 88
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
5 Public-key cryptography 93
5.1 One-way functions . . . . . . . . . . . . . . . . . . . . . . . . 93
5.1.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . 93
5.1.2 The password problem . . . . . . . . . . . . . . . . . . 94
5.1.3 Trapdoor one-way functions . . . . . . . . . . . . . . . 95
5.2 The key distribution problem . . . . . . . . . . . . . . . . . . 96
5.3 Diffie-Hellman key exchange . . . . . . . . . . . . . . . . . . . 97
5.4 The birth of public-key cryptography . . . . . . . . . . . . . . 99
5.5 The RSA cryptosystem . . . . . . . . . . . . . . . . . . . . . . 100
5.5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . 100
5.5.2 The mechanics of RSA: key generation . . . . . . . . . 102
5.5.3 The mechanics of RSA: encryption and decryption . . . 103
5.5.4 Key size in the RSA system . . . . . . . . . . . . . . . 106
5.5.5 Digital signatures with RSA . . . . . . . . . . . . . . . 107
5.5.6 The mathematics of RSA . . . . . . . . . . . . . . . . . 111
5.6 The Discrete Logarithm Problem . . . . . . . . . . . . . . . . 112
5.7 The El Gamal public-key cryptosystem . . . . . . . . . . . . . 113
5.7.1 El Gamal: key generation . . . . . . . . . . . . . . . . 113
5.7.2 El Gamal: encryption and decryption . . . . . . . . . . 114
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
7
8 MATH236 Discrete Mathematics with Applications 2009
A number of sets occur frequently enough in mathematics that they are given
special names or symbols:
• The positive integers or natural numbers: N = {1, 2, 3, . . .}.
• The integers: Z = {. . . , −2, −1, 0, 1, 2, . . .}.
• The real numbers: R.
• The rational numbers: Q, the set of all real numbers that can be written
in the form a/b, where a, b ∈ Z and b 6= 0.
• The irrational numbers: the set of all real numbers that are not rational.
√
Example 1.1.2 Hence −4 ∈ Z − N, 2 ∈ R − Q. Also, every positive integer
is an integer, every integer is in turn rational, and every rational number is real,
so N ⊆ Z ⊆ Q ⊆ R.
1. That A ⊆ B, and,
2. That B ⊆ A.
Firstly, if x is in S1 ∪ S2 ∪ · · · ∪ Sn , then it is not a member of any of the
sets S1 , S2 , . . . , Sn . Hence x is a member of S i for all i ∈ {1, 2, . . . , n}, and
hence x ∈ S 1 ∩ S 2 ∩ · · · ∩ S n . Thus A ⊆ B.
Suppose now that x ∈ S 1 ∩ S 2 ∩ · · · ∩ S n . Then x 6∈ S1 and x 6∈ S2
and, in general, x 6∈ Si for any i. Consequently, x 6∈ S1 ∪ S2 ∪ · · · ∪ Sn ,
so x ∈ S1 ∪ S2 ∪ · · · ∪ Sn . This shows that B ⊆ A, which completes the
proof.
1.2 Partitions
If S ∩ T = ∅, then S and T are disjoint. A collection {S1 , S2 , . . . , Sk } of
subsets of a set S is called pairwise disjoint if every two distinct subsets Si
and Sj are disjoint, i.e., i 6= j implies that Si ∩ Sj = ∅.
A partition of S is a pairwise disjoint collection of nonempty subsets whose
union is S. In other words, a partition of S is a collection S = {S1 , S2 , . . . , Sk }
of subsets of S satisfying all three of the following criteria:
1. For all i ∈ {1, 2, . . . , k}, Si 6= ∅.
2. For all i, j ∈ {1, 2, . . . , k}, if i 6= j, then Si ∩ Sj = ∅.
k
[
3. Si = S.
i=1
Example 1.2.1
10 MATH236 Discrete Mathematics with Applications 2009
• For each i ∈ {0, 1, 2}, let Si be the set of all integers whose remainder
when divided by 3 is i. In other words,
1.3 Relations
Let S and T be nonempty sets. A relation R from S to T is a subset of
S × T , i.e., R is a set of ordered pairs (s, t), where each s is in S and each
t is a member of T . If (s, t) ∈ R, we say that s is related to t under R, and
we write s R t. If, on the other hand, (s, t) 6∈ R, then we write s R 6 t. The
domain and range of a relation R are defined as:
R = {(1, a), (1, c), (2, a), (2, b), (3, c)}.
Sets, mappings, equivalence relations 11
Example 1.3.2
• The set R1 = {(x, x2 ) : x ∈ R} is a relation on R.
• The set R2 = {(x, y) ∈ Z2 : x < y} is a relation on Z. Some of the
ordered pairs in R2 are: (1, 5), (−3, 200), (10, 11), (−43, −29), (0, 2). In
fact, R2 is the familiar relation ‘is less than’, and we say that ‘< is a
relation on Z’.
• Similarly, ≥ is a relation on R (and on Z, and on Q, . . . ). It consists of
all those ordered pairs (x, y) of real numbers in which x is at least as large
as y.
• Consider the set P of all sixteen subsets of {1, 2, 3, 4}. Then ⊆ is a relation
on P , as is ⊂. For example, {1, 3} and {1, 3, 4} are both members of P ,
and {1, 3} ⊆ {1, 3, 4}, so {1, 3} is related to {1, 3, 4} under the relation
⊆.
• 1 The set R3 = {(x, y) ∈ Z2 : 2 | (x−y)} is a relation on Z. Some of the or-
dered pairs in R3 are: (0, 2), (2, 0), (4, 26), (98, −22), (−1, −1), (5, 29), (−9, 1).
• The set R4 = {(x, y) ∈ R2 : |x − y| < 1} is a relation on R. Some of the
ordered pairs in R4 are: (5, 5), (−3, −3.2), (10.424, 11.403), (−0.25, 0.68).
Example 1.3.3
• No number is less than itself, so < is not reflexive; for the same reason,
< is irreflexive. If x < y, then certainly y ≮ x, hence < is not symmetric.
Moreover, if x < y and y < z, then clearly x < z. It follows that < is
transitive. We are thus left to consider the question: Is < antisymmetric?
The reasoning here is a little subtle: < is antisymmetric if the implication
‘x < y and y < x implies that x = y’ is always true. Since it’s not possible
that x < y and y < x, the left-hand side of this implication is always
false. Thus2 we find that the implication is always true. Consequently, <
is antisymmetric.
Example 1.4.1
• Of the relations considered in Examples 1.3.2 and 1.3.3, only R3 is an
equivalence relation.
• Denote by L the set of all lines in the plane and define a relation R on L
as follows. For L1 , L2 ∈ L, L1 is related to L2 under R if (i) L1 and L2
coincide, or, (ii) L1 is parallel to L2 . Since every line coincides with itself,
R is reflexive. Moreover, if L1 is parallel to L2 , then L2 is parallel to L1 ,
so R is symmetric. Finally, if L1 is parallel to L2 and L2 is parallel to L3 ,
then clearly L1 is parallel to L3 , showing that R is transitive.
14 MATH236 Discrete Mathematics with Applications 2009
[x] = {y ∈ S : x R y}
Example 1.4.2
• Consider the relation R3 of Examples 1.3.2 and 1.3.3. Which integers are
in [5]? From the definition of the relation R3 , we know that x ∈ [5] if
and only if 5 − x = 2t for some integer t. Thus [5] = {5 + 2t : t ∈ Z}.
Clearly, then [5] is the set of all odd integers. Notice that [5] = [3] =
[7] = [1] = [−3] = [51] = · · · . Similarly, one may reason that [6] is the
set of even integers, and that [6] = [4] = [2] = [20] = [−10] = · · · . Thus
Z/R3 = {[0], [1]}.
• Consider the relation R on L from Example 1.4.1. Which lines are in the
equivalence class containing the line L1 : y = 2x + 3? Clearly, L1 R L2 if
and only if the slope of L2 is 2. Hence, [L1 ] = {all lines in the plane that can
be written in the form y = 2x + c : c ∈ R}.
• Consider the relation R5 from Example 1.4.1 and let S = {−6, −5, −2, −1, 0, 1, 3, 5, 7}.
What elements is −6 related to? We already know that R5 is an equiva-
lence relation, so certainly −6R5 − 6. Since −6 + 2(−5) = −16, which is
Sets, mappings, equivalence relations 15
The next theorem establishes one of the reasons why equivalence relations
are important: Every equivalence relation induces a partition.
The next example is important for what follows and it is suggested that
you study it closely.
What do the equivalence classes under this relation look like? Clearly,
[0] = {. . . , −3n, −2n, −n, 0, n, 2n, 3n, . . .}
[1] = {. . . , −3n + 1, −2n + 1, −n + 1, 1, n + 1, 2n + 1, 3n + 1, . . .}
[2] = {. . . , −3n + 2, −2n + 2, −n + 2, 2, n + 2, 2n + 2, 3n + 2, . . .}
[3] = {. . . , −3n + 3, −2n + 3, −n + 3, 3, n + 3, 2n + 3, 3n + 3, . . .}
···
[n − 1] = {. . . , −2n − 1, −n − 1, −1, n − 1, 2n − 1, 3n − 1, 4n − 1, . . .}
Thus, for example, the equivalence class [2] contains all those integers whose
remainder when divided by n is 2. In general (for 0 ≤ k < n), the equivalence
class [k] consists of all those integers whose remainder when divided by n is k.
As a more concrete example, consider the relation congruence modulo 3,
which we denote by ∼ for convenience. The set of equivalence classes under ∼
is Z/ ∼ = {[0], [1], [2]}, where
[0] = {. . . , −9, −6, −3, 0, 3, 6, 9, . . .}
[1] = {. . . , −8, −5, −2, 1, 4, 7, 10, . . .}
[2] = {. . . , −7, −4, −1, 2, 5, 8, 11, . . .}.
Notice that, as promised by Theorem 3, the equivalence classes partition Z.
Not only does every equivalence relation give rise to a partition, but the
reverse is true as well:
Theorem 4. Let P be a partition of a set S. Then there exists an equivalence
relation R on S for which S/R = P, i.e., the equivalence classes of R are
the parts of P.
Proof. Define R as follows:
For x, y ∈ S, x R y if y is in the same part of P as x.
We prove that R is an equivalence relation. Every x is in the same part as
itself, so R is reflexive. Also, if y is in the same part as x, then x is clearly
in the same part as y, showing that R is symmetric. Finally, if y is in the
same part as x and z is in the same part as y, then z is in the same part as
x, establishing that R is transitive. Hence R is an equivalence relation and,
clearly from the definition of R, the equivalence classes of R coincide with
the parts of P.
18 MATH236 Discrete Mathematics with Applications 2009
Exercises
1.1 Let A = {1, 2, 3} and B = {2, 3, 4, 5}. Compute each of the following:
(a) A ∪ B.
(b) A ∩ B.
(c) A − B.
(d) B − A.
(e) A ∆ B.
(f) A × B.
(g) B × A.
(a) R1 = {(1, 1), (1, 2), (2, 1), (3, 4), (4, 3)}.
(b) R2 = {(x, y) ∈ R2 : |x − y| ≥ 2}.
(c) R3 = {(x, y) ∈ Z2 : 2|xy}.
Solutions
1.1 (a) {1, 2, 3, 4, 5}
(b) {2, 3}
(c) {1}
(d) {4, 5}
(e) {1, 4, 5}
(f) {(1, 2), (1, 3), (1, 4), (1, 5), (2, 2), (2, 3), (2, 4), (2, 5), (3, 2), (3, 3), (3, 4), (3, 5)}
(g) {(2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3), (4, 1), (4, 2), (4, 3), (5, 1), (5, 2), (5, 3)}
1.2 {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (1, 2), (2, 3), (3, 4), (4, 5)}
How to count
|A ∪ B| + |A ∩ B| = |A| + |B|
1. We gave one slip to each member of A and then one slip to each member
of B, so clearly we gave out |A| + |B| slips of paper.
21
22 MATH236 Discrete Mathematics with Applications 2009
We’ve just counted the total number of slips of paper in two different ways,
but both ways must give the same answer. Therefore, |A| + |B| = |A ∪ B| +
|A ∩ B|, as required.
|A ∪ B| = |A| + |B|.
|A × B| = |A| · |B|.
Proof. Let A = {a1 , a2 , . . . , a|A| }. For each i ∈ {1, 2, . . . , |A|}, let Ai be the
set of all ordered pairs whose first element is ai , i.e., Ai = {(ai , b) : b ∈
S
B}. Clearly, A × B = |A| i=1 Ai , and |Ai | = |B|. Also, {A1 , A2 , . . . , A|A| } is
a pairwise disjoint collection of sets (so {A1 , A2 , . . . , A|A| } is a partition of
A × B). Thus,
|A|
X
|A × B| = |A1 ∪ A2 ∪ · · · ∪ A|A| | = |Ai | = |A| · |B|.
i=1
How to count 23
Example 2.1.1 Referring to Example 1.1.1, the sets S and T have |S| = 3
and |T | = 4. Thus |S × T | = 3 · 4 = 12. You can check, by referring to that
example, that S × T does in fact have 12 elements.
Theorem 8 is one form of the Multiplication Principle:
Let S be a set of ordered pairs (s1 , s2 ) of objects in which the
first object s1 comes from a set of size n1 , and for each choice
of object s1 there are n2 choices for object s2 . Then the set S
contains n1 n2 ordered pairs.
Example 2.1.3 How many 4-digit odd numbers are there? We consider each
number abcd as the 4-tuple (a, b, c, d). Such a number is odd if and only if the
last digit, d, is in the set {1, 3, 5, 7, 9}. There are no other restrictions on the
digits. Thus: n1 = 9 (since the first digit cannot be 0), n2 = n3 = 10, and
n4 = 5. It follows that the number of 4-digit odd numbers is 9 · 10 · 10 · 5 = 4500
Example 2.1.4 How many odd numbers less than 10,000 are there? Here,
we’ll use the Addition Principle together with the Multiplication Principle. For
i ∈ {1, 2, 3, 4}, let Ni be the set of all i-digit odd numbers. Notice that
{N1 , N2 , N3 , N4 } is a pairwise disjoint collection of sets. Then by the Addition
Principle, the number of odd numbers less than 10,000 is |N1 |+|N2 |+|N3 |+|N4 |.
Using the Multiplication Principle as in the previous example, we find that
|N1 | = 5, |N2 | = 45, |N3 | = 450, and we already know that |N4 | = 4500.
Thus the answer is 4500 + 450 + 45 + 5 = 5000.
Example 2.1.5 How many k-tuples can be chosen from a set of n elements if
repetition is allowed? We seek the number of k-tuples (s1 , s2 , . . . , sk ) in which
each si comes from a fixed set of n elements and in which it’s possible that
si = sj . For each position in the k-tuple, we can choose any one of n different
elements. Hence, by the Multiplication Principle, there are
· · · · · n} = nk
|n · n {z
k terms
such k-tuples.
If S is a set, then we let 2S denote the set of all subsets of S, sometimes
called the power set of S.
2S = {∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}
How to count 25
Clearly, each subset corresponds to exactly one |S|-tuple and each |S|-tuple
corresponds to one subset. It follows that the number of subsets is equal to
the number of such |S|-tuples. Since each position in the |S|-tuple is chosen
from a set ({0, 1}) of size 2, we are asking the question: How many |S|-tuples
can be chosen from a set of 2 elements? By Example 2.1.5, the answer is
2|S| .
You can verify this by counting the subsets that we found in the previous exam-
ple.
Proof. If this is not the case, then each box contains at most one object,
implying that the number of objects is at most n. This is a contradiction.
Example 2.2.1 If we choose 13 people, then there are two who have their
birthday in the same month.
Example 2.2.3 We choose 101 of the integers 1, 2, . . . , 200. Show that among
the integers chosen, there are two having the property that one is divisible by the
other. Each integer in {1, 2, . . . , 200} can be written in the form n2k , where n is
an odd number between 1 and 199. There are 100 odd integers in {1, 2, . . . , 200},
so if we choose 101 numbers, by the Pigeonhole Principle, two of the numbers
we’ve chosen must have the same odd n, i.e., two of the numbers we’ve chosen
are of the form n2k1 and n2k2 . Assuming without loss of generality that k1 ≥ k2 ,
the number n2k2 divides the number n2k1 , as desired.
We now give a stronger form of the Pigeonhole Principle:
Proof. Assume, to the contrary, that this is not the case. Then for each
i ∈ {1, 2, . . . , k}, the ith box contains at most ni − 1 objects. Thus the total
number of objects is at most
which is a contradiction.
n2 + 1 = (n + 1) + (n + 1) + · · · + (n + 1) −n + 1
| {z }
n terms
the Strong Pigeonhole Principle guarantees that at least one box contains at
least n + 1 objects, i.e., at least one of the integers 1, 2, . . . , n is chosen at least
n + 1 times.
Let a1 , a2 , . . . , ak be a sequence of real numbers. Recall that a subsequence
is a sequence of the form ai1 , ai2 , . . . , ait , where i1 < i2 < · · · < it . The
sequence a1 , a2 , . . . , ak is increasing if a1 ≤ a2 ≤ · · · ≤ ak , and decreasing if
a1 ≥ a2 ≥ · · · ≥ at .
Example 2.3.1
• Let f1 = {(1, a), (2, c), (3, b)} and f2 = {(1, a), (2, b), (3, b)}. Both f1
and f2 are functions. The function f1 is an injection, while f2 is not (since
the element b of the range is related to both 2 and 3). The inverse of f1
is f1−1 = {(a, 1), (c, 2), (b, 3))}.
How to count 29
Example 2.3.2 Let S = {1, 2, 3}. One permutation of S is the function f with
f (1) = 1, f (2) = 3, and f (3) = 2. This permutation can be denoted in the
following fashion: µ ¶
1 2 3
f= .
1 3 2
The top row of the matrix is read as the domain and the bottom row as the
range. Thus, in general, this notation has this form:
µ ¶
1 2 3
f= .
f (1) f (2) f (3)
There are six permutations of a set of three elements. The six permutations of
{1, 2, 3} are:
µ ¶ µ ¶ µ ¶
1 2 3 1 2 3 1 2 3
f1 = f2 = f3 =
1 2 3 2 3 1 3 1 2
µ ¶ µ ¶ µ ¶
1 2 3 1 2 3 1 2 3
f4 = f5 = f6 =
1 3 2 3 2 1 2 1 3
Written this way, it’s easy to find the inverse of a permutation: interchange
the top and bottom rows of the matrix and then (if necessary) re-order by the
30 MATH236 Discrete Mathematics with Applications 2009
is µ ¶
2 3 1
1 2 3
which, after resorting the top row into ascending order, becomes the permutation
µ ¶
1 2 1
= f3 .
3 1 2
f1−1 = f1
f3−1 = f2
f4−1 = f4
f5−1 = f5
f6−1 = f6 .
we simply write the bottom row, (2413). Thus, we could write f1 = (123),
f6 = (213), etc.
Example 2.4.1 How many permutations of the set S = {a, b, c} are there?
How to count 31
n! = n · (n − 1) · (n − 2) · · · 3 · 2 · 1,
e.g.,
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120.
This gives us a compact way to write certain expressions down. Recall that
an n-set is a set containing n elements:
Example 2.4.2 How many permutations of an n-set are there? Suppose that
the elements of the n-set are x1 , x2 , . . . , xn . As in the previous example, we
can consider each permutation to be an n-tuple (f (x1 ), f (x2 ), . . . , f (xn )). As
before, we have n choices for f (x1 ). Once we’ve chosen f (x1 ), there are (n − 1)
possible choices for f (x2 ), and, once we’ve chosen f (x2 ), there are (n − 2) pos-
sible choices for f (x3 ), and so on. So we see that the number of permutations
of an n-set is n(n − 1)(n − 2) · · · 2 · 1 = n!.
Example 2.4.3 Continuing the previous example: there are 6! = 720 permuta-
tions of the set {a, b, c, d, e, f }.
32 MATH236 Discrete Mathematics with Applications 2009
Example 2.4.4 How many k-tuples can be chosen from an n-set if repetition
of elements is not allowed? If repetition of elements is allowed, we already know
the answer to this question (Example 2.1.5). Suppose then that repetition is not
allowed. We may choose any of n elements for the first position in the k-tuple.
Once we’ve done that, we may choose any element for the second position ex-
cept the one we chose for the first, so for each choice for the first position, there
are n − 1 choices for the second position. The pattern is hopefully clear: once
we’ve chosen the second position, there are (n − 2) possibilities for the third
position, and so on, until we reach the kth position, for which there are n − k + 1
possibilities. From the Multiplication Principle, the number of such k-tuples is
thus
n(n − 1)(n − 2) · · · (n − k + 2)(n − k + 1). (2.1)
Example 2.4.6 How many six-letter words2 can be formed from the letters
a,b,c,d,e,f,g,h,i (each letter can be used only once)? Each word corresponds to
a 6-tuple. The question is then: How many 6-tuples can be formed from a set
of 9 elements. The answer is
9!
(9)6 = = 60480.
3!
2
Including nonsense words.
How to count 33
Example 2.4.7 In how many ways can a President, Vice President, and Secretary
be elected from a group of fifteen people? We need to know how many 3-tuples of
the form (name of President, name of Vice-President, name of Secretary) there
are. The answer is (15)3 = 2730.
Example 2.4.8 In how many different ways can the 26 letters of the alphabet
be arranged so that no two of the vowels a,e,i,o,u occur in consecutive positions?
First of all, there are 21 consonants, so, ignoring the vowels for a moment, there
are 21! ways of arranging the consonants. Once we’ve arranged them, we must
place the vowels in the 22 ‘holes’ between, before, and after the consonants, and
whichever hole we place one vowel in, we cannot place any of the others in the
same hole. It follows that, once the consonants have been arranged, there are
(22)5 ways of distributing the vowels. Finally, by the Multiplication Principle, the
number of ways of arranging all the letters is
22!
21! · (22)5 = 21! = 161451464537975567155200000.
17!
You might have noticed that n! grows quickly, but how quickly exactly? A
commonly used approximation for n! is Stirling’s Approximation:
√ ³ n ´n
n! ≈ 2πn .
e
This shows that n! grows exponentially fast with n.
2.5 Combinations
Let n, k be nonnegative integers with k ≤ n. We define n choose k to be the
quantity µ ¶
n n! (n)k
= = .
k (n − k)!k! k!
¡ ¢
The quantity nk is also called a binomial coefficient.
Example 2.5.1 µ ¶
7 7!
= = 35.
4 3!4!
34 MATH236 Discrete Mathematics with Applications 2009
Proof.
µ ¶
n n! n!
= =
k (n − k)!k! (n − k)!(n − (n − k))!
n!
=
(n − (n − k))!(n − k)!
µ ¶
n
= .
n−k
• T (n, k) be the set of all k-tuples chosen from the set {1, 2, . . . , n}.
How to count 35
f ((x1 , x2 , . . . , xk )) = {x1 , x2 , . . . , xk }.
Example 2.5.2
Proof. Notice that for each k-subset S of S(n, k), there are k! k-tuples T
with f (T ) = S. It follows that
But from Example 2.4.4, we know that |T (n, k)| = (n)k . The result follows.
Example 2.5.3 In how many different ways can three representatives be cho-
sen from a group of fifteen people? Notice that we’re not asking how many
3-tuples can be chosen from a set of fifteen elements, because the 3-tuple
(Adam, Mary, Lisa) is the same set of three representatives as (Mary, Lisa, Adam)
(contrast this with Example 2.4.7). The three representatives are unordered,
¡15¢ and
hence a subset rather than a k-tuple. Thus the answer we require is 3 = 455.
36 MATH236 Discrete Mathematics with Applications 2009
Example 2.5.4 How many hands of five cards can be drawn from a standard
deck of 52 cards?
¡52¢ Once again, the order the cards are drawn in is unimportant.
The answer is 5 = 2598960.
Two well-known identities involving binomial coefficients are the following:
Theorem 16 (Pascal’s Identity). Let n, k be positive integers with k ≤ n−1.
Then µ ¶ µ ¶ µ ¶
n n−1 n−1
= + .
k k−1 k
Proof. We’ll use a combinatorial proof here. Let N be the number of k-
subsets of the set S = {1, 2, . . . , n}. What is N ? Firstly, from Theorem
15, µ ¶
n
N= .
k
Here’s another way to find N . Let N1 be the number of k-subsets of S that
include the number 1, and let N2 be the number of k-subsets of S that do
not include the number 1. Clearly,
N = N1 + N2 .
Proof. If n = 0, then the left hand side and the right hand side are equal, so
we assume that n ≥ 1. Consider the left hand side:
(x + y)n = (x + y)(x + y) · · · (x + y) . (2.2)
| {z }
n terms
When we expand the right hand side of equation (2.2), we obtain terms of
the form xk y j . Since there are n terms in the product on the right hand
side of (2.2) and each term of the form xk y j is obtained by choosing in each
(x + y) either the x or the y, it must be the case that k + j = n, i.e., each
term is of the form xk y n−k . It remains to determine, for a fixed k, how many
terms of the form xk y n−k occur when we expand the right hand side of (2.2).
The term xk y n−k occurs when, in multiplying through the right hand side
of (2.2), we choose x in k of the terms (x + y) (and, consequently, choose y
in the remaining n − k terms), so the number of terms of the form xk y n−k
is equal to the number of ways we can choose ¡n¢ k x’s from the n terms of the
form (x + y). This is clearly the number k , thus completing the proof.
Example 2.5.6
3 µ ¶
X
3 3
(x + y) = xk y 3−k
k=0
k
µ ¶ µ ¶ µ ¶ µ ¶
3 3 3 2 3 2 3 3
= y + xy + x y+ x
0 1 2 3
= y 3 + 3xy 2 + 3x2 y + x3
Theorem 20. The number of objects of S that have none of the properties
P1 , P2 , . . . , Pn is given by
X X X
|S 1 ∩ S 2 ∩ · · · ∩ S n | =|S| − |Si | + |Si ∩ Sj | − |Si ∩ Sj ∩ Sk | + · · ·
· · · + (−1)n |S1 ∩ S2 ∩ · · · Sn |.
S 1 ∩ S 2 ∩ · · · ∩ S n = S1 ∪ S2 ∪ · · · ∪ Sn .
Moreover,
S = (S1 ∪ S2 ∪ · · · ∪ Sn ) ∪ (S1 ∪ S2 ∪ · · · ∪ Sn ).
The result follows immediately from algebraically manipulating the formula
in Theorem 20.
Example 2.6.2 How many numbers between 0 and 100 are divisible by 2,3, or
5? Let P2 be the property that a number is divisible by 2, P3 that it is divisible
by 3, and P5 that it is divisible by 5. Then we need to know |S2 ∪ S3 ∪ S5 |. There
are 51 numbers between 0 and 100 with property P2 , 34 with property P3 , and
21 with property P5 . A number is divisible by both 2 and 3 iff it’s divisible by 6,
and there are 17 of these numbers, so |S2 ∩ S3 | = 17. Similarly, |S2 ∩ S5 | = 11,
and |S3 ∩ S5 | = 7. Lastly, |S2 ∩ S3 ∩ S5 | = 4. Then from the Inclusion-Exclusion
Principle we have
Example 2.7.2 Let A = {3, 4, 5, 6, 7} and B = {5, 6, 7, 8, 9}. Then the func-
tion f : A → B with rule f (x) = x + 2 is a bijection, so |A| = |B|.
These two examples are both hopefully straightforward. Once the sets un-
der consideration become infinite, things become both more complicated and
more interesting.
|N| = ℵ0 , and
|R| = ℵ1
Theorem 22. ℵ0 6= ℵ1 .
Proof. From Example 2.7.5, we know that |(0, 1)| = ℵ1 . We shall thus prove
the result by showing3 that it is impossible to construct a bijection from N to
(0, 1). Suppose, to the contrary, that there exists a bijection f : N → (0, 1).
Then for each x ∈ N, f (x) is a number in (0, 1), i.e., a number that can be
3
The proof we shall use is called Cantor’s Diagonal Argument.
44 MATH236 Discrete Mathematics with Applications 2009
(
1 if xii =
6 1
yi =
2 if xii = 1
Notice the following: (i) the number y is in (0, 1), and, (ii) there is no n ∈ N
such that f (n) = y, because the nth digits of f (n) and y are not equal.
Hence f is not onto, which contradicts our assumption that f is a bijection.
It follows that no such bijection exists and ℵ0 6= ℵ1 .
Proof. We first show that the positive rational numbers Q+ are countable.
Construct a table in which the entry in row i and column j is the rational
number ji .
How to count 45
1 2 3 4 ···
1 1 1 1
1 1 2 3 4
···
2 2 2 2
2 1 2 3 4
···
3 3 3 3
3 1 2 3 4
···
4 4 4 4
4 1 2 3 4
···
.. ...
. ··· ··· ··· ···
Notice that every positive rational number occurs somewhere in this table.
We shall traverse the table in the order indicated by the arrows:
1 2 3 4 ···
1 1 1 1
1 1 2 3 4
···
2 2 2 2
2 1 2 3 4
···
3 3 3 3
3 1 2 3 4
···
4 4 4 4
4 1 2 3 4
···
.. ..
. ··· ··· ··· ··· .
46 MATH236 Discrete Mathematics with Applications 2009
- -
6
? ?
6
? ?
- -
¾ ¾ ¾
g(1) = 0
g(2) = f (1)
g(3) = −f (1)
g(4) = f (2)
g(5) = −f (2)
..
.
This is clearly a bijection between N and Q, and this establishes the result.
We have thus proved that there are ‘as many rational numbers as there
are positive integers’ !
48 MATH236 Discrete Mathematics with Applications 2009
Exercises
2.1 Chalk comes in 3 different lengths, 8 different colors, and 4 different
diameters. How many different kinds of chalk are there?
2.3 How many two-digit numbers have distinct and nonzero digits?
2.4 How many odd numbers between 1000 and 9999 have distinct digits?
2.5 How many different five-digit numbers can be constructed from the
digits 1,2,3,3,3?
2.6 Show that if n + 1 integers are chosen from the set {1, 2, . . . , 2n}, then
there are always two which differ by 1.
2.7 A bag contains 100 apples, 100 bananas, 100 oranges, and 100 pears.
If I pick one piece of fruit out of the bag every minute, how long will it
be before I am assured of having picked at least a dozen pieces of fruit
of the same kind?
2.12 Use the Binomial Theorem to write out the expansion of (x + y)6 .
2.13 Use the Binomial Theorem to write out the expansion of (2x − 3)4 .
¡ n ¢¡n−m¢ ¡n¢¡n−k¢
2.14 ¡Prove
¢ the formula m k
= k m without using the formula for
n
k
. Hint: consider pairs of subsets.
2.15 A used car dealer has 18 cars. Nine of them have automatic transmis-
sions, twelve have power steering, and eight have power brakes. Seven
have automatic transmissions and power steering, four have automatic
transmissions and power brakes, and five have power steering and power
brakes. Three cars have automatic transmission and power steering and
power brakes. How many cars do not have automatic transmissions,
power steering or power brakes?
2.16 Find the number of integers between 1 and 10000, inclusive, which are
divisible by none of 4,5, and 6.
2.17 Let ( √ )
n2 + 2
S= x∈R:x= ,n ∈ N .
n
√
n2 + 2
Define f : N → S by f (n) = n
.
2.18 How do the cardinalities of the sets [0, 1] and [1, 3] compare? Justify
your answer.
50 MATH236 Discrete Mathematics with Applications 2009
How to count 51
Solutions
2.1 96
2.2 512
2.3 72
2.4 2240
2.5 20
2.7 45
2.8 (a) 24
¡ ¢
2.9 (17)2 15
3
= 123760
¡ ¢
2.10 (a) 22 4
= 7315
¡12¢¡10¢ ¡12¢¡10¢ ¡12¢¡10¢
(b) 2 2 + 3 1 + 4 0 = 5665
¡¢ ¡¢
2.11 84 + 83 = 126
¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢
2.12 60 x6 + 61 x5 y + 62 x4 y 2 + 63 x3 y 3 + 64 x2 y 4 + 65 xy 5 + 66 y 6 = x6 +
6x5 y + 15x4 y 2 + 20x3 y 3 + 15x2 y 4 + 6xy 5 + y 6
2.15 2
2.16 5334
52 MATH236 Discrete Mathematics with Applications 2009
Chapter 3
53
54 MATH236 Discrete Mathematics with Applications 2009
Example 3.1.2 We’ll use the Division Algorithm to find the GCD of 112 and
268. We begin by setting p0 = 268, q0 = 112, and i = 0. Since 268 = 2·112+44,
i.e., q0 does not divide p0 , we set r0 = 44, then let p1 = 112, q1 = 44, and
i = 1. We now repeat the process with p1 and q1 : since 112 = 2 · 44 + 24, we
let r1 = 24, p2 = 44, and q2 = 24. The process is recorded in this table:
i pi qi ri
0 268 112 44
1 112 44 24
2 44 24 20
3 24 20 4
4 20 4 0
Example 3.1.3 The set Z is closed under addition, multiplication, and subtrac-
tion, but not under division. N is closed under addition and multiplication, but
not under subtraction.
Elementary number theory 55
Lemma 24. Let S be a nonempty set of integers that is closed under addition
and subtraction. Then exactly one of the following two statements is true:
1. S = {0}.
2. S = {0, ±d, ±2d, ±3d, . . .}, where d is the smallest positive integer in
S.
Proof. Certainly the set {0} is closed under addition and subtraction. Sup-
pose that S 6= {0}. Then S contains an element a 6= 0. Since S is closed
under subtraction, S contains −a = a − a − a. Exactly one of a and −a is
positive; thus S contains a positive number and thus, by the Well-Ordering
Axiom, S contains a smallest positive number, d. Since S is closed under
addition and subtraction, we therefore have that S ⊇ {0, ±d, ±2d, ±3d, . . .}.
It remains to prove that S ⊆ {0, ±d, ±2d, ±3d, . . .}. Let z ∈ S. Then, by
the Division Algorithm, there are integers q and r with 0 ≤ r < d so that
z = qd + r. Thus, r = z − qd. Since d, z ∈ S and S is closed under addition
and subtraction, we therefore have r ∈ S. Finally, since r < d and d is
the smallest positive integer in S, the only possibility is that r = 0, whence
z = qd, implying that S ⊆ {0, ±d, ±2d, ±3d, . . .}.
Theorem 25. Let a and b be nonzero integers. Then gcd(a, b) can be ex-
pressed as a linear combination of a and b with integer coefficients; that is,
gcd(a, b) = sa + tb for some integers s and t.
Proof. Let
S = {sa + tb : s, t ∈ Z}.
Clearly, S is closed under addition and subtraction. Consequently, by Lemma
24, S = {0, ±d, ±2d, ±3d, . . .}, where d is the smallest positive integer in S.
We claim that d = gcd(a, b). Certainly, since a, b ∈ {±d, ±2d, ±3d, . . .}, d is
a factor of both a and b. It remains to show that d is the largest factor of
both a and b. Since d ∈ S, there exist integers s0 and t0 such that d = s0 a+t0 b.
But since d = s0 a + t0 b, any positive number p that divides both a and b must
also divide d, implying that p ≤ d, and hence that d = gcd(a, b).
56 MATH236 Discrete Mathematics with Applications 2009
Example 3.1.4 Continuing from Example 3.1.2, let’s find integers s and t such
that
4 = 268s + 112t.
The procedure is, more or less, to ‘reverse’ the Division Algorithm. To do this,
we begin by rewriting gcd(112, 268) = r3 = 4 = 24 − 20. Now we replace
r2 = 20 with (from the previous step in the Division Algorithm) 44 − 24:
4 = 24 − 20 = 24 − (44 − 24).
Consequently,
4 = 12 · 112 + (−5) · 268.
The procedure that we followed in this example is sometimes called the Extended
Division Algorithm.
2×0=0
2×1=2
2×2=0
2×3=2
Elementary number theory 57
sa = 1 − tm ≡ 1 (mod m).
Example 3.2.2 Suppose we wish to find 4−1 ∈ Z21 . Firstly, we check that
gcd(4, 21) = 1, which means that the inverse exists. Using the extended Division
Algorithm, we find that
1 = 21 − 5 · 4
from which it follows that −5 · 4 ≡ 1 (mod 21). From this, it looks like the in-
verse of 4 is -5, but the inverse of 4 has to be a number in [0, 20]. Remembering
that −5 ≡ 16 (mod 21), we therefore have that in Z21 , 4−1 = 16. To check:
4 · 16 = 64 = 3 · 21 + 1 ≡ 1 (mod 21).
58 MATH236 Discrete Mathematics with Applications 2009
1563 = 210 + 29 + 24 + 23 + 2 + 1
Hence:
10 +29 +24 +23 +2+1
21351563 = 21352
10 9 4 3
= 21352 · 21352 · 21352 · 21352 · 21352 · 2135
Now
10 9 9
21352 = 21352·2 = (21352 )2
so
9 9 4 3
21351563 = (21352 )2 · 21352 · 21352 · 21352 · 21352 · 2135
2
If you’re using a calculator that can do binary arithmetic, you can quickly see which
powers of 2 the number 1563 is the sum of by punching 1563 in (as a decimal number)
and then converting it to binary.
Elementary number theory 59
Now, 21352 is relatively easy to compute: it’s 4558225, which is 61 (mod 3172),
so
9 9 4 3
21351563 ≡ 612 · 21352 · 21352 · 21352 · 21352 · 2135 (mod 3172)
29 24 23
≡ (61 · 2135) · 2135 · 2135 · 21352 · 2135 (mod 3172)
We calculate 61 · 2135 ≡ 183 (mod 3172), and then begin the whole pro-
9 9
cess over again, first rewriting the term (61 · 2135)2 ≡ 1832 (mod 3172) ≡
8
(1832 )2 , and then continuing in this fashion until we’ve found the answer:
8 4 3
21351563 ≡ (1832 )2 · 21352 · 21352 · 21352 · 2135 (mod 3172)
8 4 3
≡ 17692 · 21352 · 21352 · 21352 · 2135 (mod 3172)
7 4 3
≡ (17692 )2 · 21352 · 21352 · 21352 · 2135 (mod 3172)
27 24 23
≡ 1769 · 2135 · 2135 · 21352 · 2135 (mod 3172)
6 4 3
≡ 17692 · 21352 · 21352 · 21352 · 2135 (mod 3172)
5 4 3
≡ 17692 · 21352 · 21352 · 21352 · 2135 (mod 3172)
4 3
≡ (1769 · 2135)2 · 21352 · 21352 · 2135 (mod 3172)
3
≡ (61 · 2135)2 · 21352 · 2135 (mod 3172)
2
≡ 1832 · 21352 · 2135 (mod 3172)
≡ (1769 · 2135)2 · 2135 (mod 3172)
≡ 61 · 2135 (mod 3172)
≡ 183 (mod 3172)
Thus,
21351563 ≡ 183 (mod 3172).
Several other explicit examples of the use of the square and multiply algo-
rithm are given later in the notes.
It’s useful to remember that two positive integers have a greatest common
divisor greater than 1 if and only if they have a prime factor in common.
Prime numbers will play an important role throughout the rest of this course,
particularly when we consider public-key cryptography. Since it will be useful
to have a list of small prime numbers, we give one now. Here are the primes
p satisfying 2 ≤ p ≤ 7000:
2 3 5 7 11 13 17 19 23 29
31 37 41 43 47 53 59 61 67 71
73 79 83 89 97 101 103 107 109 113
127 131 137 139 149 151 157 163 167 173
179 181 191 193 197 199 211 223 227 229
233 239 241 251 257 263 269 271 277 281
283 293 307 311 313 317 331 337 347 349
353 359 367 373 379 383 389 397 401 409
419 421 431 433 439 443 449 457 461 463
467 479 487 491 499 503 509 521 523 541
547 557 563 569 571 577 587 593 599 601
607 613 617 619 631 641 643 647 653 659
661 673 677 683 691 701 709 719 727 733
739 743 751 757 761 769 773 787 797 809
811 821 823 827 829 839 853 857 859 863
877 881 883 887 907 911 919 929 937 941
947 953 967 971 977 983 991 997 1009 1013
1019 1021 1031 1033 1039 1049 1051 1061 1063 1069
1087 1091 1093 1097 1103 1109 1117 1123 1129 1151
1153 1163 1171 1181 1187 1193 1201 1213 1217 1223
1229 1231 1237 1249 1259 1277 1279 1283 1289 1291
1297 1301 1303 1307 1319 1321 1327 1361 1367 1373
1381 1399 1409 1423 1427 1429 1433 1439 1447 1451
1453 1459 1471 1481 1483 1487 1489 1493 1499 1511
1523 1531 1543 1549 1553 1559 1567 1571 1579 1583
1597 1601 1607 1609 1613 1619 1621 1627 1637 1657
1663 1667 1669 1693 1697 1699 1709 1721 1723 1733
1741 1747 1753 1759 1777 1783 1787 1789 1801 1811
1823 1831 1847 1861 1867 1871 1873 1877 1879 1889
1901 1907 1913 1931 1933 1949 1951 1973 1979 1987
1993 1997 1999 2003 2011 2017 2027 2029 2039 2053
Elementary number theory 61
2063 2069 2081 2083 2087 2089 2099 2111 2113 2129
2131 2137 2141 2143 2153 2161 2179 2203 2207 2213
2221 2237 2239 2243 2251 2267 2269 2273 2281 2287
2293 2297 2309 2311 2333 2339 2341 2347 2351 2357
2371 2377 2381 2383 2389 2393 2399 2411 2417 2423
2437 2441 2447 2459 2467 2473 2477 2503 2521 2531
2539 2543 2549 2551 2557 2579 2591 2593 2609 2617
2621 2633 2647 2657 2659 2663 2671 2677 2683 2687
2689 2693 2699 2707 2711 2713 2719 2729 2731 2741
2749 2753 2767 2777 2789 2791 2797 2801 2803 2819
2833 2837 2843 2851 2857 2861 2879 2887 2897 2903
2909 2917 2927 2939 2953 2957 2963 2969 2971 2999
3001 3011 3019 3023 3037 3041 3049 3061 3067 3079
3083 3089 3109 3119 3121 3137 3163 3167 3169 3181
3187 3191 3203 3209 3217 3221 3229 3251 3253 3257
3259 3271 3299 3301 3307 3313 3319 3323 3329 3331
3343 3347 3359 3361 3371 3373 3389 3391 3407 3413
3433 3449 3457 3461 3463 3467 3469 3491 3499 3511
3517 3527 3529 3533 3539 3541 3547 3557 3559 3571
3581 3583 3593 3607 3613 3617 3623 3631 3637 3643
3659 3671 3673 3677 3691 3697 3701 3709 3719 3727
3733 3739 3761 3767 3769 3779 3793 3797 3803 3821
3823 3833 3847 3851 3853 3863 3877 3881 3889 3907
3911 3917 3919 3923 3929 3931 3943 3947 3967 3989
4001 4003 4007 4013 4019 4021 4027 4049 4051 4057
4073 4079 4091 4093 4099 4111 4127 4129 4133 4139
4153 4157 4159 4177 4201 4211 4217 4219 4229 4231
4241 4243 4253 4259 4261 4271 4273 4283 4289 4297
4327 4337 4339 4349 4357 4363 4373 4391 4397 4409
4421 4423 4441 4447 4451 4457 4463 4481 4483 4493
4507 4513 4517 4519 4523 4547 4549 4561 4567 4583
4591 4597 4603 4621 4637 4639 4643 4649 4651 4657
4663 4673 4679 4691 4703 4721 4723 4729 4733 4751
4759 4783 4787 4789 4793 4799 4801 4813 4817 4831
4861 4871 4877 4889 4903 4909 4919 4931 4933 4937
4943 4951 4957 4967 4969 4973 4987 4993 4999 5003
5009 5011 5021 5023 5039 5051 5059 5077 5081 5087
5099 5101 5107 5113 5119 5147 5153 5167 5171 5179
62 MATH236 Discrete Mathematics with Applications 2009
5189 5197 5209 5227 5231 5233 5237 5261 5273 5279
5281 5297 5303 5309 5323 5333 5347 5351 5381 5387
5393 5399 5407 5413 5417 5419 5431 5437 5441 5443
5449 5471 5477 5479 5483 5501 5503 5507 5519 5521
5527 5531 5557 5563 5569 5573 5581 5591 5623 5639
5641 5647 5651 5653 5657 5659 5669 5683 5689 5693
5701 5711 5717 5737 5741 5743 5749 5779 5783 5791
5801 5807 5813 5821 5827 5839 5843 5849 5851 5857
5861 5867 5869 5879 5881 5897 5903 5923 5927 5939
5953 5981 5987 6007 6011 6029 6037 6043 6047 6053
6067 6073 6079 6089 6091 6101 6113 6121 6131 6133
6143 6151 6163 6173 6197 6199 6203 6211 6217 6221
6229 6247 6257 6263 6269 6271 6277 6287 6299 6301
6311 6317 6323 6329 6337 6343 6353 6359 6361 6367
6373 6379 6389 6397 6421 6427 6449 6451 6469 6473
6481 6491 6521 6529 6547 6551 6553 6563 6569 6571
6577 6581 6599 6607 6619 6637 6653 6659 6661 6673
6679 6689 6691 6701 6703 6709 6719 6733 6737 6761
6763 6779 6781 6791 6793 6803 6823 6827 6829 6833
6841 6857 6863 6869 6871 6883 6899 6907 6911 6917
6947 6949 6959 6961 6967 6971 6977 6983 6991 6997
There are, in fact, infinitely many prime numbers, which we now prove:
Theorem 28. There are infinitely many prime numbers.
Proof. Suppose, to the contrary, that there are finitely many prime numbers.
Specifically, suppose that there are k prime numbers, p1 , p2 , . . . , pk . Consider
the number n = p1 p2 · · · pk + 1, which is certainly larger than any pi , and
hence not equal to any of them. Since n gives a remainder of 1 when divided
by any pi , n is not divisible by any prime pi . Thus n is itself a prime number,
which contradicts the assumption that there are only k such numbers.
The prime counting function π(n) is the number of prime numbers less
than or equal to n.
Example 3.4.2 How many primes are there between 1 and 10100 ? According
to Theorem 29, the answer is approximately
10100 1098
= ≈ 5 × 1097 .
ln(10100 ) ln(10)
Example 3.5.2
1
φ(32) = φ(25 ) = 25 (1 − ) = 16
2
Also,
φ(27) = φ(33 ) = 33 − 32 = 18
k
Y
Theorem 33. If n = pei i , where p1 , p2 , . . . , pk are distinct primes and
i=1
e1 , e2 , . . . , ek are positive integers, then
k µ
Y ¶
1
φ(n) = n 1− .
i=1
pi
Elementary number theory 65
This establishes the base case. Assume, then, that k ≥ 2 and that the result
is true for all positive integers that are divisible by k − 1 distinct primes. Let
n be a positive integer that is divisible by k distinct primes, p1 , p2 , . . . , pk .
We wish to count the set S of all integers between 1 and n that are multiples
of at least one of the integers pi , 1 ≤ i ≤ k. To do this we use the Addition
Rule.
Let X be the set of all integers between 1 and n that are multiples of
at least one of the integers pi , 1 ≤ i ≤ k − 1, and let Y be the set of all
integers between 1 and n that are multiples of pk but not of pi for any i
where 1 ≤ i ≤ k − 1. By the Addition Rule, |S| = |X| + |Y |. By the
inductive hypothesis,
Yµ
k−1
1
¶
|X| = n − n 1− . (3.3)
i=1
pi
Next we determine |Y |. The set of all integers between 1 and n that are
multiples of pk are µ ¶
n
pk , 2pk , 3pk , . . . , pk .
pk
66 MATH236 Discrete Mathematics with Applications 2009
|S| = |X| + |Y |
Yµ
k−1
1
¶
n Y
k−1 µ
1
¶
= n−n 1− + 1−
i=1
pi pk i=1 pi
" ¶# µ
Yµ
k−1
1 1
¶
= n− n 1− 1−
i=1
pi pk
k µ
Y ¶
1
= n−n 1− .
i=1
pi
¡ ¢¡ ¢¡ ¢
Example 3.5.3 φ(60) = φ(22 ·3·5) = 60 1 − 12 1 − 13 1 − 15 = 60· 12 · 23 · 45 =
16.
φ(mn) = φ(m)φ(n).
Q Q0
Proof. Let m = ki=1 pei i and n = ki=1 (p0i )ei , where p1 , p2 , . . . , pk , p01 , p02 , . . . , p0k0
0
(ii) Suppose, to the contrary, that there is some integer i and a prime number
p such that p|ri and p|m. Then p|(qi m + ri ), hence p|asi , which means
that p divides a or p divides si . Thus, there is an integer p that divides
Elementary number theory 69
Proof. If p is prime, then φ(p) = p − 1. The result now follows directly from
Theorem 37.
Thus, x = 3 ∈ Z11 .
Another useful consequence of Theorem 37 is the following:
3.7 Groups
A group is an ordered pair (S, ◦), where S is a nonempty set and ◦ a binary
operation on S, such that the following conditions hold:
Elementary number theory 71
Example 3.7.2 (Z, ·) is not a group (by · we mean simply multiplication). The
number 1 is the identity: if x is any integer, then x·1 = 1·x = x. However, most
of the integers do not have inverses under ·. For example, there is no integer y
such that 3 · y = 1.
Example 3.7.3 Denote by GLn the set of all invertible n × n matrices with
entries from R. Then GLn together with the operation of matrix multiplication
is a group, the general linear group. The identity element is the n × n identity
matrix and the group inverse of a matrix A is its matrix inverse, A−1 . Similarly,
if we let SLn be the subset of GLn consisting of all those invertible n×n matrices
with determinant 1, then SLn is the special linear group.
Example 3.7.4 (Zn , +), where + denotes addition modulo n, is a group. The
identity element is the number 0. The inverse of x ∈ Zn is the unique number
72 MATH236 Discrete Mathematics with Applications 2009
Example 3.7.5 Consider the group Z∗10 . The elements of Z∗10 are the integers
in Z10 that are relatively prime to 10. Hence
Z∗10 = {1, 3, 7, 9}
(and notice that |Z∗10 | = 4 = φ(10)). Consider the element 7 ∈ Z∗10 . We find
the order of 7 by finding the least positive integer k such that 7k ≡ 1 (mod 10):
k 7k mod 10
1 7
2 9
3 3
4 1
Thus, |7| = 4. Notice that if we rewrite 74 ≡ 1 (mod 10) as 7·73 ≡ 1 (mod 10),
it becomes clear that 73 ≡ 7−1 ≡ 3 (mod 10).
Analogously with the preceding, we can construct a table listing the order of
each element of Z10 :
a |a|
1 1
3 4
7 4
9 2
Elementary number theory 73
Notice that for each a ∈ Z∗10 , the number |a| is a divisor of 4 = |Z∗10 | = φ(10).
This is not a coincidence.
If α ∈ Z∗n is such that |α| = |Z∗n | = φ(n), then α is a generator3 of Z∗n . There
are many values of n for which the group Z∗n does not have a generator4 ,
e.g., Z∗8 does not have a generator5 . However, we shall be most interested
in Z∗p for p a prime number. When p is prime, Z∗p always has at least one
generator.
Example 3.7.6 The numbers 3 and 7 are both generators of Z∗10 , while 1 and
9 are not. Intuitively, 7 is a generator because the powers of 7 generate all the
elements of the group (while, on the other hand, 9 does not generate Z∗10 because
there is no integer k such that 9k ≡ 3 (mod 10) or 9k ≡ 7 (mod 10)).
We shall need to be able to find quickly generators of Z∗p ; hence, we present
the following result (without proof):
Example 3.7.7 Consider the group Z∗31 = {1, 2, . . . , 30}. Here, p − 1 = 30,
which is divisible by exactly three primes: 2, 3, and 5. So for each α ∈ Z∗31 , we
compute
From this we see that 3, 11, 12, 13, 17, 21, 22, and 24 are generators of Z∗31 .
Of course, in general we don’t need a list of all the generators of Z∗p . We
just need one. Theorem 40 suggests the following procedure for finding a
generator of Z∗p :
Elementary number theory 75
Exercises
3.1 Determine which of the following pairs of integers are relatively prime
(give reasons for your answers):
(a) 12 and 32
(b) 21 and 40
(c) 24 and 84
3.2 Use the Division Algorithm to compute the GCD of each of the follow-
ing pairs of integers:
(a) 5 and 21
(b) 82 and 248
(c) 240 and 2805
(d) 2160 and 99225
3.3 For each pair a, b of integers given below, use the Extended Division
Algorithm to find a pair s, t of integers such that gcd(a, b) = sa + tb.
(a) 5 and 21
(b) 82 and 248
(c) 240 and 2805
(d) 2160 and 99225
3.5 Use the square and multiply algorithm to find each of the following:
3.9 For each value of n below: (i) determine the elements of Z∗n , (ii) write
down the multiplication table for Z∗n , (iii) find the order of each element,
and (iv) determine which elements are generators.
(a) n = 5
(b) n = 6
(c) n = 9
(d) n = 15
(e) n = 16
(f) n = 17
3.10 Use the algorithm on page 75 to find a generator for each of the fol-
lowing:
(a) Z∗19
(b) Z∗157
(c) Z∗887
(d) Z∗9949
78 MATH236 Discrete Mathematics with Applications 2009
Elementary number theory 79
Solutions
3.1 (a) Not relatively prime (2 is a common factor).
(b) Relatively prime (no nontrivial common factor).
(c) Not relatively prime (6 is a common factor).
3.2 (a) 1
(b) 2
(c) 15
(d) 135
3.4 (a) 7
(b) 606
(c) 608
3.5 (a) 10
(b) 33
3.6 (a) φ(11) = 10, φ(12) = 4, φ(13) = 12, φ(14) = 6, φ(15) = 8, φ(16) =
8, φ(17) = 16, φ(18) = 6, φ(19) = 18, φ(20) = 8
(b) 100
(c) 48
(d) 396
(e) 1008
3.7 (a) 2
(b) 6
3.8 (a) 10
(b) 3
80 MATH236 Discrete Mathematics with Applications 2009
Fundamentals of cryptology
Note: While studying for this course, you might wish to download
the Handbook of Applied Cryptography, by Menezes, Oorschot,
and Vanstone, published by CRC Press, which has very kindly
made it available for free on the web. You can download it as a
set of PDFs from http://www.cacr.math.uwaterloo.ca/hac.
81
82 MATH236 Discrete Mathematics with Applications 2009
While the word cryptology1 was used for the first time by John Wilkins
in 1641, the subject itself is much older. A very primitive form of cryptology
was used by the Egyptians 4000 years ago. The Spartans used cryptographic
devices in approximately 400 BC and, about forty years later, Tacitus in-
cluded in his military manual a chapter headed On secret messages. For
most of its history, cryptology has been the province of governments and the
military, but with the increasing use of computer networks in the last forty
years, commercial entities have become strongly interested in information
security. Today, the feasibility of internet commerce rests on the ability to
conduct secure electronic transactions.
4.1 Definitions
We wish to send a message in such a way that it is unintelligible to all
unauthorized persons, but can be understood by the intended recipient.
The plaintext (or message) M is a finite string of symbols from a finite
alphabet2 Σ. M is converted, by the process of encryption (or enciphering)
into an enciphered text called the ciphertext (or cryptogram), C. The person
who enciphers M is called the sender or encipherer and uses a set of rules
(or algorithm) to encrypt M . He sends the ciphertext, C, to the (intended)
recipient (or receiver). Normally the operation of the algorithm involves the
use of a key K which is known to both the encipherer and the receiver. The
receiver uses an algorithm (involving the key) to obtain M from C; this is
known as decryption (or deciphering). Note that he ciphertext C and the key
K must determine the plaintext M uniquely.
We shall adopt the convention that plaintext is written lowercase and ci-
phertext uppercase. For example, we might encrypt the word goodbye as
AHYEKVA.
Any person who intercepts the message is called an interceptor3 . In gen-
eral, an interceptor will not know the key and will (we hope!) be unable to
1
From the Greek words krypte (‘to hide’) and logos (‘word’).
2
An alphabet is a set of symbols which we use to write down our messages. Two
important examples are (i) the Latin alphabet {a, b, . . . , z}, and, (ii) the binary alphabet
{0, 1}.
3
Or: adversary, enemy, attacker, opponent, tapper, eavesdropper, intruder, interloper.
Fundamentals of cryptology 83
Interceptor
6
?
ciphertext - ciphertext
unsecured channel
6
encryption decryption
?
plaintext plaintext
Sender Recipient
Example 4.2.1 Suppose that the following set of substitutions (the key) is
used. Both the encipherer and the decipherer have a copy of this key, which is
simply a permutation of the letters of the alphabet:
Plaintext a b c d e f ··· t u v w ···
Ciphertext D X W E G A ··· B F R C ···
Then cat is enciphered as WDB and AGC is deciphered as few.
In a simple substitution cipher like this one, the re-ordered alphabet (D X W
E G A · · · B F R C · · · ) is called the substitution alphabet.
Shift ciphers
In the Gallic wars Julius Caesar used a cipher in which each of the letters
a,b,. . .,z is replaced by the letter which occurs three places after it in the
alphabet4 . We can represent this with the following permutation:
Plaintext a b c d e ··· w x y z
Ciphertext D E F G H ··· Z A B C
4
Of course, there is no letter three places after x, y, or z, but this is easily remedied:
We encrypt x as A, y as B, and z as C.
Fundamentals of cryptology 85
We call this a shift cipher or additive cipher or translation cipher with shift
(or key) 3.
More generally, in a shift cipher with shift d, each letter in the plaintext
alphabet is encrypted as the letter that occurs d places further on in the
alphabet and decrypted by replacing each letter by one that occurs d places
earlier on in the alphabet (or 26 − d places further on). As before, z is
followed by a b c · · · . Note that a shift cipher just a special case of the
simple substitution cipher.
Encryption can be done mechanically by means of a simple device con-
sisting of a large disc on which there is a smaller disc (with the same centre)
which can be rotated d places forward for encryption or d places back for
decryption.
The key is easily remembered, but the cipher is so insecure that it is of
no practical use, as an interceptor has to test at most 25 possible values of d
to find the key.
Example 4.2.2 Suppose that the adversary, who knows that a shift cipher is
being employed, intercepts the following ciphertext:
He tests values of d on the word MHRL and finds that d = 7 yields a plaintext
of fake, while d = 19 yields toys. All other shifts (values of d) result in
unintelligible plaintext. He now turns his attention to the other words in the
ciphertext. If he decrypts PZ with d = 7, he gets is, while d = 19 yields wg. So
he chooses d = 7 and decrypts the ciphertext to find the plaintext message5 .
Alternatively, if he had thought for a moment, he might have spotted that H
probably represents a or i (corresponding to d = 7 or d = 25, respectively) and,
testing d = 7, he would have decrypted the message with ease.
In this example, the words fake and toys are translates of one another. We
know of no pairs of English words of length six or more that are translates of
each other, and only a few of length four or five.
n-gram substitution
Example 4.2.3 Suppose that part of the key for a digram encryption scheme
looks like this:
6
And 263 trigrams, and, in general, 26n n-grams.
Fundamentals of cryptology 87
a b ··· x y z
.
.
.
c MZ BQ JA DD FK
d IA DT TB AT ZS
e LP SX AM EO BR
.
.
.
k BA AC QP MN LA
l WF EH GO BJ RE
m CT MB CW HP IS
.
.
.
Then the word lady would be encrypted as WFAT.
An array for decryption can easily be obtained from the encryption array.
Permutation ciphers
A block cipher is an encryption scheme in which the plaintext message is
broken up into blocks of a fixed length d, each of which is then encrypted
separately. All of the encryption schemes that we have seen so far have been
block ciphers, e.g., in a digram substitution scheme, each block has length
d = 2. We now describe another block cipher: the permutation cipher.
Let d be a positive integer. Divide the message M into blocks of length
d. Then take a permutation π of 1, 2, 3, . . . , d and apply π to each block.
Specifically, if the plaintext block is x1 x2 · · · xd , then the corresponding ci-
phertext block is xπ(1) xπ(2) · · · xπ(d) .
Example 4.2.4 Let d = 4 and π = (2413). Suppose that the message we want
to encrypt is
he is a great mathematician.
We make sure (i) we remember which symbols are spaces, and, (ii) that we pad
the message so that its length is a multiple of the block length, 4:
he-is-a-great-mathematician-.
Next we divide the message up into blocks of length 4:
he-i s-a- grea t-ma them atic ian-.
88 MATH236 Discrete Mathematics with Applications 2009
We now apply the permutation (2413) to each block. This means that the first
letter in the ciphertext block is the second letter in the plaintext block, the second
letter in the ciphertext block is the fourth letter in the plaintext block, and so
on:
plaintext he-i s-a- grea t-ma them atic ian-
ciphertext EIH- --SA RAGE -ATM HMTE TCAI A-IN
To decrypt, we apply the inverse
µ ¶
−1 1 2 3 4
π =
3 1 4 2
to each block of the ciphertext to recover the original message:
he-i s-a- grea t-ma them atic ian-.
Once we represent the alphabet using numbers (Table 4.2.3), this allows us to
‘add’ two letters together using arithmetic modulo 26, frequently abbreviated
as arithmetic (mod 26), which we now define. Let Z26 = {0, 1, . . . , 25},
and for two numbers x, y ∈ Z26 define x + y mod 26 to be the number
(x + y) mod 26, i.e, we add the two numbers x and y together and then find
the remainder when the result is divided by 26.
Example 4.2.8
the shift or key (modulo 26) to each number. To decrypt, we convert the
ciphertext to numbers, then subtract the shift or key (modulo 26) from each
number.
penguin of death
Plaintext (letters) p e n g u i n o f d e a t h
Plaintext (numbers) 15 4 13 6 20 8 13 14 5 3 4 0 19 7
Ciphertext (numbers) 22 11 20 13 1 15 20 21 12 10 11 7 0 14
Ciphertext (letters) W L U N B P U V M K O H A O
a≡b (mod n)
Exercises
4.1 Encrypt the message
using
4.2 Indicate how you would decrypt (not attack!) each of the ciphertexts
you generated in Question 4.1.
92 MATH236 Discrete Mathematics with Applications 2009
Solutions
4.1 (a) LWTCHWPAALTIWGTTBTTIPVPXC. . .
(b) ULIFNLJGGUIYLEIIHIIYJDJVF. . .
(c) WNEHSHAWLTELHEEEMREGAIAT. . .
Public-key cryptography
Example 5.1.1 Let p be a large prime number and f (x) a polynomial of high
degree, where f : Zp → Zp . It is easy to calculate f (x) for all x ∈ Zp , but
usually hard to solve f (x) = y for x. The function f is a one-way function. For
example, if we choose f (x) = 2x1553 + 3x1471 − x101 − 1 and p = 17957, it is
very difficult to find x ∈ Z17957 for which f (x) ≡ 12202 (mod 17957).
93
94 MATH236 Discrete Mathematics with Applications 2009
Example 5.1.2 Choose N1 and N2 to be large prime numbers and let S consist
of all ordered pairs (p, q) of prime numbers with N1 ≤ p ≤ q ≤ N2 . Define
f : S → Z by the rule
f (p, q) = pq.
It is easy to calculate f (p, q) for all (p, q) ∈ S. However, if we are given the
number pq (without being told the factors p and q), then it is (in general)
computationally infeasible to find p and q. For example, the number 26547259
is the product of two (relatively small) 4-digit primes p and q. If you wish to
gauge the difficulty of finding p and q, try to factor 26547259. You will find
this easy to do on a computer (especially with a computer algebra system like
Mathematica), but extremely time-consuming by hand.
Now suppose that, instead of using two 4-digit prime numbers, we use two
300-digit prime numbers. Their product will be a number that even a computer
will have tremendous difficulty factoring. This difficulty is the basis of the RSA
cryptosystem, which we shall shortly encounter.
Suppose we are given a one-way function f . One way in which we might try
to ‘get around’ the second property, that it is in general infeasible to solve the
equation y = f (x) for x, is by creating a table of all the pairs (f (x), x): we
work our way through the set S, calculating f (x) for each x ∈ S, and then re-
order the results by increasing f (x). Now, using this table, we can in theory
quickly look up an x for any given f (x). However, when S is large enough,
this approach is not feasible. It requires too much memory to store the table.
For example, suppose that S consists of all 200-digit binary numbers; then
|S| = 2200 . If we write the table in binary and use one molecule to store each
bit (0 or 1) of information, then we still require more molecules than are in
our solar system.
make a copy of the file and thus gain access to all of the user accounts.
Similarly, it is dangerous to encrypt the list of passwords using a symmetric-
key cryptosystem. The key must be stored somewhere on the computer and
a hacker gaining access to the computer can use the key to decrypt the list
of usernames and passwords.
As an alternative, consider the following. Let f be a one-way bijec-
tion whose domain is the set of all possible passwords and suppose that
instead of storing a list of pairs (u, p(u)), the computer stores the list of pairs
(u, f (p(u))). Each time a user logs in:
3. The computer checks the entered name-password pair, (u, f (p0 )), against
the stored name-password pair (u, f (p(u))). If f (p0 ) = f (p(u)), then,
since f is a bijection, p0 = p(u) and the computer allows the user to
login. Otherwise, the computer denies the user access.
An intruder who gains access to the list of pairs (u, f (p(u))) obtains no useful
information. To login as a user u, they must know the password p(u). How-
ever, all they know is the encrypted form of the password, f (p(u)); since f is
a one-way function, it is (for all practical purposes) impossible to determine
p(u) from f (p(u)).
Example 5.1.3 Suppose that each password is a pair (p, q) of large prime num-
bers and that the one-way function is f (p, q) = pq. Then for the user angus with
password (2879, 9221), the computer would create the entry (angus, 26547259).
The primes 2879 and 9221 (the factors of 26547259) would not be stored on
the computer. An intruder who hacked into the system and wanted to login as
angus would be faced with the task of factoring the number 26547259.
the bank over the next week. As business networks grew in size,
as more messages were sent, and as more keys had to be deliv-
ered, the banks found that this distribution process became a
horrendous logistical nightmare, and the overhead costs became
prohibitive.
2. C decrypts the message using the key KA , then re-encrypts it with the
key KB .
With this setup, only n keys need to be exchanged and stored. But there are
some problems: the key centre C knows the contents of every message sent
between the other parties; even if C is deemed trustworthy1 , an opponent
who gains access to C’s list of keys will be able to read every message on the
network.
1. They first pick two positive integers, Y and P . There is no need (as you
will see) for them to keep this information secret, so they could do this
on the telephone or by email or by placing a succession of page-length
ads in the New York Times.
Example 5.3.1 Suppose that Alice calls Bob one morning and they agree, over
the phone, that Y = 13 and P = 29. She hangs up. While she is choosing her se-
cret number, A = 12, Bob, after some thought, decides that B = 17. Alice now
computes α = Y A mod P = 1312 mod 29 = 23298085122481 mod 29 = 23.
Similarly, Bob determines β = 1317 mod 29 = 8650415919381337933 mod 29 =
22. Alice calls Bob again. She tells him that α = 23; he replies that β = 22.
She hangs up again. She now computes α0 = β A mod P = 2212 mod 29 =
12855002631049216 mod 29 = 16. In the meantime, Bob (after finishing
his morning cup of coffee) works out β 0 = αB (mod P ) = 2317 mod 29 =
141050039560662968926103 mod 29 = 16. Both of them now know the secret
key to be used between them is 16.
The security of Diffie-Hellman key exchange rests on the intractability of the
Discrete Logarithm Problem, about which we shall have more to say later.
2
Actually, it’s a little more complicated than this, but not much. The details can be
found in the Handbook of Applied Cryptography.
Public-key cryptography 99
3. If the ciphertext C and the private key pri(A) are known, it should be
easy to compute the plaintext P = Dpri(A) (C).
While Diffie and Hellman were the first to publicly3 propose the idea of a
public-key cryptosystem, in order to actually construct a public-key cryp-
tosystem, they needed a trapdoor one-way function and, at the time their
paper was published, they had been unable to find one. It would be a year
later when three researchers on the East coast constructed the first public-key
cryptosystem.
Thus Adleman, Rivest, and Shamir became Rivest, Shamir, and Adleman,
and their cryptosystem became known by the acronym RSA. Almost thirty
years later, RSA is the most widely used public-key cryptosystem in the
world5 . The security of the system rests on the belief that there is no efficient
5
Interestingly, while Rivest, Shamir, and Adleman are credited as the inventors of
RSA, they were not the first to come up with the idea. In 1973, Clifford Cocks, a British
102 MATH236 Discrete Mathematics with Applications 2009
Since the n in her private key is the same as the n in her public key,
we shall frequently think of the private key as just the number d and
write pri(Alice) = d.
n = pq = 2773
and
φ(n) = (p − 1)(q − 1) = 2668.
Alice now needs a number e such that 1 < e < 2668 and gcd(e, 2668) = 1. A
good choice is a relatively small prime number; she chooses e = 17 and quickly
checks that 17 - 2668.
The next step is to find her private key d, which satisfies 17d ≡ 1 (mod 2668),
i.e., d is the multiplicative inverse of 17 in Z2668 . Using the Extended Division
Algorithm from the previous chapter we find that d = 157. Thus
She publishes her public key and keeps her private key a secret.
C = M e mod n.
4. To decrypt the ciphertext C she receives from Bob, Alice uses her
private key pri(Alice) = d to find
M = C d mod n.
(notice that we’ve padded the last block). Now Bob encrypts each block M
separately, each time producing an encrypted block C according to the rule
C = M e mod n
= M 17 mod 2773.
4 +1
132517 mod 2773 = 13252 mod 2773
2·23
= (1325) · 1325 mod 2773
23
= (316) · 1325 mod 2773
2
= (28)2 · 1325 mod 2773
= 7842 · 1325 mod 2773
= 192.
The first block is thus encrypted as 0192. The process is repeated for the other
fourteen blocks in the message, yielding the ciphertext
0192 0596 2024 1787 0578 0195 0317 2244 2751 0844 1444
0882 0508 1278 2342
M = C d mod n
= C 157 mod 2773.
106 MATH236 Discrete Mathematics with Applications 2009
For example, the encrypted first block 0192 would be decrypted as follows:
7 4 3 2
192157 mod 2773 = 1922 1922 1922 1922 192 mod 2773
6 4 3 2
= 8152 1922 1922 1922 192 mod 2773
5 4 3 2
= 14782 1922 1922 1922 192 mod 2773
4 4 3 2
= 21332 1922 1922 1922 192 mod 2773
4 3 2
= (2133 · 192)2 1922 1922 192 mod 2773
4 3 2
= 19052 1922 1922 192 mod 2773
3 2
= (1941 · 192)2 1922 192 mod 2773
3 2
= 10902 1922 192 mod 2773
2
= (1256 · 192)2 192 mod 2773
2
= 26742 192 mod 2773
= 14822 192 mod 2773
= 1325
Notice that we have successfully recovered the first block of Bob’s message! You
should now repeat the procedure to decrypt the other fourteen blocks in the
message.
We shall return later to the problem of proving that the RSA system works
as advertised.
RSA Laboratories also recommends that the two primes p and q that com-
prise the modulus n should be of roughly the same length (so for a 1024 bit
modulus n, p and q should be about 512 bits each) and that p and q should
not be extremely close to one another12 .
reading the message will know with certainty that the message was created
by the signer.
Before we explain the mechanics, we introduce some new terminology.
To concatenate means to place end to end. If we concatenate message A
with message B, we denote the result A||B. For example, if A = cat and
B = dog, then A||B = catdog and B||A = dogcat.
Suppose that Alice wants to send Bob a message M in such a fashion
that he is certain that she is the one who sent it, e.g., she might be sending
her bank manager instructions to transfer money out of one of her accounts.
She uses an RSA key pair pub(Alice) = (n, e) and pri(Alice) = d.
1. She begins by representing the message M as an integer in the interval
[0, n − 1] (or breaks it into blocks if it is too long).
2. Using her private key she computes the message signature, Mpri(Alice) =
M d mod n, i.e., she encrypts the message M with her private key.
3. Alice concatenates M with Mpri(Alice) to produce M ||Mpri(Alice) .
4. Assuming that the message M is confidential, she encrypts M ||Mpri(Alice)
with Bob’s public key, pub(Bob); she then sends (M ||Mpri(Alice) )pub(Bob)
to Bob.
We now examine events from Bob’s perspective:
1. Bob receives a message (M ||M 0 )pub(Bob) from someone claiming to be
Alice. He begins by using his private key, pri(Bob), to remove the outer
layer of encryption, recovering M ||M 0 , which he separates into M and
M 0.
2. Bob now encrypts M 0 with Alice’s public key, pub(Alice), i.e., he finds
0
Mpub(Alice) = (M 0 )e mod n and compares it with M , the first half of the
concatenated message he received. There are two possibilities:
0
• Mpub(Alice) = M . Then Bob knows that M 0 was encrypted with
Alice’s private key. Since Alice is the only one who knows Alice’s
private key, this proves that the message M is from Alice.
0
• Mpub(Alice) 6= M . Therefore, either the message M 0 was not en-
crypted with Alice’s private key, or some malicious third party
altered the text M after Alice added her signature; in either case,
Bob knows that the message was not authorized by Alice.
Public-key cryptography 109
Example 5.5.3 Suppose that Alice wishes to send the signed and encrypted
message
give henda money
to Bob, and that
and
and encrypts each block B of length 4 by the rule C = B 157 mod 2773 to
produce the message signature
so that
Since each of the numbers in these blocks is in the range [0, 3232], blocks of
length 4 will work nicely with Bob’s public modulus. Alice now encrypts each
block B with Bob’s public key, using the rule C = B 19 mod 3233 to obtain
(M ||Mpri(Alice) )pub(Bob) = 2920 0156 1304 1312 1189 1477 1719 1131
0373 0127 1984 0997 3079 2118 2410 2578
Let p and q be the prime numbers that comprise the public modulus, i.e.,
n = pq. From Corollary 38, if p does not divide M , then
M p−1 ≡ 1 (mod p).
Raising both sides to the power k(q − 1), we have
M k(p−1)(q−1) ≡ 1k(q−1) (mod p)
≡ 1 (mod p)
14
Which can be downloaded from http://theory.lcs.mit.edu/∼rivest/rsapaper.pdf
112 MATH236 Discrete Mathematics with Applications 2009
so that
M kφ(n) · M ≡ 1 · M (mod p)
which gives, finally,
M kφ(n)+1 ≡ M (mod p). (5.1)
Notice that if p|M , then (5.1) is trivially true, and hence (5.1) is true for all
M . Similarly,
M kφ(n)+1 ≡ M (mod q) (5.2)
holds for all M . Combining (5.1) and (5.2) with Lemma 41, we therefore
have that
as required.
ax ≡ b (mod n).
f (x) = 17x
x f (x)
1130 1305
1131 1365
1132 309
1133 2106
1134 1576
1135 2403
we notice immediately the lack of any perceivable pattern in the values of f (x).
We have already noted that the security of the Diffie-Hellman key exchange
system rests on the difficulty of the Discrete Logarithm Problem:
3. She sets
pub(Alice) = (p, α, αa )
pri(Alice) = a
Example 5.7.1 Suppose Alice chooses the prime p = 149 (which is far too
small, but this is just an example). She must now find a generator α of Z∗149 .
She decides to try α = 5. To determine whether 5 is a generator of Z∗149 ,
she uses Theorem 40 (or, equivalently, the algorithm that follows it). The prime
factorization of 148 is 22 ·37, so she must compute 5148/2 mod 149 = 574 mod 149
and 5148/37 mod 149 = 54 mod 149. She finds that 574 ≡ 1 (mod 149), so
α = 5 is not a generator of Z∗149 . She tries α = 12 and finds that 1274 ≡ 148
(mod 149) and 124 ≡ 25 (mod 149), so she chooses α = 12 as her generator
for Z∗149 . She picks a = 37 and calculates αa = 1237 ≡ 105 (mod 149). Thus,
Notice that someone wishing to deduce Alice’s private key from her public
key must be able to find the number a ∈ {1, 2, . . . , 147} such that 12a ≡ 105
(mod 149), i.e., solve an instance of the Discrete Logarithm Problem.
4. He then computes
γ = αk mod p
and
δ = M · (αa )k mod p.
γ p−1−a mod p.
Example 5.7.2
Key generation: Suppose that Alice chooses p = 2579; she writes 2578 as the
product of 2 and 1289 (which is prime). She tries α = 2, and computes
α2 mod 2579 = 4 and α1289 mod 2579 = 2578, so α generates Z∗2579 .
She picks a = 956, finds 2956 mod 2579 = 1272, and so publishes the
information
pub(Alice) = (2579, 2, 1272))
while keeping
pri(Alice) = 956
to herself.
nuts
1421 2019
and encrypt each block separately. For additional security, he will select
a different value of k for each block. For the first block, M1 = 1421,
he picks k1 = 318, while for the second block, M2 = 2019, he will use
k2 = 1905. Thus, for the first block, he finds
γ1 = αk1 mod p = 2318 mod 2579 = 792
δ1 = M1 (αa )k1 mod p = 1421 · 1272318 mod 2579 = 590
and, for the second block,
γ2 = αk2 mod p = 21905 mod 2579 = 1035
δ2 = M2 (αa )k2 (mod p) = 2019 · 12721905 mod 2579 = 1684
Bob sends Alice the message
(792, 590), (1035, 1684)
or, equivalently, he could concatenate everything and send Alice the number
0792059010351684.
and then
Similarly,
nuts
Notice that since k is chosen randomly for each encryption, the same message
M would probably be encrypted differently if it was sent from Bob to Alice
a second time. This is an advantage that the El Gamal system has over RSA
encryption. On the other hand, ciphertext generated with the El Gamal
system is twice as long as the plaintext.
118 MATH236 Discrete Mathematics with Applications 2009
Exercises
5.1 Alice and Bob agree to use Diffie-Hellman key-exchange to agree on a
secret key. They decide that Y = 8 and P = 11. Alice chooses A = 5
and Bob chooses B = 3. Find the shared secret key.
5.2 Alice wants to set up an RSA key-pair. Suppose she chooses p = 73,
q = 89, and e = 23.
(a) Chuck wants to send Delia the signed and encrypted message
I will buy your penguin
using Table 5.1 (on p104) and blocks of length 4. Determine the
message he sends her.
(b) Delia receives the signed and encrypted message
Public-key cryptography 119
1377109002613383178412301758231404471734023320262869
0856005906532902012710442102087319412215324119490143
from someone claiming to be Chuck. Decrypt it and verify the
signature.
5.4 Choose a pair p, q of three-digit prime numbers from Section 3.4 and
generate your own RSA key-pair.
Solutions
5.1 10
5.3 (a) 1377 1090 0261 2424 2711 1230 1758 3459 1603 1809 1870 3337
0856 0059 0653 1690 2280 1044 2102 1682 0376 0480 1833 1861
(b) the message is i will pay you sixty rand
5.7 (a) Since α2776/2 mod 2777 = 2776 6= 1 and α2776/347 mod 2777 =
1007 6= 1, α generates Z∗2777 .
(b) pub(Alice) = (2777, 3, 244)
(c) pri(Alice) = 9
(d) The ciphertext is 00030863 00091299 00271599 00812022 02432643
07292124 21871395 10070208
(e) The plaintext is no such thing
Chapter 6
Two of the first kinds of cryptosystems that we considered were simple sub-
stitution ciphers and permutation ciphers. Each of them quickly proved
vulnerable to attack. We now consider a new kind of cryptosystem that is
based on them but which is considerably more difficult to attack; so difficult,
in fact, that most modern cryptosystems are of the type we now consider. A
product cryptosystem is a block cipher that repeatedly performs substitutions
and permutations, one after the other, to produce ciphertext.
6.1 Background
In 1973, the US’s National Bureau of Standards1 called for the development
of an “algorithm to be implemented in electronic hardware devices, to be
used for the cryptographic protection of computer data”.
After rigorous testing, the proposal submitted by IBM was adopted in
1977 as the Data Encryption Standard, or DES. DES is based on an earlier
cryptosystem called Lucifer that was developed at IBM by Horst Feistel.
DES became the most widely used cryptosystem in the world. It is used,
for example, to protect PIN’s (Personal Identification Numbers) of banking
clients, telephonic transfers of money, and (of course) communication over
the internet.
1
Now the NIST.
121
122 MATH236 Discrete Mathematics with Applications 2009
6.2 ASCII
Both DES and AES are designed to operate on the binary alphabet Z2 =
{0, 1}, so any message we wish to encrypt with them must first be encoded
as such. There are many ways to accomplish this. Perhaps the most widely
used convention is ASCII, the American Standard Code for Information In-
terchange, which assigns an 8-digit binary number (a byte) to each symbol
we wish to encrypt (see Table 6.2).
Except where otherwise indicated, we’ll assume from this point on that all
of the cryptosystems we consider operate on the binary alphabet Z2 = {0, 1}.
• A block length, t.
• A number of rounds, r.
Product cryptosystems. DES and AES 123
Li = Ri−1
and
– K1 in round 1,
– K2 in round 2, and, in general,
– Ki in round i,
we use
– Kr in round 1,
Product cryptosystems. DES and AES 125
Ok
f (b1 , b2 , b3 , b4 ) = (b2 , b1 ⊕ b3 , 0, b1 ⊕ b2 )
(for simplicity, we have chosen a round function that has no explicit dependence
on a key).
She begins by encoding the message in ASCII as
0100111101101011.
Her Feistel cipher will operate on blocks of length 2t = 8, so she breaks the
message into two bytes2 ; she will encrypt each separately. Consider the first
byte: 01001111. She has
L0 = 0100
R0 = 1111
Thus,
L1 = R0 = 1111
R1 = L0 ⊕ f (R0 ) = 0100 ⊕ f (1111) = 0100 ⊕ 1000 = 1100
i Li Ri
0 0100 1111
1 1111 1100
2 1100 0011
3 0011 1000
2
A byte is eight bits.
126 MATH236 Discrete Mathematics with Applications 2009
Example 6.3.2 Continuing from the preceding example, suppose Bob receives
the ciphertext
1000001110100110.
from Alice. To decipher it, he performs the same operations as the encryption
process, but reverses the order in which the round keys are used. In this example,
there are no round keys, so the encryption and decryption processes are identical.
As with encryption, he first breaks the ciphertext up into blocks of length
2t = 8, recovering the two bytes 10000011 and 10100110. Consider the first
one, 10000011. For this byte,
L0 = 1000
R0 = 0011
Then,
L1 = R0 = 0011
R1 = L0 ⊕ f (R0 ) = 1000 ⊕ f (0011) = 1100
Ok
Example 6.4.1 Suppose the first seven bits of a byte in a DES key are 0111011.
There are five 1s, so we would set the last bit to be 0.
Checkbits (and, more generally, checkdigits) allow for the detection of trans-
mission errors. If a DES key is transmitted to a recipient who finds that one
or more of the bytes has even parity, then he knows that a transmission error
has occurred and can request that the key be resent4 .
It follows that in a DES key we are free to decide the value of fifty six of
the sixty four bits. This means there are 256 = 72057594037927936 ≈ 7×1016
DES keys.
Stage 3: The inverse of the initial permutation, IP−1 , is applied to the result
of Stage 2 to produce the final ciphertext.
DES decryption follows exactly the same procedure, except that the round
keys are used in reverse order.
We shall now consider the three stages of DES in more detail.
• and so on.
Product cryptosystems. DES and AES 129
The inverse, IP−1 , of the permutation IP, which is applied in the 3rd stage
of encryption, can easily be determined from the preceding.
2. For each i with 1 ≤ i ≤ 16, the subkeys Ci and Di are determined from
Ci−1 and Di−1 by shifting the bits in Ci and Di left by a predetermined
amount (see Table 6.2).
3. For each i with 1 ≤ i ≤ 16, the round key Ki is found by feeding Ci ||Di
to the permutation PC2 (see below).
The permutations C and D are collectively given the name PC-1, for per-
muted choice 1.
57 49 41 33 25 17 9
1 58 50 42 34 26 18
C= 10 2 59 51 43 35
27
19 11 3 60 52 44 36
63 55 47 39 31 23 15
7 62 54 46 38 30 22
D= 14 6 61 53 45 37
29
21 13 5 28 20 12 4
This notation should be read in the same way as that used for the initial
permutation, IP, i.e., the first bit of C0 = C(K) is the 57th bit of K, the
2nd bit of C0 is the 49th bit of K, the 8th bit of D0 = D(K) is the 7th bit
of K, and so on.
Notice that PC-1 does not contain any numbers that are congruent to
0 modulo 8. This is because, as previously discussed, the bits in positions
8,16,24,32,40,48,56, and 64 are parity bits and do not form part of the actual
key.
Key
?
Permuted Choice 1
? ?
C0 D0
? ?
1 left shift 1 left shift
? ?
C1 D1
- Permuted Choice 2 -K
1
? ?
1 left shift 1 left shift
? ?
C2 D2
- Permuted Choice 2 -K
2
? ?
2 left shifts 2 left shifts
? ?
C3 D3
- Permuted Choice 2 -K
3
? ?
.. ..
. .
(notice that each byte of this DES key has odd parity). Then
Ci = L(Ci−1 , `i )
Di = L(Di−1 , `i )
Example 6.6.3 We continue from Example 6.6.1. We must first find C1 ; from
Table 6.2, we see that
C1 = 0111100011101101001101100010.
D1 = 0101010001101111011010010001.
i `i i `i
1 1 9 1
2 1 10 2
3 2 11 2
4 2 12 2
5 2 13 2
6 2 14 2
7 2 15 2
8 2 16 1
i Ci Di
0 0011110001110110100110110001 1010101000110111101101001000
1 0111100011101101001101100010 0101010001101111011010010001
2 1111000111011010011011000100 1010100011011110110100100010
3 1100011101101001101100010011 1010001101111011010010001010
4 0001110110100110110001001111 1000110111101101001000101010
5 0111011010011011000100111100 0011011110110100100010101010
6 1101101001101100010011110001 1101111011010010001010101000
7 0110100110110001001111000111 0111101101001000101010100011
8 1010011011000100111100011101 1110110100100010101010001101
9 0100110110001001111000111011 1101101001000101010100011011
10 0011011000100111100011101101 0110100100010101010001101111
11 1101100010011110001110110100 1010010001010101000110111101
12 0110001001111000111011010011 1001000101010100011011110110
13 1000100111100011101101001101 0100010101010001101111011010
14 0010011110001110110100110110 0001010101000110111101101001
15 1001111000111011010011011000 0101010100011011110110100100
16 0011110001110110100110110001 1010101000110111101101001000
134 MATH236 Discrete Mathematics with Applications 2009
Example 6.6.4 Continuing our example: The round key K3 is equal to PC2(C3 ||D3 ).
Since
C3 ||D3 = 11000111011010011011000100111010001101111011010010001010,
we find
K3 = 011110010101010001111111101001010010111001100110.
1. The 32-bit string Ri−1 is expanded to a 48-bit string using the expansion
function, E (see below).
2. The resulting 48-bit string, E(Ri−1 ), is XORed with the round key, Ki ,
and the result is split into eight 6-bit strings B1 , B2 , . . . , B8 , i.e.,
B1 B2 · · · B8 = E(Ri−1 ) ⊕ Ki .
3. Each 6-bit string Bi is sent through an S-box6 . There are eight S-boxes,
S1 , S2 , . . . , S8 (see below), one for each Bi . The S-box Si operates on
the 6-bit string Bi to return a 4-bit string Si (Bi ).
4. Finally, the eight 4-bit strings S1 (B1 ), S2 (B2 ), . . . , S8 (B8 ) are concate-
nated to produce a 32-bit string which is then permuted using (yet
another) predetermined permutation, P (see below), to produce the
final result,
The procedure is represented in Figure 6.2. As before, we now give the details
of each of the steps in calculating fKi (Ri−1 ).
The notation is the same as for the other DES built-in functions.
6
For ‘substitution box’.
136 MATH236 Discrete Mathematics with Applications 2009
?
º·
E
¹¸
?
E(Ri−1 ) (48 bits) Ki (48 bits)
L
- ¾
S1 S2 S3 S4 S5 S6 S7 S8
?
º·
P
¹¸
?
fKi (Ri−1 ) (32 bits)
The S-boxes S1 , S2 , . . . , S8
S1
14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13
S2
15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10
3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5
0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15
13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9
S3
10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8
13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1
13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7
1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12
S4
7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15
13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9
10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4
3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14
S5
2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9
14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6
4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14
11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3
S6
12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 11
10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8
9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6
4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13
138 MATH236 Discrete Mathematics with Applications 2009
S7
4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1
13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6
1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2
6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12
S8
13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7
1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2
7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8
2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11
Each S-box consists of four rows and sixteen columns. The rows are numbered
0,1,2, and 3 and the columns are numbered 0,1,2, . . . , 15. The input to an
S-box Si is a 6-bit string, Bi , but the output is a 4-bit string, Si (Bi ). The
notation used for the S-boxes is different to the notation used for the other
DES functions we’ve encountered. Here’s how to find the output of an S-box,
given an input Bi = b1 b2 b3 b4 b5 b6 :
1. The binary number b1 ||b6 formed by concatenating the first and last
bits of Bi is a decimal number r between 0 and 3.
2. The binary number b2 ||b3 ||b4 ||b5 similarly represents a decimal number
c between 0 and 15.
3. The number in row r and column c of Si is a decimal number between
0 and 15, which can be written as a 4-digit binary number, d. The
number d is the output Si (Bi ) of the S-box.
Example 6.6.5 Suppose that B4 = 110110. Then we must use the S-box S4 .
Looking at the string B4 , we have b1 ||b6 = 10, which is the decimal number 2.
Furthermore, b2 b3 b4 b5 = 1011, which is the decimal number 11. We thus find
the number in row 2, column 11 of S4 , which is 14. The decimal number 14 is
the 4-bit binary number 1110. Thus,
S4 (B4 ) = S4 (110110) = 1110.
Product cryptosystems. DES and AES 139
The permutation P
The 32-bit string S1 (B1 )||S2 (B2 )|| · · · ||S8 (B8 ) is permuted in the following
fashion to produce fKi (Ri−1 ):
16 7 20 21 29 12 28 17
1 15 23 26 5 18 31 10
P = 2 8 24 14 32 27
3 9
19 13 30 6 22 11 4 25
The notation for P is what you would expect, i.e., if we let X = S1 (B1 )||S2 (B2 )|| · · · ||S8 (B8 ),
then
• and so on.
6.7.1 Triple-DES
If we denote by EK and DK the (standard) DES encryption and decryption
functions using key K, then triple-DES encrypts a 64-bit block P of plaintext
to a 64-bit block C of ciphertext according to the rule9
C = EK3 (DK2 (EK1 (P ))).
There are three keying options defined for triple-DES:
1. The keys K1 , K2 , and K3 are independent.
2. K1 and K2 are independent, but K1 = K3
3. K1 = K2 = K3
The second option, in which K1 = K3 , is widely used. The resulting 128-bit
triple-DES key consists of the two 64-bit DES keys K1 and K2 . Since K1
and K2 have fifty-six non-parity bits, a 128-bit triple-DES key has 112 data
bits. The keyspace of triple-DES with this keying option (which contains
2112 ≈ 5 × 1033 keys) is so large that it has been estimated10 that a triple-
DES exhaustive key search on a $10 million machine would take roughly 30
billion years. Thus, while DES is no longer considered secure, triple-DES
should be secure for quite some time11 .
Still another way to make DES more secure is to use one of the approved
modes of operation.
9
Actually, there’s more than one way to do this. What we describe here is called
DES-EDE. A variant is DES-EEE, in which C = EK3 (EK2 (EK1 (P ))).
10
In 2003.
11
As of April 2005, triple-DES and AES are the two NIST-approved symmetric-key
cryptosystems, though federal agencies using triple-DES are required to use the third
keying option, i.e., a 192-bit triple-DES key.
Product cryptosystems. DES and AES 141
Pi
-L -
- EK
Ci−1 - Ci
Pi
?
L
Ci−1 - EK - - Ci
To encrypt, we let
Ci = Pi ⊕ zi .
Since we must also send the initialization vector, OFB has a nonzero
message extension. If we transmit a ciphertext block Ci incorrectly,
then there will be an error in the decryption of that block, but no
other blocks will be affected. On the other hand, if we transmit z0
incorrectly, then none of the blocks of the message will decrypt cor-
rectly. The initialization vector can be transmitted in the clear, and if
the parties are communicating simultaneously, some time can be saved
because both can generate the keystream without having to wait for
the message.
6.8 AES
As has been mentioned previously, AES was published as FIPS 197 in 2001.
AES is the successor to DES, and it shares many of the same characteristics.
AES is a block cipher, but has a block length of 128 bits, as compared to
DES’s 64 bits. A DES key is always 64 bits, but an AES key can be 128,
192, or 256 bits. Like DES, AES performs a number of rounds of encryption.
The number of rounds, Nr , depends on the key size. If
Exercises
6.1 Consider the following 5-round Feistel cipher:
• The blocklength is t = 4.
• The cipher has a 20-bit key, K.
• For each integer i ∈ {1, 2, 3, 4, 5}, we obtain the round key Ki from
K by concatenating the bits of K whose position is congruent to
i (mod 5), i.e., if K = k1 k2 k3 · · · k20 , then
K1 = k1 k6 k11 k16
K2 = k2 k7 k12 k17
K3 = k3 k8 k13 k18
K4 = k4 k9 k14 k19
K5 = k5 k10 k15 k20
Yes!
using this Feistel cipher with key K = 01100 10011 11010 01101.
6.2 In this question we consider a DES variant which works exactly the
same way as DES, but with only 3 rounds of encryption instead of the
full 16.
(b) Using the key K from part (a), find the round keys K1 , K2 , and
K3 .
146 MATH236 Discrete Mathematics with Applications 2009
(c) Finally, use the round keys K1 , K2 , and K3 from part (b) to
encrypt the message
Last tut
with a 3-round DES cipher.
Product cryptosystems. DES and AES 147
Solutions
6.1 The first block is the letter Y = 01011001, which encrypts to 11100000.
An Introduction to Graphs
7.1 Introduction
Recent years have seen increased demand for application of mathematics.
Graph theory has proven to be particularly useful to a large number of rather
diverse fields. The exciting and rapidly growing area of graph theory is rich
in theoretical results as well as applications to real-world problems. With the
increasing importance of the computer, there has been a significant movement
away from the traditional calculus courses and toward courses on discrete
mathematics, including graph theory.
One of the primary activities of an applied mathematician in modelling.
In a mathematical mode, we represent or identify a real-life situation or
problem with a mathematical system. One of the best-known examples of
this representation is plane Euclidean geometry which gives useful results for
describing small regions, such as measuring distances.
For a graph theorists, the modelling process involves formulating a prob-
lem in such a way that it can be attacked by techniques of graph theory. This
is not always easy; the way in which the modelling is carried out, and the
degree to which the mathematical model accurately represents the original
problem, varies considerably from problem to problem.
Many real-life situations can be described by means of a diagram con-
sisting of a set of points with lines joining certain pairs of points. Loosely
speaking (we shall be more precise shortly), such a diagram is what we mean
by a graph. Graph theory is one area of mathematics that is particulary
well-suited to model building. The two main themes of this course are the
149
150 MATH236 Discrete Mathematics with Applications 2009
development of graph theory as a subject in its own right, and the modelling
of problems.
Instances of graphs abound: for example, the points might represent
cities with lines representing direct flights between certain pairs of these
cities in some airline system, or perhaps the lines represent pipelines be-
tween certain pairs of these cities in an oil network. On the other hand, the
points might represent factories with lines representing communication links
between them. Electrical networks, multiprocessor computers or switching
circuits may clearly be represented by graphs. In chemistry, graphs may
sometimes be helpful in describing the structure of molecules. A chemical
molecule can be represented as a graph whose ’points’ correspond to the
atoms and whose ’lines’ correspond to the chemical bonds connecting them.
The problem of counting the alkanes (paraffins) Cn H2n+2 is essentially a
tree-counting problem. (Trees are a class of graphs which we will study in
Chapter 3.) For the sociologist, a graph may depict the manner in which
people (or groups of people) exert influence over one another. Graphs can
arise in several seemingly unrelated contexts, such as genetics, ecology, ar-
chaeology, music, and the phasing of traffic lights. In order to investigate
such relationships more deeply, we need to study the theory of graphs in
greater detail.
An important part of learning graph theory is problem solving, and for
this reason a number of problems at the end of most sections have been
included. Many of these are routine exercises, designed to test understanding
of the material in the text, but some are more challenging and less routine.
The large variety of proofs used in this course can help strengthen our use of
mathematical techniques.
G: s v2
¡@
¡ @
v3 ¡
s @s v4
For example, if G is the graph shown in Figure 7.1, then the graphs H1 ,
H2 and H3 shown in Figure 7.2 are all subgraphs of G. (Note that G is
regarded as a subset of itself.)
s v1 s v1
H1 : s v2 H2 : s v2 H3 : s v2
¡@ ¡@
¡ @ ¡ @
v3 s s v4 v3 s¡ @s v4 v3 ¡
s @s v4
For example, if G is the graph shown in Figure 7.1, and H1 and H2 are
the subgraphs of G shown in Figure 7.2, then H1 = hF i and H2 = hW i,
where F = {v1 v2 , v3 v4 } and W = {v2 , v3 , v4 }.
Exercises
An Introduction to Graphs 153
7.1 Draw the graph with vertex set V = {v1 , v2 , v3 , v4 , v5 } and edge set
E = {v1 v2 , v1 v4 , v1 v5 , v2 v3 , v3 v5 , v4 v5 }.
7.2 Write down the vertex set and the edge set of the following graph:
as bs cs
G:
s s s
e d f
7.3 Which of the following graphs are subgraphs of the graph G in Exer-
cise 7.2?
bs as bs
¡@
¡ @
s s s s s¡ @s s s
a b c d d e e d
(a) (b) (c)
7.4 Six university teams A,B,C,D,E and F belong to the same league and
have played a number of matches: A has played C, D and E; B has
played C and E; C has played A, B and D; D has played A, C and E;
E has played A, B and D; F has not yet played. Let G be a graph with
vertex set V = {A, B, C, D, E, F } and let two vertices of G be adjacent
if and only if the corresponding teams have played a match.
Empty graphs.
The empty graph is a graph containing no edges. The empty graph of order n
is denoted by Kn .
s s s
s s s s s s
s s s s s s
K1 K2 K3 K4 K5
Figure 7.4. Empty graphs.
Bipartite graphs.
Of particular importance in applications are bipartite graphs. A bipartite
graph is a graph whose vertex set can be partitioned into two sets V1 and V2
(called partite sets) in such a way that each edge of the graph joins a vertex
of V1 to a vertex of V2 . We can distinguish the vertices in V1 from those in
V2 by drawing the former in black and the latter in white, so each edge is
incident with a black vertex and a white vertex. Some examples are shown
below.
V1
z s }| s{ s c
J J @
@c ¡
s¡ s c
J J
J J s c s c s c
c
c J c Jc ¡
c¡ @@s s c s
| {z }
V2 Figure 7.5. Bipartite graphs.
An Introduction to Graphs 155
Exercises
7.7 Draw the following graphs: (a) K6 (b) K4,4 (c) K2,5
7.8 How many edges does a complete bipartite graph Km,s have?
s s s s
s s s s s ¡¡ @
s s @s
Using the join operation, we see that Kr,s = Kr +Ks . Another illustration
is given in Figure 7.8.
s
©©s
¡
s @ @s s ¡ @
© @s
P P³³ ³
G1 : s G2 : s G1 + G2 : @
sH³PP
¡
³ Ps
¡ @
H@
s¡ H¡s¡
Exercises
7.9 Draw the following graphs: (a) 3K3 (b) K2,2 + K2 (c) K2,3 .
In Figure 7.11, a graph G is shown together with the degrees of its vertices.
158 MATH236 Discrete Mathematics with Applications 2009
2s 3s 4s 1s
¡@ @ ¡@ ¡
G: ¡ @ @¡ ¡
@
s
¡ @s s @¡
¡ s @s s
1 1 3 5 2 0
Figure 7.11. The degrees of the vertices of a graph.
Regular graphs.
We say that a graph is regular if all its vertices have the same degree. In
particular, if the degree of each vertex is r, then the graph is regular of
degree r or is r-regular. Figure 7.12 illustrates some examples of graphs
which are regular of degree r, for various values of r.
s s s s
s s s @
¡ ¡ @s
JJ
J
s s s s ©©Hs J
s s @ @¡s ¡ s
©
H s
H
J
r=1 r=2 r=3
Figure 7.12.
Observe that for the graph G shown in Figure 7.11, n(G) = 10 and
m(G) = 11, while the sum of the degrees of its ten vertices is 22. The fact
that this last number equals 2m(G) is no mere coincidence, as we now show.
Theorem 7.1 In any graph, the sum of all the vertex degrees is equal to
twice the number of edges.
Proof. Every edge is incident with two vertices; hence, when the degrees of
the vertices are summed, each edge is counted twice. 2
hands shaken by the corresponding person, and the sum of the degrees is
the total number of hands shaken. So the handshaking lemma states simply
that the total number of hands shaken is equal to twice the number of hand-
shakes - the reason being, of course, that exactly two hands are involved in
each handshake. There are some important consequences of the handshaking
lemma.
Proof. Let G be a (n, m) graph. If G has no odd vertices, then the result fol-
lows immediately. Suppose that G contains k (≥ 1) odd vertices v1 , v2 , . . . , vk .
If G contains even vertices as well, then denote these by vk+1 , . . . , vn . By
Theorem 7.1,
X k Xn
d(vi ) + d(vi ) = 2m.
i=1 i=k+1
Pn
Since each of the numbers d(vk+1 ), . . . , d(vn ) is even, i=k+1 d(vi ) is even, so
we have
X k X n
d(vi ) = 2m − d(vi )
i=1 i=k+1
is even. However, each of the numbers d(v1 ), d(v2 ), . . . , d(vk ) is odd. Since
the sum of an odd number of odd numbers is odd, if follows that k must
be even; that is, G has an even number of odd vertices. If G has no even
vertices, then we have d(v1 ) + d(v2 ) + · · · + d(vk ) = 2m, from which we again
conclude that k is even. 2
With the aid of Theorem 7.3, we may now present a procedure, or algo-
rithm, that allows us to determine whether a finite sequence of nonnegative
integers is graphical.
2. If all the integers in the sequence are 0, then the sequence is graphical.
5. Delete the first number, say t, from the sequence and subtract 1 from
the next t numbers in the sequence to form a new sequence. Return to
Step 2.
s : 4, 4, 4, 3, 3, 2.
Step 1 is satisfied, and we begin the loop of Steps 2 to 5. The tests in Steps 2
and 3 do not immediately halt us. Proceeding to Step 5, we get
s1 = s01 : 3, 3, 2, 2, 2.
162 MATH236 Discrete Mathematics with Applications 2009
s02 : 2, 1, 1, 2
s2 : 2, 2, 1, 1 (reordering)
s03 : 1, 0, 1
s3 : 1, 1, 0 (reordering)
s4 = s04 : 0, 0.
It should be pointed out that the graph G in Figure 7.13 is not the only
graph with degree sequence s. The graphs G and H of Figure 7.14 both have
the same degree sequence, namely 2, 2, 2, 2, 2, 2. So degree sequences do not
always provide enough information to uniquely describe a graph.
s s s s s
¢A ¢A
G: H: ¢ A ¢ A
s s s s¢ As s¢ As
An Introduction to Graphs 163
Exercises
7.10 For the graph G in the accompanying figure, write down the degrees of
all the vertices and the degree sequence of G. Verify the handshaking
lemma for the graph G.
v2 v6
© ©sHH v4 v5 ©©
s
G : v1 ©
sH
HH©
H
©s s©
HH ©sv7
s © Hs©©
v3 v8
7.11 Suppose we know the degrees of the vertices of a graph G. Is it possible
to determine the order and size of G? Explain.
7.12 Show that in any group of at least two people there must be two who
have exactly the same number of acquaintances in the group.
7.13 Suppose you and your partner attended a party with three other cou-
ples. Several handshakes took place. No one shook hands with himself
(or herself) or his (or her) partner, and no one shook hands with the
same person more than once. After all the handshaking was com-
pleted, suppose you asked each person, including your partner, how
many hands he or she had shaken. Each person gave a different an-
swer.
7.14 Prove that if G is a regular bipartite graph with partite sets V1 and V2 ,
then |V1 | = |V2 |.
7.15 Determine whether the following sequences are graphical. If so, con-
struct a graph with the appropriate degree sequence.
(a) 5, 5, 5, 3, 3, 2, 2, 2, 2, 2
(b) 4, 4, 3, 2, 1, 0
164 MATH236 Discrete Mathematics with Applications 2009
(c) 3, 3, 2, 2, 2, 2, 1, 1
(d) 7, 4, 3, 3, 2, 2, 2, 1, 1, 1
7.6 Connectivity
7.6.1 Introduction
Many of the applications of graph theory involve getting from one vertex to
another in a graph. For example, how can you find the shortest route between
one London Underground station and another? How do you determine the
best route for postal deliveries? In order to formulate general methods for
solving such problems, we need to investigate the concept of connectedness
in a graph; that is, a property of a graph which enables us to proceed from
one vertex to another by a sequence of edges.
Definitions. If all the edges (but not necessarily all the vertices) of
walk are different, then the walk is called a trail. If, in addition, all
the vertices are different, then the trail is called a path. We consider a
single vertex as a trivial path (walk or trail).
The v3 -v4 walk described above is not a trail (since the edge v4 v5 occurs
twice); however, v3 , v2 , v6 , v3 , v4 is a v3 -v4 trail in the graph G of Figure 7.14.
This trail is not a path (since the vertex v3 is repeated). However, v3 , v5 , v4
is a v3 -v4 path. It is also useful to have special terms for those walks or trails
which start and finish at the same vertex.
By definition, every path is a trail and every trail is a walk. Although the
converse of each of these statements fails to hold, we do have a result that
relates walks and paths.
Path graphs.
A path graph is a graph consisting of a single path. The path graph of order n
is denoted by Pn .
s s s s s s s s s s s s s s s
P1 P2 P3 P4 P5
Figure 7.16.
Cycle graphs.
A cycle graph is a graph consisting of a single cycle. The cycle graph of
order n is denoted by Cn (n ≥ 3).
s s s s s s
¢A ¡@
s¡ @s s s
¢ A
¢s As s s s s s s
C3 C4 C5 C6
Figure 7.17.
Exercises
7.17 Give an example of a disconnected graph with four components where
each component is complete.
7.18 Give an example of a disconnected graph with three components where
every two components are isomorphic.
7.19 In the accompanying graph G, give an example of:
(a) a circuit which is not a cycle;
(b) a trail which is not a path; v1
s
(c) a path; (d) a cycle. ©©HHHs
G : v2 HH »»©
©
s » v3
»©
s »Hs©
» s
v4 v5 v6
7.24 Let G be a graph of even order n (i.e., n = 2s for some positive integer s)
such that G has two complete components. Prove that the minimum
size possible for G is m = (n2 −2n)/4. (Hint: Try a calculus argument.)
If G has this size, what does G look like?
7.25 Let G be a graph of order n such that d(v) ≥ (n − 1)/2 for every v ∈
V (G). Prove that G is connected. (Hint: Try a proof by contradiction:
Assume, to the contrary, that G is disconnected. This means that G
has two or more components. What can be said about the number of
vertices in each component?)
7.26 Let G be a graph of order n ≥ 2 such that d(v) ≥ (n − 2)/2 for every
v ∈ V (G). Show that G need not be connected if n is even.
Figure 7.19.
Notice that the diameter of G is the maximum distance between any two
vertices in G. Furthermore, if rad(G) = 1, then G contains a vertex that
is adjacent to every other vertex. In Figure 7.20, the vertices of the graph
G are labelled with their eccentricities. For this graph G, rad(G) = 3 and
diam(G) = 5.
170 MATH236 Discrete Mathematics with Applications 2009
3s 4s
4 sH s5
HH
HH
G: 5 s Hs 3
@ ¡ HHHs
@ ¡ 3
@¡
s
4
Figure 7.20. Eccentricities of vertices.
The next result shows that the diameter of a graph is at most twice its
radius.
Proof. The inequality rad(G) ≤ diam(G) follows directly from the defini-
tions. To verify the inequality diam(G) ≤ 2 rad(G), let u and v be vertices
in G satisfying d(u, v) = diam(G). Furthermore, let w be a central vertex
of G. Since the distance function satisfies the triangle inequality (see Prop-
erty (iii) of Theorem 7.5), diam(G) = d(u, v) ≤ d(u, w) + d(w, v) ≤ 2 e(w) =
2 rad(G). 2
The lower bound of Theorem 7.6 is sharp; that is, there exists a graph
G for which rad(G) = diam(G). In fact, the family Kn , n ≥ 2, of complete
graphs satisfies this equation, as does the family of all cycles. The upper
bound is also sharp. To see this, let G belong to the family of paths of
odd order; that is, G ∼= P2k+1 , k ≥ 1. Then rad(G) = k and diam(G) = 2k.
Hence for each positive integer k, there exists a graph G such that diam(G) =
2 rad(G).
Exercises
7.29 If u and v are adjacent vertices in a graph G, then show that |e(u) −
e(v)| ≤ 1.
8.1 Introduction
Consider the following problem. A traveller wishes to drive from Knysna
in the Cape Province to Graskop in the Eastern Transvaal. Given that the
traveller has a map of South Africa that shows the distance between partic-
ular pairs of cities or towns, how does the traveller determine the shortest
possible route?
In this particular example it may not be too difficult to find the solution
by intelligent guesswork, but such an approach is less likely to succeed as
the road network becomes more and more complicated. In this section we
describe an efficient algorithm which can be used to find the shortest path
between any two vertices in a graph.
173
174 MATH236 Discrete Mathematics with Applications 2009
By ’∞’ we shall mean a number larger than any weight actually occurring in
our calculations.) For example, a graph and its weight matrix are shown in
Figure 8.1, where the weights of the edges are as indicated in the diagram.
v1 1 v2
u u
@ 0 1 2 5
@ 2 1 0 4 ∞
G: 5 @ 4 W (G) =
2 4
@ 0 1
@ 5 ∞ 1 0
u @u
v4 1 v3
P : x = w0 , w 1 , w 2 , . . . , w t = v
1. Set `(x) = 0 and for all v 6= x, set `(v) = ∞ and set S = V (G).
`(x) v2 v3 v4 removed S
from S
Table 8.1.
v d(x, v) Qi
v2 `(v2 ) = 1 x, v2
v3 `(v3 ) = 2 x, v3
v4 `(v4 ) = 3 x, v3 , v4
Table 8.2.
`(x) v1 v2 v3 v4 v5 removed S
from S
Table 8.3.
Our results may be summarised as shown in Table 8.4. Using Table 8.3
we obtain, for each i = 1, 2, . . . , 5, the distance from x to vi and a shortest
x-vi path Qi .
v d(x, v) Qi
v1 `(v1 ) = 18 x, v5 , v1
v2 `(v2 ) = 13 x, v2
v3 `(v3 ) = 19 x, v5 , v1 , v3
v4 `(v4 ) = 15 x, v5 , v4
v5 `(v5 ) = 8 x, v5
Table 8.4.
Lemma 8.2 At the termination of Dijkstra’s algorithm, `(v) is finite for all
v ∈ V (G).
vertices already deleted from S have finite labels. But then there is no edge
from V (G) − S to S (since if such an edge e = uv with u ∈ V (G) − S and
v ∈ S did exist, then when u was selected as the current vertex is Step 3 of the
algorithm, the label `(v) of v would have dropped from ∞ to `(u) + w(uv),
which is finite). Thus there is no path from a vertex of S to a vertex of
V (G) − S. Hence G is disconnected, which produces a contradiction. 2
`(vi+1 ) ≤ `(vi ) + w(vi vi+1 ). If vi+1 6= v, then, since Step 4 can only decrease
labels, `(vi+1 ) still satisfies this inequality when v is chosen. Thus,
This, however, contradicts the fact that v was chosen before vi+1 , so `(v) ≤
`(vi+1 ). Hence vi+1 = v and so
Exercises
8.2 Let G be the weighted graph in the accompanying figure. Use Dijkstra’s
algorithm to compute d(x, v) for each v ∈ V (G) and to determine a
shortest x-v6 path.
The Shortest Path Algorithm 181
v1 2 v2 1 v3
s s s
@ ¡ ¡@ 6
3@@s¡ 6
¡ ¡ @
4¡ @sv4
G: 3 ¡
x ¡ 3
¡
¡1 ¡ ¡
s
¡ ¡
s s¡ 3
v7 10 v6 2 v5
8.3 Let G be the weighted graph with V (G) = {v1 , v2 , . . . , v7 } and weight
matrix W (G) as shown. (i) Draw the weighted graph G.
(ii) Find the distance from v3 to every other vertex of G.
(iii) Find a shortest v3 -v2 path, and a shortest v3 -v7 path.
0 8 1 4 2 7 ∞
8 0 7 1 ∞ ∞ 4
1 7 0 ∞ 2 ∞ ∞
W (G) =
4 1 ∞ 0 ∞ 3 6
2 ∞ 2 ∞ 0 5 ∞
7 ∞ ∞ 3 5 0 4
∞ 4 ∞ 6 ∞ 4 0
8.4 Let G be the weighted graph in the accompanying figure. Use Dijkstra’s
algorithm to compute d(v1 , vi ) for each vi ∈ V (G) and to determine a
shortest v1 -vi path.
v2 2 v4 8 v6
s s s
1¡ @
@
@ 2
¡ @
v1 ¡ @4
G: s 3 1 @ 3 @sv8
@ ¡
@ @ ¡
7 @s s @s¡ 1
v3 5 v5 5 v7
9.1 Introduction
You are designing an oil pipeline. Oil is to be pumped from an unloading
point s to a refinery t. To minimize the possibility that pipe repairs will
completely halt the flow of oil, there will be several routes. There will be
four pumping stations u, v, x and y along the pipelines, which are linked as
shown in Figure 9.1. The arrows indicate the directions in which oil can flow
and the capacities of the section of pipelines are indicate (in 1000 barrels of
oil per hour). The question we are faced with is to determine what is the
maximum volume of oil that can be pumped into the system (through s) per
hour? In this section, we shall develop a method of solving problems of this
type.
uu 5 vu
→
¡@ ¡@
4 ¡¡ @ ¡ @ 3
%
% @ ¡4 &
@
¡ ¡ @
@
s u
¡ ¡
@
@u t
@ ¡ @ ¡
@& ¡ 6 %¡
@&
5@ ¡ @ ¡ 8
¡
@
@u¡ @u
¡
→
x 2 y
Figure 9.1.
183
184 MATH236 Discrete Mathematics with Applications 2009
9.2 Digraphs
Although many problems lend themselves to a graph-theoretic formulation,
the concept of a graph is sometimes not quite adequate. When dealing with
problems of traffic flow, for example, it is necessary to know which roads are
one-way, and in which direction traffic is permitted. We may deal with prob-
lems involving flow in information or water, transport of some commodity,
etc. To deal with such problems, what we need is a graph in which every
edge has been assigned a direction - ”a digraph”. The terminology used for
digraphs is quite similar to that used for graphs.
A digraph D with V (D) = {u, v, w, x} and arc set E(D) = {(u, v), (v, u),
(v, w), (x, v), (x, w)} is shown in Figure 9.2 along with the underlying graph
G of D.
Maximum Flows in Networks 185
u us
®s ©
↓ ↑
D: s ª
v G: s v
¡@& ¡@
%
¡ @ ¡ @
x s¡ → @s w x ¡
s @s w
Proof. When the outdegrees of the vertices are summed, each arc is counted
exactly once, since every arc is incident from exactly one vertex. Similarly,
when the indegrees are summed, each arc is counted just once since every
arc is incident to exactly one vertex. 2
u = u0 , a1 , u1 , a2 , . . . , uk−1 , ak−1 , uk = v
of vertices and arcs that begin with the vertex u and ends with the
vertex v and such that ai = (ui−1 , ui ) for i = 1, 2, . . . , k. The number of
arcs k in the walk is called the length of the walk. The concepts of trail,
path, cycle, and circuits in digraphs are defined analogously to those
in graphs, except that in digraphs, we always proceed in the direction
of the arcs. Note that cycles of length 2 are possible in digraphs.
u = u0 , a1 , u1 , a2 , . . . , uk−1 , ak−1 , uk = v
of vertices and arcs that begin with the vertex u and ends with the
vertex v and such that either ai = (ui−1 , ui ) or ai = (ui , ui−1 ) for i =
1, 2, . . . , k. If ai = (ui−1 , ui ), then we call ai a forward arc; otherwise,
we call ai a backward arc. The number of arcs k in the semiwalk is called
the length of the semiwalk. If the vertices u0 , u1 , . . . , uk are distinct,
then the u-v semiwalk is called a u-v semipath.
where f + (v) denotes the total flow on edges exiting v and f − (v) denotes
the total flow on edges entering v, i.e.,
X X
f + (v) = f (v, w) and f − (v) = f (w, v).
w∈N + (v) w∈N − (v)
For a vertex v ∈ V (D), the net flow out of v is defined as f + (v)−f − (v),
while the net flow into v is defined as f − (v) − f + (v). The value f (N )
of a flow in N is the net flow
f (N ) = f + (s) − f − (s)
Examples of a flow. The zero flow assigns flow 0 to each arc in the network.
Figure 9.3 shows a flow f in a network N . Associated with each arc, we write
an ordered pair where the first number denotes the capacity of the arc and
the second number the flow in the arc. For example, f (u, v) = 1 while
c(u, v) = 5. The value of a flow is f (N ) = f + (s) − f − (s) = 8 − 0 = 8.
uu 5, 1 vu
→
¡@ ¡@
4, 4 ¡ @ ¡ @ 3, 3
%
% ¡
@
&
¡4, 2 @
¡ ¡ @
@
¡
s u ¡
@
@u t
@ ¡ @ ¡
@& ¡ 6, 3 %¡
@&
5, 4@ ¡ ¡
@ ¡ 8, 5
@
@u¡ @ ¡
u
→
x 2, 2 y
Figure 9.3.
while
X X X
f − (v) = f (u, v) + f (u, v) = f (S, S) + f (S, S).
v∈S (u,v)∈(S,S) (u,v)∈(S,S)
Thus,
X X
f (N ) = f + (v) − f − (v) = f (S, S) − f (S, S). 2
v∈S v∈S
f (N ) = f − (t) − f + (t).
while X
f (S, S) = f (t, w) = f + (t).
w∈N + (t)
Proof. By Theorem 9.2, the value of the flow f (N ) equals the net flow out
of S. Thus, f (N ) = f (S, S) − f (S, S) ≤ f (S, S) since f (S, S) ≥ 0. However
by the capacity constraint (1), f (S, S) ≤ c(S, S), whence f (N ) ≤ c(S, S). 2
Figure 9.4.
Exercises
9.1 Let N be the network shown in Figure 9.1, where each arc is labelled
with its capacity function. A function f is defined on the arcs as follows:
f (s, u) = 2 f (s, x) = 2 f (u, v) = 1 f (u, y) = 2
f (v, t) = 2 f (x, v) = 1 f (x, y) = 1 f (y, t) = 3
Is f a flow? Explain?
9.2 For the network shown below, associated with each arc is an ordered
pair where the first number denotes the capacity of the arc and the
second number the flow in the arc. Determine the values of the flows
a, b and c.
uu 5, a vu
→
¡@ ¡@
4, 3 ¡ @ ¡ @ 3, 3
%
% ¡
@
&
¡4, 2 @
¡ ¡ @
@
s u
¡ ¡
@
@u t
@ ¡ @ ¡
@& ¡ 6,
@&
b %¡
5, 3@ ¡ ¡
@ ¡ 8, c
@
@u¡ @ ¡
u
→
x 2, 1 y
9.3 Consider the network N shown below, where as before the first number
associated with an arc a is its capacity c(a) and the second number its
flow f (a). Use Corollary 9.5, to show that the given flow is a maximum
flow and find the corresponding minimum cut.
192 MATH236 Discrete Mathematics with Applications 2009
uu 5, 0 vu
→
¡@ ¡@
4, 4 ¡ @ ¡ @ 3, 3
%
% ¡
@
&
¡4, 3 @
¡ ¡ @
@
s u
¡ ¡
@
@u t
@ ¡ @ ¡
@& ¡ 6, 4 %¡
@&
9, 5@ ¡ ¡
@ ¡ 8, 6
@
@u¡ @ ¡
u
→
x 2, 2 y
P : s, (s, x), x, (x, v), v, (u, v), u, (u, y), y, (y, t), t
Theorem 9.6 (Ford and Fulkerson, 1956) In every network, the value of a
maximum flow equals the capacity of a minimum cut.
2. Label s with (−, ∞) and add s to L, the list of labelled and unscanned
vertices.
Maximum Flows in Networks 195
3. Select and remove the first element of L, say u, with label (x+ , ²(u)) or
(x− , ²(u)). If L is empty, then stop. Otherwise, continue.
(a) To all vertices v that are unlabelled and such that (u, v) ∈ E and
f (u, v) < c(u, v), assign the label (u+ , ²(v)), where
s = u0 , a1 , u1 , a2 , . . . , un−1 , an−1 , un = t.
Figure 9.5.
Figure 9.6.
Figure 9.7.
Figure 9.8.
Figure 9.9.
uu 5, 0 vu
→
¡@ ¡@
4, 4 ¡ @ ¡ @ 3, 3
%
% ¡
@
&
¡4, 3 @
¡ ¡ @
@
¡
(−, ∞) s u ¡
@
@u t
@ ¡ @ ¡
@& ¡ 6, 4 %¡
@&
5, 5@ ¡ ¡
@ ¡ 8, 6
@
@u¡ @ ¡
u
→
x 2, 2 y
Figure 9.10.
xu
¡@
106 , 0 ¡ @ 106 , 0
% ¡ &
@
¡ @
s ¡
u 1, 0 @u t
@ ↓ ¡
@& %¡
106 , 0@ ¡106 , 0
@
@¡u¡
y
Figure 9.11.
200 MATH236 Discrete Mathematics with Applications 2009
Exercises
9.4 For the networks shown below, associated with each arc is an ordered
pair where the first number denotes the capacity of the arc and the
second number the flow in the arc. Starting with the given flow, use
the Edmonds-Karp algorithm to find a maximum flow and a minimum
cut for these networks.
u 6, 2 v
v → v
¡@
¡ ¡@
5, 2 ¡ @ % ¡ @ 2, 2
¡ @
%
¡ @ 3, 0 &
@
@ ¡
¡ @
@ ¡
(i) s v
¡ ¡
@
@v t
@ ¡ @ ¡
@ ¡ ¡
&
@ @ 8, 0 %¡
¡ @
6, 0 @ ¡ & ¡ 7, 0
@ @ ¡
@v¡ → @v ¡
x 1, 0 y
uv 5, 1 xv
←
¡
¡ @
@
6, 2 ¡ @ 9, 5
% ↓ 6, 3
¡ 9, 6 ↑ & @
¡ y v 6, 2 @@v
6, 3 vv 4, 2
(ii) s¡
v ← → ← t
@ ¡
@ ¡
& %
6, 4 @ ↑ 6, 2 6, 2 ↑
@ ¡
¡ 7, 0
@
@v ¡
¡
v
→
w 6, 2 z
Maximum Flows in Networks 201
[2] Berge C., Two theorems on graph theory. Proc. Nat. Acad. Sci. USA 43
(1957), 842–844.
[3] Berge C., Theory of Graphs and its Applications (Methuen, London,
1962), 40–51.
203
204 MATH236 Discrete Mathematics with Applications 2009
[14] Chartrand G. and L. Lesniak, Graphs & Digraphs: Third Edition, Chap-
man & Hall, London (1996).
[16] Diestel R., Graph Theory, Springer, New York, Inc (1997).
[18] Ford L.R. and D. R. Fulkerson, Maximal flow through a network. Canad.
J. Math. 8 (1956), 399–404.
[19] Ford L.R. and D. R. Fulkerson, A simple algorithm for finding maximal
network flows and an application to the Hitchcock problem. Canad. J.
Math. 9 (1957), 210–218.
[21] Frank A., Connectivity and network flows, Chapter 2 in the Handbook of
Combinatorics (R.L. Graham, M. Grötschel, and L. Lovász, eds), North
Holland, 1993, pp. 111–178.
[25] Havel, V., A remark on the existence of finite graphs (Czech). Ĉasopis
Pěst. Mat. 80 (1955), 189–194.
[26] Kruskal, J. B., On the shortest spanning subtree of a graph and the
traveling salesman problem. proc. Amer. Math. Soc 7 (1956), 48–50.