Discrete Structures

Lecture Notes
Vladlen Koltun
1
Winter 2008
1
Computer Science Department, 353 Serra Mall, Gates 374, Stanford University, Stanford, CA
94305, USA; [email protected].
Contents
1 Sets and Notation 1
1.1 Dening sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Set operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 More sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 Induction 5
2.1 Introducing induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Strong induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3 Why is the induction principle true? . . . . . . . . . . . . . . . . . . . . . . 8
3 More Proof Techniques 11
3.1 Proofs by contradiction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2 Direct proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4 Divisibility 15
4.1 The division algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.2 Remainders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.3 Greatest common divisors . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.4 Greatest common divisors and linear combinations . . . . . . . . . . . . . . 18
5 Prime Numbers 21
5.1 The fundamental theorem of arithmetic . . . . . . . . . . . . . . . . . . . . 21
5.2 The innity of primes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
6 Modular Arithmetic 25
6.1 Congruences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
6.2 Modular division . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
7 Relations and Functions 31
7.1 Ordered pairs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
7.2 Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
7.3 Kinds of relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
7.4 Creating relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
7.5 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
8 Mathematical Logic 37
8.1 Propositions and predicates . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
8.2 Quantiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
i
8.3 Negations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
8.4 Logical connectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
8.5 Tautologies and logical inference . . . . . . . . . . . . . . . . . . . . . . . . 41
9 Counting 43
9.1 Fundamental principles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
9.2 Basic counting problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
10 Binomial Coecients 49
10.1 Basic properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
10.2 Binomial theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
11 The Inclusion-Exclusion Principle 53
11.1 Statement and proof of the principle . . . . . . . . . . . . . . . . . . . . . . 53
11.2 Derangements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
12 The Pigeonhole Principle 57
12.1 Statements of the principle . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
12.2 Simple applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
12.3 Advanced applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
13 Asymptotic Notation 61
13.1 Denitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
13.2 Examples and properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
14 Graphs 65
14.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
14.2 Common graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
14.3 Some important concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
14.4 Kinds of graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
15 More GraphsEulerian, Bipartite, and Colored 69
15.1 Eulerian graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
15.2 Graph coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
15.3 Bipartite graphs and matchings . . . . . . . . . . . . . . . . . . . . . . . . . 71
16 Trees 75
16.1 Basic properties of trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
16.2 Spanning trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
17 Planar Graphs 79
17.1 Drawing graphs in the plane . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
17.2 Eulers formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
17.3 Coloring planar graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
17.4 Concluding remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
ii
Chapter 1
Sets and Notation
1.1 Dening sets
Denition. A set is an unordered collection of distinct objects. The objects in a
set are called the elements, or members, of the set. A set is said to contain its elements.
A set can be dened by simply listing its members inside curly braces. For example,
the set 2, 4, 17, 23 is the same as the set 17, 4, 23, 2. To denote membership we
use the symbol, as in 4 2, 4, 17, 23. On the other hand, non-membership is
denoted as in 5 , 2, 4, 17, 23.
If we want to specify a long sequence that follows a pattern, we can use the ellipsis
notation, meaning ll in, using the same pattern. The ellipsis is often used after two
or more members of the sequence, and before the last one, as follows: 1, 2, . . . , n.
The pattern denoted by the ellipsis should be apparent at rst sight! For instance,
1, . . . , n is generally regarded as underspecied (that is, too ambiguous). Of course,
even 1, 2, . . . , n is still ambiguousdid we mean all integers between 1 and n, all
powers of two up to n, or perhaps the set 1, 2, 25, n?but is generally sucient,
unless you really do mean all powers of two up to n, in which case 2
0
, 2
1
, 2
2
, . . . , 2
k

for an appropriate k is a better choice. The ellipsis can also be used to dene an
innite set, as in the following.
Denition. The set of natural numbers or nonnegative integers, denoted by N, is
dened as 0, 1, 2, . . ..
To avoid ambiguities it is often useful to use the set builder notation, which lists
on the right side of the colon the property that any set element, specied on the left
side of the colon, has to satisfy. Lets dene the positive integers using the set builder
notation:
N
+
= x : x N and x > 0.
We can also write
N
+
= x N : x > 0.
1
This is a matter of taste. In general, use the form that will be easiest for the reader
of your work to understand. Often it is the least cluttered one.
Ok, now onto the integers:
Z = x : x N or x N.
Hmm, perhaps in this case it is actually better to write
Z = . . . , 2, 1, 0, 1, 2, . . ..
Remember, when you write mathematics, you should keep your readers perspective
in mind. For now, wethe sta of this courseare your readers. In the future it
might be your colleagues, supervisors, or the readers of your published work. In
addition to being reasonably formal and unambiguous, your mathematical writing
should be as clear and understandable to your intended readership as possible.
Here are the rational numbers:
Q =
_
a
b
: a Z, b Z, b ,= 0
_
.
Instead of a Z, b Z, you can write a, b Z, which is more concise and generally
more readable. Dont go overboard, though, with writing something like a, b ,= 0 Z,
this is way too confusing and does not say what you want it to.
Finally, the set of real numbers is denoted by R. All the reals that are not rational
are called irrational. These include the familiar = 3.1415926..., e = 2.7182818...,

2, and innitely many others. (How do we know that these numbers are irrational,
do you ask? Actually, we will see a proof of this for

2 shortly. The proofs for and

e require mathematical analysis and are outside our scope.)
On being formal. Were the above denitions formal enough? The answer is: it
depends. For example, dening the natural numbers is an important and non-trivial
accomplishment of mathematics. After all, what do these symbols 1, 2, 3,
actually mean? These numbers can be formally dened in terms of sets. Even more
involved is the formal denition of the reals, usually covered in a rst mathematical
analysis course.
Here we cannot aord to cover everything in complete detail, which would have to
include, among other things, basic algebra and trigonometry. Furthermore, the vast
majority of mathematical works, while considered to be formal, gloss over details
all the time. For example, youll be hard-pressed to nd a mathematical paper that
goes through the trouble of justifying the equation a
2
b
2
= (a b)(a +b). In eect,
every mathematical paper or lecture assumes a shared knowledge base with its readers
or listeners. It is extremely important for an author of mathematics, such as yourself
during this course, to estimate this shared knowledge base correctly!
In CS103X we will assume most of high-school mathematics, including perhaps
some AP math like single-variable calculus, as our shared knowledge base. Thus
notions and techniques from this base will generally not be justied in lecture, and
can be used freely in your homework and exams. Furthermore, once we develop certain
2
notation or prove some theorem in class, you can use these freely in your homework
and exams, provided that you clearly cite the appropriate theorems. In writing and
speaking mathematics, a delicate balance is maintained between being formal and
not getting bogged down in minutia.
1
This balance usually becomes second-nature
with experience. You should all get the hang of it by the end of the quarter.
1.2 Set operations
A is said to be a subset of B if and only if every element of A is also an element of B,
in which case we write A B. A is a strict subset of B if A is a subset of B and A is
not equal to B, which is denoted by A B. For example, 4, 23 2, 4, 17, 23
2, 4, 17, 23.
Two sets A and B are considered equal if and only if they have the same elements.
This is denoted by A = B. More formally, A = B if and only if A B and B A.
For two sets A and B, the operations of union, intersection, and dierence are
dened as follows:
A B = x : x A or x B
A B = x : x A and x B
A B = x : x A and x , B
The and notation can be extended to the union and intersection of multiple sets.
Given n sets A
1
, A
2
, . . . , A
n
, we can write
n
_
i=1
A
i
for their union, and
n

i=1
A
i
for their intersection. In fact, this notation is pretty exible and the same union can
be written as
n
_
i=1
A
i
=
_
1in
A
i
=
_
i{x : 1xn}
A
i
.
Here is another example:

i {x : 1 x 10}
i is prime
A
i
= A
2
A
3
A
5
A
7
.
Given a set A, the cardinality of A, also known as the size of A, is simply the number
of elements in A. The cardinality of A is denoted by [A[. For example, if A =
2, 4, 17, 23, then [A[ = 4.
1
Of course, what is considered minutia diers from subeld to subeld, and from classroom to
classroom.
3
1.3 More sets
The empty set is denoted by . It is the unique set without elements. It holds that
A for any set A. Why? By denition, this holds if every element of is also an
element of A. Since has no elements, all possible statements about the elements of
are true! In particular, all elements of are also elements of A. If this is confusing
dont worry, we will go into such matters more rigorously when we get to logic. (For
now, you can ponder the following: If we know for a fact that there are no unicorns
<Gasp!>, then it is denitely true that all unicorns have soft light-blue fur.)
A set can contain sets as its elements. For example, 2, 4, 17, 23 is a per-
fectly valid set with three elements, two of them sets. (The second element is
a singleton, a set with one element.) Note that 2, 4 2, 4, 17, 23, but
2, 4 2, 4, 17, 23, and that 17 , 2, 4, 17, 23, but 17 2, 4, 17, 23.
Also, is not the empty set. (Think about it.)
The power set of a set A is the set of all subsets of A, and is denoted by 2
A
. That
is,
2
A
= S : S A.
For example, for A = 2, 4, 17, 23, we have
2
A
=
_
, 2, 4, 17, 23, 2, 4, 2, 17, 2, 23, 4, 17, 4, 23, 17, 23,
2, 4, 17, 2, 4, 23, 2, 17, 23, 4, 17, 23, 2, 4, 17, 23
_
.
The cardinality of this set is 16, and 16 = 2
4
. This is not a coincidence: As we shall
see when we get to combinatorics and counting, for a set A with n elements, the
cardinality of 2
A
is 2
n
. This is in fact the reason for the power set notation.
4
Chapter 2
Induction
2.1 Introducing induction
Suppose there is an innite line of people, numbered 1, 2, 3, . . ., and every person
has been instructed as follows: If something is whispered in your ear, go ahead
and whisper the same thing to the person in front of you (the one with the greater
number). Now, what will happen if we whisper a secret to person 1? 1 will tell it to
2, 2 will tell it to 3, 3 will tell it to 4, and ... everybody is going to learn the secret!
Similarly, suppose we align an innite number of dominoes, such that if some domino
falls, the next one in line falls as well. What happens when we knock down the rst
domino? Thats right, they all fall. This intuition is formalized in the principle of
mathematical induction:
Induction Principle: Given a set A of positive integers, suppose the following
hold:
1 A.
If k A then k + 1 A.
Then all positive integers belong to A. (That is, A = N
+
.)
Here are two simple proofs that use the induction principle:
Theorem 2.1.1. Every positive integer is either even or odd.
Proof. By denition, we are required to prove that for every n N
+
, there exists
some l N, such that either n = 2l or n = 2l + 1. The proof proceeds by induction.
The claim holds for n = 1, since 1 = 2 0 + 1. Suppose the claim holds for n = k.
That is, there exists l N, such that k = 2l or k = 2l + 1. We prove that the claim
holds for n = k + 1. Indeed, if k = 2l then k + 1 = 2l + 1, and if k = 2l + 1 then
k + 1 = 2(l + 1). Thus the claim holds for n = k + 1 and the proof by induction is
complete.
Theorem 2.1.2. Every positive integer power of 3 is odd.
5
Proof. By denition, we are required to prove that for every n N
+
, it holds that
3
n
= 2l + 1, for some l N. The proof proceeds by induction. For n = 1, we have
3 = 2 1 + 1, so the claim holds. Suppose the claim holds for k, so 3
k
= 2l + 1, for
some l N. Then
3
k+1
= 3 3
k
= 3(2l + 1) = 2(3l + 1) + 1,
and the claim also holds for k + 1. The proof by induction is complete.
Proof tip: If you dont know how to get a proof started, look to the denitions,
and state formally and precisely what it is that you need to prove. It might not be
obvious how to prove that Every positive integer power of 3 is odd, but a bit easier
to proceed with proving that for every n N
+
, it holds that 3
n
= 2l + 1, for some
l N. If you need to prove an implication (that is, a claim of the form if . . . then
. . .), then formally state all the assumptions as well as what you need to prove that
they imply. Comparing the two might lead to some insight.
Proof technique: Induction. The induction principle is often used when we are
trying to prove that some claim holds for all positive integers. As the above two proofs
illustrate, when we use induction we do not need to explicitly refer to the set A from
the statement of the induction principle. Generally, this set is the set of numbers for
which the claim that we are trying to prove holds. In the rst proof, it was the set of
numbers n that are either even or odd. In the second proof, it was the set of numbers
n for which 3
n
is odd. Suppose we want to show that some claim holds for all positive
integers. Here is a general template for proving this by induction:
(a) State the method of proof. For example, The proof proceeds by induction.
(b) Prove the induction basis. That is, prove that the number 1 satises the
claim. (This step is often easy, but is crucially important, and should never be
omitted!)
(c) Assume the induction hypothesis. That is, state the assumption that the
claim holds for some positive integer k.
(d) Prove, using the induction hypothesis, that the claim holds for k +1. The proof
should consist of a chain of clear statements, each logically following from the
previous ones combined with our shared knowledge base. The nal statement
in the chain should state that the claim holds for k + 1.
(e) Conclude the proof. For example, This completes the proof by induction.
Theorem 2.1.3. For every positive integer n,
1 + 2 + +n =
n(n + 1)
2
.
6
Proof. The proof proceeds by induction. For n = 1, we have 1 =
12
2
and the claim
holds. Assume 1 + 2 + +k = k(k + 1)/2. Then
1+2+ +k +(k +1) =
k(k + 1)
2
+(k +1) =
k(k + 1) + 2(k + 1)
2
=
(k + 1)(k + 2)
2
,
which proves the claim for k + 1 and completes the proof by induction.
Sigma and Pi notations. Just as the

symbol can be used to compactly express

the union of many sets, the

symbol can be used to express summations. For

example,
1 + 2 + +n =
n

i=1
i =

1in
i =

i{x : 1xn}
i.
You should not assume just because

appears that there is an actual summation,

or that there are any summands at all. For example, when n = 1,

n
i=1
i = 1, and
when n 0,

n
i=1
i = 0 !
Similarly, products can be expressed using the

symbol, as in
2
0
2
1
2
2
... 2
n
=
n

i=0
2
i
.
One thing to be aware of is that the empty product is dened to equal 1, so
1

i=3
i =

i {2, 4, 10, 14}

i is odd
i = 1.
A single

or

symbol can also be used to describe the sum or product over

more than one variable. For example,

1i,jn
(i +j) =
n

i=1
n

j=1
(i +j).
2.2 Strong induction
Suppose that a property P holds for n = 1, and the following is true: If P holds for
all integers between 1 and k, then it also holds for k + 1. Under these assumptions,
P holds for all positive integers. This is the principle of strong induction. It diers
from regular induction in that we can assume something stronger to derive the same
conclusion. Namely, we can assume not only that P holds for k, but that in fact P
holds for all positive integers up to k. We state the strong induction principle more
formally, and then demonstrate its usefulness.
7
Strong Induction Principle: Given a set A of positive integers, suppose the fol-
lowing hold:
1 A.
If 1, 2, . . . , k A then k + 1 A.
Then all positive integers belong to A.
Denition. An integer p > 1 is said to be prime if the only positive divisors of p
are 1 and p itself.
Theorem 2.2.1. Every positive integer greater than 1 can be expressed as a product
of primes.
Proof. The proof proceeds by strong induction. Since 2 is a prime, the claim holds for
2. (Note how the induction basis in this case is 2, not 1, since we are proving a claim
concerning all integers equal to or greater than 2.) Now assume the claim holds for all
integers between 2 and k. If k +1 is a prime then the claim trivially holds. Otherwise
it has a positive divisor a other than 1 and k + 1 itself. Thus, k + 1 = a b, with
2 a, b k. Both a and b can be expressed as products of primes by the induction
hypothesis. Their product can therefore also be thus expressed. This completes the
proof by strong induction.
The versatility of induction. We have seen in the proof of Theorem 2.2.1 that
if we want to prove a statement concerning all positive integers equal to or greater
than 2, we can use induction (or strong induction) with 2 as the base case. This holds
for any positive integer in the place of 2. In fact, induction is an extremely versatile
technique. For example, if we want to prove a property of all even positive integers,
we can use 2 as the base case, and then prove that if the property holds for k, it will
also hold for k + 2. Generally we will just assume that such variations are ok, there
is no need to state a separate induction principle for each of these cases.
Fairly subtle variations of induction are often used. For example, if we can prove
that a statement holds for 1 and 2, and that if it holds for k it will also hold for
k + 2, we can safely conclude that the statement holds for all the positive integers.
However, dont get carried away with variations that are simply incorrect, like using
1 as a base case, proving that if a statement holds for k then it also holds for k + 2,
and then claiming its validity for all positive integers.
2.3 Why is the induction principle true?
Some of you might be surprised by the title question. Isnt it obvious? I mean, you
know, the dominoes are aligned, you knock one down, they all fall. End of story.
Right? Not quite.
Common sense often misleads us. You probably noticed this in daily life, and
youre going to notice it a whole lot if you get into mathematics. Think of optical
8
illusions: we see, very clearly, what isnt really there. Our mind plays tricks on us too,
just like our eyes sometimes do. So in mathematics, we are after proving everything.
To be mathematically correct, every statement has to logically follow from previously
known ones. So how do we prove the induction principle?
The answer lies in the previous paragraph. We said that every statement has
to logically follow from other statements that we have proven previously. But this
cannot go on forever, do you see? We have to start from some statements that we
assume to be true. Such statements are called axioms. For example, why is it true
that for any two natural numbers a, b, c, it holds that a+(b+c) = (a+b)+c? Because
we assume it to be so, in order to build up the rest of mathematics from this and a
small number of other such axioms.
This is also what we do with the induction principle: We accept it as an axiom.
And if we accept the induction principle, strong induction can be proved from it, as
youll discover in the homework.
9
10
Chapter 3
More Proof Techniques
3.1 Proofs by contradiction
The following proof proceeds by contradiction. That is, we will assume that the claim
we are trying to prove is wrong and reach a contradiction. If all the derivations along
the way are correct, then the only thing that can be wrong is the assumption, which
was that the claim we are trying to prove does not hold. This proves that the claim
does hold.
Theorem 3.1.1.

2 is irrational.
Proof. We have seen previously that every integer is either even or odd. That is, for
every n Z there exists k Z, such that either n = 2k or n = 2k +1. Now, if n = 2k
then n
2
= (2k)
2
= 4k
2
= 2 (2k
2
), which means that if n is even then n
2
is also even.
On the other hand, if n = 2k+1 then n
2
= (2k+1)
2
= 4k
2
+4k+1 = 2 (2k
2
+2k)+1,
so if n is odd then n
2
is also odd.
We now proceed with a proof by contradiction. Assume that

2 is rational,
that is,

2 Q. (This is the assumption that should lead to a contradiction.) By

denition, this means that there exist two numbers p, q Z, with q ,= 0, such that
p
q
=

2,
and thus
_
p
q
_
2
= 2.
We can assume that p and q have no common divisor, since all common divisors can
be divided out to begin with. We have
p
2
= 2q
2
.
This shows that p
2
is even, and consequently p must be even; that is, p = 2k for some
k Z. Then
p
2
= 4k
2
= 2q
2
,
11
so
2k
2
= q
2
.
This shows that q
2
is even, and consequently that q is even. Thus both p and q are
even, contradicting the fact that p and q have no common divisor. We have reached
a contradiction, which completes the proof.
Proof Technique: Proof by contradiction. Suppose we want to prove some
statement A by contradiction. A common template for such proofs is as follows:
(a) State the method of proof. For example, The proof proceeds by contradiction.
(b) State the assumption that should lead to the contradiction. For example, As-
sume statement A does not hold.
(c) Proceed with a chain of clear statements, each logically following from the
previous ones combined with our shared knowledge base. The nal statement
in the chain should be a contradiction, either of itself (as in, 0 ,= 0), or of some
previous statement in the chain, or of part of our shared knowledge base.
(d) Conclude the proof. For example, We have reached a contradiction, which
completes the proof.
Theorem 3.1.2. log
2
3 is irrational.
Proof. The proof proceeds by contradiction. Assume that log
2
3 is rational. By
denition, there exist two numbers p, q Z, with q ,= 0, such that
log
2
3 =
p
q
,
which means that
2
p
q
= 3,
and thus
2
p
= 3
q
.
We can assume that p, q > 0. (Indeed, if p/q > 0 then we can just work with [p[ and
[q[, and if p/q 0 we reach a contradiction of the form 3 = 2
p/q
2
0
= 1.) Now, any
positive integer power of 2 is even, because it has 2 as a divisor, so 2
p
is even. On the
other hand, a positive integer power of 3 is odd, as weve seen previously. We have
reached a contradiction.
3.2 Direct proofs
We should not forget perhaps the most intuitive proof technique of all: the direct
one. Direct proofs start out with our shared knowledge base and, by a sequence of
logical derivations, reach the conclusion that needs to be proved. Such proofs are
often particularly ingenious and surprising.
12
Consider the following well-known puzzle question. Take the usual 88 chessboard
and cut out two diagonally opposite corner squares. Can the remaining 62 squares be
tiled by domino-shaped 21 tiles, each covering two adjacent squares of the board?
(That is, each tile can be placed either horizontally or vertically, so as to precisely
cover two squares of the board.)
Theorem 3.2.1. A tiling as above is impossible.
Proof. Every tile covers one white square and one black square. Thus in any tiling as
above, the number of white squares covered is the same as the number of black ones.
The two removed squares have the same color, hence the number of white squares left
on the board is not the same as the number of black ones. So the remaining squares
cannot be tiled.
The above proof can also be phrased as a proof by contradiction, or even in terms
of induction. However, even though such a phrasing might appear more formal, it is
rather unnecessary, as the above proof is already logically sound (which is critical!),
and better conveys the power (and dare I say, the beauty) of the argument.
Proof Technique: Direct proof. Here is a common template for direct proofs:
(a) Provide a chain of clear statements, each logically following from our shared
knowledge base and the previous ones. The nal statement in the chain should
be the claim we need to prove.
(b) (Optional.) Conclude the proof. For example, This completes the proof.
13
14
Chapter 4
Divisibility
4.1 The division algorithm
For the next few lectures we will exercise our ability to prove mathematical state-
ments, using the fertile ground of number theory. In the process we will learn new
proof techniques and tricks of trade. The number-theoretic concepts and results
we will cover will be useful throughout your computer science studies, and, indeed,
throughout your involvement with mathematics.
The following result is commonly known as the division algorithm, even though it
is not an algorithm at all.
Theorem 4.1.1. If a and b are integers and b ,= 0, then there is a unique pair of
integers q and r, such that a = qb +r and 0 r < [b[.
Proof. We need to prove two things: that there is some such pair q, r (existence) and
that this pair is unique (uniqueness).
Lets begin with existence. First we show that there is a pair q, r Z that satises
a = qb +r for some r 0. This is easy after some playing around: Take q = [ab[/b
and r = a + [ab[. Since [b[ 1, it holds that r 0. Now we need to show that such
q, r Z exist with r in addition being smaller than [b[. For this, consider the set
S of all r N that satisfy a = qb + r for some q Z. Weve just shown that S is
nonempty, so it must have a smallest element, call it r
0
. We have a = q
0
b + r
0
. If
r
0
< [b[ were done. Otherwise, we have a = (q
0
b +[b[) +(r
0
[b[), which means that
r
0
[b[ is a smaller element of S than r
0
, leading to a contradiction. This completes
the existence proof.
To prove uniqueness, suppose that a = qb + r = sb + t, with 0 r, t < [b[. Thus
(q s)b +(r t) = 0. Since 0 r, t < [b[, we have [r t[ < [b[, hence [(q s)b[ < [b[
and [q s[ < 1. Since q and s are integers, this implies q = s. From this we have
r = t and the uniqueness proof is complete.
Proof tip: When we need to prove that some mathematical object exists and is
unique, it is useful to approach in two stages. First prove that at least one such object
exists. This can be done either by directly constructing an object and demonstrating
15
that it fullls the requirements, or by assuming that no such object exists and reaching
a contradiction. Then show that any two such objects must be the same.
The Well-Ordering Principle. In proving the division algorithm, we considered
a certain set S N and argued that since it is nonempty, it must have a smallest
element. Why is this true? As with induction, we accept this proposition as an
axiom. In general, the well-ordering principle states that any nonempty set of
natural numbers must have a smallest element. As you will prove in the homework,
the well-ordering principle is equivalent to the principles of induction and strong
induction.
4.2 Remainders
A more algorithmic view of Theorem 4.1.1 is as follows: If we divide the equation
a = qb +r
by b we get
a
b
= q +
r
b
.
Since 0 r < [b[, we get that if b > 0, then 0
r
b
< 1 and thus q =
_
a
b
_
, the greatest
integer less than or equal to
a
b
. If b < 0, then 0
r
b
> 1 and thus q =
_
a
b
_
, the
least integer greater or equal to
a
b
. This can be used to calculate q, from which we
can derive r.
In Theorem 4.1.1, we call q the quotient and r the remainder. We use the notation
r = a rem b to denote that r is the remainder when a is divided by b. There is no
need for a special notation for quotient, since we can just use
_
a
b
_
and
_
a
b
_
, depending
on the sign of b.
Denition: If a and b are such that a rem b = 0 we say that a is a multiple of b,
or that b divides a (or is a divisor of a). Note that this holds when there exists some
integer q, such that a = qb. In particular, every integer divides 0, and every integer
is a multiple of 1. When b divides a we write b[a, and when b does not divide a we
write b,[a.
Denition: An integer u is called a linear combination of a set of integers a
1
, a
2
, . . . , a
n
if and only if there exist integer coecients c
1
, c
2
, . . . , c
n
that satisfy
u =
n

i=1
c
i
a
i
.
Theorem 4.2.1. Properties of divisibility:
(a) If b[a and c[b then c[a.
16
(b) If b[a and a ,= 0 then [b[ [a[.
(c) If b divides each of a
1
, a
2
, . . . , a
n
, then b divides all linear combinations of
a
1
, a
2
, . . . , a
n
.
(d) a[b and b[a if and only if a = b.
Proof. We prove the properties in turn:
(a) Since b[a, there exists an integer q, such that a = qb. Similarly, there exists an
integer r, such that b = rc. Thus a = qb = qrc. Since qr is an integer, it holds
that c[a.
(b) Since b[a, there exists an integer q, such that a = qb. This implies [a[ = [q[ [b[.
Assume for the sake of contradiction that a ,= 0 but [b[ > [a[. Then [q[ [b[ < [b[.
Since [b[ > [a[ > 0, we can divide by [b[ to get [q[ < 1, implying q = 0. Thus
a = qb = 0, which is a contradiction.
(c) Consider a linear combination u =

n
i=1
c
i
a
i
. Since b[a
i
, there exists an integer
q
i
, such that a
i
= q
i
b, for all 1 i n. Thus
u =
n

i=1
c
i
a
i
=
n

i=1
c
i
q
i
b = b
n

i=1
c
i
q
i
.
Since

n
i=1
c
i
q
i
is an integer, we have b[u.
(d) For the if statement, note that if a = b then b = qa and a = qb, for q = 1,
so a[b and b[a. To prove the only if statement, assume that a[b and b[a. This
implies the existence of integers q and r, such that b = qa and a = rb. Thus
b = qrb. If b = 0 then a = 0 and the claim that a = b holds. Otherwise we
can divide by b to get qr = 1. Note that in this case q, r ,= 0. Part (b) of the
theorem implies that [q[ 1 and [r[ 1. Thus q, r = 1 and the claim that
a = b follows.
Proof tip: Often we need to prove that a proposition A holds if and only if some
other proposition B holds. Such an if and only if (sometimes abbreviated as i)
statement is really composed of two implications, each of which needs to be proved.
It is often useful to decouple these and prove them separately. First prove that If A
then B, and then prove that If B then A. Another strategy is to prove that If A
then B and If not A then not B.
4.3 Greatest common divisors
If d[a and d[b then d is a common divisor of a and b. For example, 1 is a common
divisor of any pair a, b. If a and b are not both 0 then, by Theorem 4.2.1(b), any
17
common divisor of a and b is not greater than max([a[, [b[). Thus the set of common
divisors of a and b has a largest element, called the greatest common divisor of a and
b, or gcd(a, b). This is the integer d that satises the following two criteria:
d[a and d[b.
If c[a and c[b then c d.
Note that when a = b = 0, there is no greatest common divisor, since any integer
divides 0. When a and b are not both 0, we often want to compute gcd(a, b) eciently.
Note that the set of divisors of a and a is the same, and similarly for b and b.
Furthermore, if a = 0 then gcd(a, b) = b, and if a = b then gcd(a, b) = a = b. Thus it
suces to concentrate on the case a > b > 0, without loss of generality.
Since 1 gcd(a, b) b, we can just test all integers between 1 and b and choose
the largest one that divides both a and b. However, there is a much more ecient
way to nd greatest common divisors, called Euclids algorithm. This algorithm, one
of the earliest in recorded history, is based on the following lemma.
Lemma 4.3.1. If a = qb +r then gcd(a, b) = gcd(b, r).
Proof. By Theorem 4.2.1(c), all common divisors of b and r also divide a, since a is
a linear combination of b and r. Thus a common divisor of b and r is also a common
divisor of a and b. Similarly, since r = a qb, a common divisor of a and b also
divides r, so it is a common divisor of b and r. Thus a, b and b, r have the same set
of common divisors, and in particular the same greatest common divisor.
With this lemma in our toolbelt, Euclids algorithm is easy to describe. To nd
gcd(a, b), use the division algorithm (Theorem 4.1.1) to represent a = qb + r, where
0 r < b. (Remember that we are assuming that a > b > 0.) If r = 0 then b[a and
gcd(a, b) = b. Otherwise gcd(a, b) = gcd(b, r) and b > r > 0. We can thus repeat the
above procedure recursively with the pair b, r. Every recursive call strictly reduces
both numbers in the pair, so after at most b steps the algorithm will terminate with
a valid greatest common divisor of a and b. You will formally prove the correctness
of the algorithm in the homework.
4.4 Greatest common divisors and linear combi-
nations
We have seen that a common divisor of a and b divides any linear combination of a
and b. Now we will prove a surprising property known as Bezouts identity that shows
that the greatest common divisor of a and b is itself a linear combination of a and b.
Theorem 4.4.1. For two integers a and b that are not both 0, gcd(a, b) is a linear
combination of a and b.
18
Proof. As above, we can concentrate on the case a > b > 0. The proof proceeds by
strong induction on the value of a. In the base case, a = 2, b = 1, and gcd(a, b) =
1 = 0 a + 1 b. Assume that the theorem holds for all pairs a, b with 0 < b < a k.
Consider a pair a

, b

with 0 < b

< a

= k + 1. If b

[a

then gcd(a

, b

) = b

and the
theorem trivially holds. Otherwise use the division algorithm to express a

= qb

+r,
where 0 < r < b

. By the induction hypothesis, there exist coecients u and v, such

that gcd(b

, r) = ub

+ vr. Lemma 4.3.1 shows that gcd(a

, b

) = gcd(b

, r), therefore
gcd(a

, b

) = ub

+vr = ub

+v(a

qb

) = va

+(u vq)b

. This shows that gcd(a

, b

)
is a linear combination of a

and b

and completes the proof by induction.

Bezouts identity implies that the set of linear combinations of a and b is the same
as the set of multiples of their greatest common divisor (!):
Corollary 4.4.2. An integer z is a linear combination of a and b if and only if it is
a multiple of gcd(a, b). In particular, gcd(a, b) is the least positive linear combination
of a and b.
Proof. By Theorem 4.2.1(c), since gcd(a, b) divides both a and b, it divides any linear
combination z of a and b, and thus z is a multiple of gcd(a, b). On the other hand, we
know by Bezouts identity that there are coecients u and v, such that gcd(a, b) =
ua +vb, so if z = c gcd(a, b), then z = c(ua +vb) = (cu)a + (cu)v.
19
20
Chapter 5
Prime Numbers
5.1 The fundamental theorem of arithmetic
Denition: An integer p > 1 is said to be prime if its only positive divisors are 1
and p itself. All other integers greater than 1 are called composite.
A composite number n can be written as a product n = ab of two strictly smaller
numbers 1 < a, b < n. Note that, by convention, 1 is neither prime nor composite.
Here are all primes below 100:
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.
Given a prime p and another integer a, either a is a multiple of p or gcd(p, a) = 1.
Indeed, gcd(p, a) divides p, so it must be either 1 or p, and since gcd(p, a) also divides
a then either gcd(p, a) = 1 or a is a multiple of p. This can be used to prove a very
important property of primes:
Theorem 5.1.1. Let p be a prime.
(a) Given two integers a and b, if p[ab then either p[a or p[b.
(b) Given k integers a
1
, a
2
, . . . , a
k
, if p[

k
i=1
a
i
then p[a
i
for some 1 i k.
Proof.
(a) If p[a we are done. Otherwise gcd(p, a) = 1 and by Bezouts identity there exist
linear coecients u and v for which 1 = ua + vp. Multiplying both sides by b
we get b = uab + vpb. Since p divides ab, p divides the whole sum uab + vpb.
Therefore p[b.
(b) The proof proceeds by induction. The case k = 1 is trivial and k = 2 is handled
in part (a). So we assume that the claim holds for some k > 1 and prove that it
also holds for k + 1. Given that p[

k+1
i=1
a
i
, we put b =

k
i=1
a
i
. Since p[ba
k+1
,
part (a) implies that either p[a
k+1
or p[b. In both cases the claim holds, in the
latter case by the induction hypothesis. This completes the proof by induction.
21
Theorem 5.1.1 can be used to derive a fundamental theorem of number theory. It
is so fundamental it has fundamental in its name.
Theorem 5.1.2 (Fundamental Theorem of Arithmetic). Every positive integer can
be represented in a unique way as a product of primes,
n = p
1
p
2
p
k
(p
1
p
2
. . . p
k
).
Proof. We rst prove existence and then uniqueness. Actually, we already proved
existence in one of the previous lectures as an illustration of strong induction, but
give the prove here again for completeness. So, to prove that every integer can be
represented as a product of primes we use strong induction. The base case n = 1
holds because the empty product, as we previously discussed, is dened to equal 1.
The induction hypothesis assumes that for some n > 1, all positive integers k < n
can be represented as a product of primes. If n is prime, then it is trivially a product
of primes. Otherwise it can be written as n = ab, for 1 < a, b < n. By the induction
hypothesis, both a and b are products of primes, so their product n is also a product
of primes. This proves existence.
The proof that the above representation is unique proceeds by contradiction. As-
sume then that there exists some positive integer that can be represented as a product
of primes in (at least) two ways. By the well-ordering principle, there is a smallest
such integer n. It holds that n = p
1
p
2
p
k
= q
1
q
2
q
l
, where p
1
p
2
. . . p
k
,
q
1
q
2
. . . q
l
, and p
i
,= q
i
for some i. By Theorem 5.1.1(b), since p
i
[q
1
q
2
q
l
,
there must exist some q
j
for which p
i
[q
j
. Since q
j
is prime and p
i
> 1, this can
only occur when p
i
= q
j
. Thus we can eliminate p
i
and q
j
from the equation
p
1
p
2
p
k
= q
1
q
2
q
l
and get two distinct representations of the positive integer
number n/p
i
as a product of primes. This contradicts the assumption that n is the
smallest positive integer with this property, and concludes the proof of uniqueness.
5.2 The innity of primes
Here is another fundamental result with a proof from Euclids Elements:
Theorem 5.2.1. There are innitely many primes.
Proof. Assume for the sake of contradiction that there is only a nite set of primes,
p
1
, p
2
, . . . , p
n
. Consider the number
p = p
1
p
2
. . . p
n
+ 1.
By Theorem 5.1.2, p has a prime divisor, which has to be p
i
, for some 1 i n.
Since p
i
divides both p and p
1
p
2
. . . p
n
, it also divides p p
1
p
2
. . . p
n
= 1. However,
this is impossible since p
i
> 1. This contradiction proves the theorem.
Lets get some more mileage out of Euclids proof. The results below show that
not only do the primes never stop, but the number of primes p x is at least a certain
natural function of x, namely at least log log x. (Here the base of the logarithm is 2.)
22
Theorem 5.2.2. The n-th prime p
n
satises p
n
2
2
n1
for all n 1.
Proof. We proceed using strong induction. For the base case, the rst prime is 2 = 2
2
0
.
Assume that the claim holds for all primes p
1
through p
k
. Consider p = p
1
p
2
. . . p
k
+1.
As in the above proof, p has a prime factor that is not one of the rst k primes. This
prime factor is thus at least as large as p
k+1
, which implies
p
k+1
p = p
1
p
2
. . . p
k
+ 1 2
2
0
2
2
1
2
2
k1
+ 1
= 2
1+2+4+...+2
k1
+ 1
= 2
2
k
1
+ 1
=
1
2
2
2
k
+ 1
2
2
k
.
This is precisely the induction step we needed, and concludes the proof by strong
induction.
Denote by (x) the number of primes p x.
Corollary 5.2.3. For x 2, (x) log log x| + 1.
Proof. Plugging n = log log x| + 1 into Theorem 5.2.2 implies that the n-th prime
is at most x. Thus there are at least n primes below x.
For general education, you should know that this is by far not the best possible
estimate. A celebrated achievement in number theory is the Prime Number Theorem
due to Hadamard and de la Vallee Poussin, which states that x/ ln x (here we use the
natural logarithm) is the right bound, in the sense that
lim
x
(x)
x/ ln x
1.
23
24
Chapter 6
Modular Arithmetic
6.1 Congruences
We usually associate arithmetic with the innite set of integer numbers. However,
modular arithmetic on nite sets is commonly used in our daily life. As an example,
if it is now 1 am and we let 1000 hours pass, what time will it be? We can use the
division algorithm to see that 1000 = 41 24 + 16 and conclude that adding 1000
hours is like adding 16 hours, since the clock returns to the same position every 24
hours. So after 1000 hours it will be 5 pm (17 hours after midnight).
There are many examples in which it is natural and useful to limit our number
system to a nite range of integers, such as 0 through n1, for some n. This number
system is denoted by Z
n
. Days of the week, hours of the day, minutes in an hour
are all familiar examples of nite number systems, as are numbers in microprocessor
registers, commonly limited to 32 binary digits.
Modular arithmetic allows us to add, subtract, multiply, and sometimes divide
numbers while staying within the nite set Z
n
. The number n is called the modulus.
A central notion in modular arithmetic is congruence. We say that two integers are
congruent modulo n if they leave the same remainder when divided by n. Here is the
formal denition:
Denition: Two integers a, b Z are said to be congruent modulo n, written as
a
n
b or a b (mod n), if and only if they leave the same remainder when divided
by n, that is, a rem n = b rem n.
This denition captures our intuition that the day of the week will be the same
whether we let 10, 17, or 80 days pass. There is an equivalent denition of congruence
that is often useful in proofs:
Lemma 6.1.1. a
n
b if and only if n[(a b).
Proof. If a
n
b then a rem n = b rem n. Put r = a rem n = b rem n. Then there
exist two integers q
1
and q
2
, such that a = q
1
n + r and b = q
2
n + r. Subtracting the
second equation from the rst, we get a b = (q
1
q
2
)n and n[(a b).
On the other hand, if n[(ab) then there exists an integer d, such that ab = nd.
By the division algorithm, there exist integers q
1
, q
2
Z, and 0 r
1
, r
2
< n, such
25
that a = q
1
n + r
1
and b = q
2
n + r
2
. Thus (q
1
q
2
)n + (r
1
r
2
) = nd, and r
1
r
2
=
(q
2
q
1
+ d)n. Thus n[(r
1
r
2
). However, [r
1
r
2
[ < n, so necessarily r
1
r
2
= 0,
which implies that a rem n = b rem n, and a
n
b.
You should use the denition to verify that for any a, b, c Z,
a
n
a. (Reexivity.)
If a
n
b then b
n
a. (Symmetry.)
If a
n
b and b
n
c then a
n
c. (Transitivity.)
The operations of addition, subtraction, and multiplication on Z
n
are dened by
rst doing the corresponding operation in Z and then taking the remainder modulo
n. That is, if we denote these respective operations by +
n
,
n
, and
n
, then
a +
n
b = (a +b) rem n
a
n
b = (a b) rem n
a
n
b = (ab) rem n
Exponentiation is dened through repeated multiplication.
Lemma 6.1.2. Properties of congruence:
(a) (a rem n) rem n = a rem n
(b) (a rem n)
n
a
(c) (ab) rem n = (a rem n)(b rem n) rem n
(d) (a rem n)(b rem n)
n
ab
(e)

k
i=1
(a
i
rem n)
n

k
i=1
a
i
(f ) If a
1

n
a
2
and b
1

n
b
2
then
a
1
+b
1

n
a
2
+b
2
a
1
b
1

n
a
2
b
2
a
1
b
1

n
a
2
b
2
Proof. (b) is just a restatement of (a). To prove these we need to show that n[(a
(a rem n)). Put r = a rem n. By the division algorithm, there exists q Z, such that
a = qn +r. Thus a r = qn, which implies that n[a r and concludes the proof.
(d) is a restatement of (c), and (e) can be proved from (d) by induction. To prove
(c) we need to show that n[(ab (a rem n)(b rem n)). Use the division algorithm to
represent a = q
1
n +r
1
and b = q
2
n +r
2
. Then
ab (a rem n)(b rem n) = (q
1
n +r
1
)(q
2
n +r
2
) r
1
r
2
= (q
1
q
2
n +r
1
q
2
+q
1
r
2
)n,
26
which implies the claim.
We now prove (f). We know that n[(a
1
a
2
) and n[(b
1
b
2
). That is, there exist
integers q and s, such that a
1
a
2
= qn and b
1
b
2
= sn. Adding these equations gives
(a
1
+b
1
) (a
2
+b
2
) = (q +s)n, which yields the rst part of the claim. Subtracting
similarly gives the second part. Writing a
1
= a
2
+qn and b
1
= b
2
+sn and multiplying
the equations gives
a
1
b
1
= a
2
b
2
+b
2
qn +a
2
sn +qsn
2
a
1
b
1
a
2
b
2
= (b
2
q +a
2
s +qsn)n,
which yields the third part.
6.2 Modular division
You might have noticed that we dened addition, subtraction, and multiplication, but
not division. This might not be surprising, since the division operation is not dened
for the integers in general: There is no integer that corresponds to 5 divided by 4, for
instance. (In other words, there is no x Z, such that 4x = 5.) This distinguishes Z
from sets like Q or R that are closed under division.
Division in Z
n
appears even more unruly. For example, in Z
6
, the equation 2x = 4
is satised by both x = 2 and x = 5, while the equation 2x = 3 has no solutions.
So the notion of b divided by a can be undened or even ambiguous in Z
n
. In
particular, we cannot generally cancel a multiplier from both sides of a congruence,
that is, if ab
n
ac we cannot reason that b
n
c. To take the above illustration,
2 2
6
2 5, but 2 ,
6
5.
Quite remarkably, however, the division operation is well-dened when n is a
prime p. Thus Z
p
is in a sense as well-behaved as the real numbers, despite being a
nite set! After a small digression that explores what well-behaved actually means
here, we will state an even more general result on modular division.
Digression (notions from abstract algebra): There is a way to precisely state
what we mean by well-behaved above. Jumping the gun, Ill say that Z
p
is a eld,
not just a ring. Now let me tell you what this means. The notion of a ring in algebra
is meant to abstract our intuition concerning the essential properties of the integers.
Given a set S equipped with two operations, + (addition) and (multiplication), we
say that S is a ring if the following all hold for any a, b, c S:
a +b S and a b S.
a + (b +c) = (a +b) +c and a (b c) = (a b) c.
a +b = b +a and a b = b a.
a (b +c) = a b +a c.
There exists an additive identity element 0 S that satises a + 0 = a and a
multiplicative identity element 1 S that satises a 1 = a for all a S.
27
For every a S there exists an additive inverse a S for which a+(a) = 0.
All the number systems we have encountered so far are rings, including Z, Q, R,
and Z
n
. However, some of them possess additional structure that allows the division
operation. Namely, a ring is said to be a eld if, in addition to the above, the following
holds
For every a S, such that a ,= 0, there exists a multiplicative inverse a
1
S
for which a a
1
= 1.
The number systems R and Q, as well as Z
p
when p is prime, are elds. In elds
the division operation is well-dened, and b/a = b a
1
, as can be veried by plugging
x = b a
1
into the equation ax = b. A eld with a nite number of elements is called
a Galois eld, after the French mathematician Evariste Galois. (A feisty young man
who died in a duel at the age of 20, after making signicant enough contributions
to mathematics to have a whole eld (sic) named in his honor!) Anyway, now that
we know what elds are, lets see why Z
p
is one. In fact, we prove something more
general:
Theorem 6.2.1. If a and n are coprime then there exists exactly one x Z
n
for
which ax
n
b, for any b Z.
Proof. We need to prove existence and uniqueness of x as described in the theorem.
ax
n
b if and only if there exists q Z, such that axb = nq, or axnq = b. Now,
since gcd(a, n) = 1, any integer, including b, is a linear combination of a and n. This
proves existence.
To prove uniqueness, assume that for x, y Z
n
it holds that ax
n
b and ay
n
b.
Thus axay
n
0, or n[a(xy). As you proved in one of the homework assignments,
since n and a are coprime, this implies that n[(x y), and therefore that x y
n
0.
Thus x
n
y, which proves uniqueness.
Corollary 6.2.2. For a prime p and any a, b Z, such that a ,
p
0, there exists
exactly one x Z
p
for which ax
p
b.
The fact that division is well-dened in Z
p
when p is prime also means that
cancelations become valid. Thus if a ,
p
0 and ab
p
ac we can safely conclude that
b
p
c.
We now know that b/a is well-dened in Z
p
, but how do we nd it? That is, how
do we nd x Z
p
, for which ax
p
b. This question is particularly important when p
is large and it takes too long to simply enumerate all the elements of Z
p
. Fortunately,
the following result, known as Fermats Little Theorem, can help us:
Theorem 6.2.3. For a prime p and any a ,
p
0,
a
p1

p
1.
Proof. Consider the set S, dened as 1 a, 2 a, . . . , (p 1) a. None of these p 1
integers are congruent modulo p, since we have seen that if ia
p
ja then i
p
j.
28
However, each element of S is congruent to some element of Z
p
. Since there are p 1
elements in S and p 1 nonzero elements in Z
p
, the elements of S must be congruent
to each of 1, 2, . . . , (p 1) in some order. Therefore,
1 2 (p 1)
p
1a 2a (p 1)a,
or
1 2 (p 1)
p
1 2 (p 1) a
p1
.
We can cancel each of 1, 2, . . . , (p 1) from both sides of the congruence, obtaining
a
p1

p
1.
Fermats Little Theorem allows us to quickly perform division in Z
p
. The element
x Z
p
for which ax
p
b is simply (a
p2
b rem p).
29
30
Chapter 7
Relations and Functions
7.1 Ordered pairs
The denition of a set explicitly disregards the order of the set elements, all that
matters is whos in, not whos in rst. However, sometimes the order is important.
This leads to the notion of an ordered pair of two elements x and y, denoted (x, y).
The crucial property is:
(x, y) = (u, v) if and only if x = u and y = v.
This notion can be extended naturally to dene an ordered n-tuple as the ordered
counterpart of a set with n elements.
Give two sets A and B, their cartesian product AB is the set of all ordered pairs
(x, y), such that x A and y B:
A B = (x, y) : x A, y B.
Here is a useful special case:
A
2
= A A = (x, y) : x, y A.
And here is a general denition: A
1
= A, and for n 2,
A
n
=
_
(x
1
, x
2
, . . . , x
n
) : x
1
, x
2
, . . . , x
n
A
_
.
For example, R
2
is the familiar cartesian plane, and R
n
is often referred to as the
n-dimensional Euclidean space. If we omit the parentheses and the commas, a, b
4
is comprised of child babble and a 70s pop band:
aaaa, baba, abab, baaa, baab, aaab, aaba, abaa, abba, bbaa, bbba, bbbb, aabb, abbb, babb, bbab.
Proposition 7.1.1. (A B) C = (A C) (B C)
Proof. Recall that for two sets X and Y , X = Y if and only if X Y and Y X.
Consider any element (u, v) (A B) C. By denition, u A B and v C.
Thus, u A or u B. If u A then (u, v) AC and if u B then (u, v) BC.
31
Thus (u, v) is in A C or in B C, and (u, v) (A C) (B C). This proves
that (A B) C (A C) (B C).
Now consider any element (u, v) (AC) (B C). This implies that (u, v)
A C or (u, v) B C. In the rst case u A and v C and in the second case
u B and v C. Thus u AB and v C, which implies (u, v) (AB)C.
7.2 Relations
Given a set A, a relation on A is some property that is either true or false for any
ordered pair (x, y) A
2
. For example, greater than is a relation on Z, denoted
by >. It is true for the pair (3, 2), but false for the pairs (2, 2) and (2, 3). In more
generality,
Denition 7.2.1. Given sets A and B, a relation between A and B is a subset of
A B.
By this denition, a relation R is simply a specication of which pairs are related
by R, that is, which pairs the relation R is true for. For the relation > on the set
1, 2, 3,
> = (2, 1), (3, 1), (3, 2).
This notation might look weird because we do not often regard the symbol > as a
meaningful entity in itself. It is, at least from the vantage point of the foundations of
mathematics: This symbol is a particular relation.
The common usage of the symbol > (as in 3 > 2) is an instance of a useful
notational convention: For a relation R, (a, b) R can also be specied as aRb.
Thus, in the above example, (2, 1) > can be written as 2 > 1. How convenient!
Common mathematical relations that will concern us include <, >, , , =,
,=, [,
n
, , , etc. For example, the relation = on the set Z is precisely the set
(n, n) : n Z and the relation on R is the set (x, x +[y[) : x, y R.
The concept of a relation is as general as the concept of a set, and is not limited to
strictly mathematical settings. For instance, we can dene the relation likes between
the set Anna,Britney,Caitlyn and the set Austin,Brian,Carlos, such that
likes =
_
(Britney,Austin),(Caitlyn,Austin),(Britney, Carlos),(Anna,Austin),(Caitlyn,Brian)
_
.
In this setting we can write Britney likes Austin.
7.3 Kinds of relations
A relation R on a set A is called
reexive if for all a A, aRa.
symmetric if for all a, b A, aRb implies bRa.
antisymmetric if for all a, b A, aRb and bRa implies a = b.
transitive if for all a, b, c A, aRb and bRc implies aRc.
32
Equivalence relations. A relation that is reexive, symmetric, and transitive is
called an equivalence relation. Clearly, the common relation = on the set R, say, is an
equivalence relation. Also, we have seen earlier that the congruence relation
n
on
the set Z is reexive, symmetric, and transitive, thus it is also an equivalence relation.
The similarity relation on the set of triangles in the plane is another example.
Equivalence relations are special in that they naturally partition the underlying
set into equivalence classes. For example, the relation
2
partitions the integers into
even and odd ones. These are, respectively, the integers that are related (by
2
) to
0, and the ones related to 1. Lets formalize these concepts.
Denition 7.3.1. A partition of a set A is a set A 2
A
, such that
(a) Each a A belongs to some S A.
(b) If S, T A, either S = T or S T = .
Stated dierently, this denition says that the set A is the union of the members
of A, and these members are disjoint. Now, given an equivalence relation R on A,
the equivalence class of a A is dened as
R[a] = b A : aRb.
Theorem 7.3.2. Let R be an equivalence relation on a set A. Then R[a] : a A
is a partition of A.
Proof. Consider an equivalence relation R on A. Due to reexivity, every element
a A belongs to R[a], which implies (a). Now, consider two equivalence classes
R[a] and R[b]. If aRb, then for any c R[a], by transitivity and symmetry, bRc and
c R[b]. This shows R[a] R[b]. We can symmetrically argue that R[b] R[a],
which together implies R[a] = R[b].
Otherwise, if a
/
Rb then consider some c R[a]. If c R[b] then aRc and bRc,
which imply, by transitivity and reexivity, aRb, leading to a contradiction. Thus no
element of R[a] belongs to R[b] and R[a] R[b] = . This shows (b) and concludes
the theorem.
Order relations. A relation that is reexive, antisymmetric, and transitive is called
a partial order. The relations , , and [ on the set Z, as well as the relation on
the powerset 2
A
of any set A, are familiar partial orders. Note that a pair of elements
can be incomparable with respect to a partial order. For example, [ is a partial order
on Z, but 2/[ 3 and 3/[ 2. A set A with a partial order on A is called a partially ordered
set, or, more commonly, a poset.
A relation R on a set A is a total order if it is a partial order and satises the
following additional condition:
For all a, b A, either aRb or bRa (or both).
For example, the relations and are total orders on R, but [ is not a total order
on Z. Finally, a strict order on A is a relation R that satises the following two
conditions:
33
For all a, b, c A, aRb and bRc implies aRc. (Transitivity.)
Given a, b A, exactly one of the following holds (and not the other two): aRb,
bRa, a = b.
The familiar < and > relations (on R, say) are examples of strict orders.
7.4 Creating relations
There are a few ways to dene new relations from existing ones, and we describe two
important such ways below.
Restrictions of relations. Here is one notion that is sometimes useful: Given a
relation R on a set A, and a subset S A, we can use R to dene a relation on S
called the restriction of R to S. Denoted by R[
S
, it is dened as
R[
S
=
_
(a, b) R : a, b S
_
.
Compositions of relations. For three sets A, B, C, consider a relation R between
A and B, and a relation S between B and C. The composition of R and S is a
relation T between A and C, dened as follows: aTc if and only if there exists some
b B, such that aRb and bSc. The composition of R and S is commonly denoted by
R S.
Note that by this denition, the composition of relations on the same set A is
always well-dened. In particular, given a relation R on A we can recursively dene
R
1
= R and R
n
= R
n1
R for all n 2. Now consider the innite union
T =
_
iN
+
R
i
.
This relation T is called the transitive closure of R.
Proposition 7.4.1. Important properties of transitive closure:
(a) T is transitive.
(b) T is the smallest transitive relation that contains R. (That is, if U is a transitive
relation on A and R U, then T U.)
(c) If [A[ = n then
T =
n
_
i=1
R
i
.
34
7.5 Functions
The general concept of a function in mathematics is dened very similarly to relations.
In fact, as far as the denitions go, functions are relations, of a special type:
Denition 7.5.1. Given two sets A and B, a function f : A B is a subset of
A B such that
(a) If x A, there exists y B such that (x, y) f.
(b) If (x, y) f and (x, z) f then y = z.
A function is sometimes called a map or mapping. The set A in the above denition
is the domain and B is the codomain of f.
A function f : A B is eectively a special kind of relation between A and B,
which relates every x A to exactly one element of B. That element is denoted by
f(x).
If the above denition is followed rigidly, particular functions should be dened
by specifying all the pairs (x, f(x)). This is often cumbersome and unnecessary, and
we will mostly continue describing a function from A to B as we did before: as a rule
for picking an element f(x) B for every element x A. As in, Consider a function
f : R R, where f(x) = x
2
for all x R.
Kinds of Functions. For a function f : A B, the set f(A) = f(x) : x A
is called the range of f. The range is a subset of the codomain but may be dierent
from it. If f(A) = B then we say that f is onto. More precisely, a function f : A B
is a surjection (or surjective), or onto if each element of B is of the form f(x) for at
least one x A.
Today is the day of weird names, so: A function f : A B is an injection (or
injective), or one-to-one if for all x, y A, f(x) = f(y) implies x = y. Put dierently,
f : A B is one-to-one if each element of B is of the form f(x) for at most one
x A.
As if this wasnt enough: A function f : A B is a bijection (or bijective), or a
one-to-one correspondence if it is both one-to-one and onto. Alternatively, f : A B
is a bijection if each element of B is of the form f(x) for exactly one x A.
Compositions and Inverse Functions. Given two functions f : A B and
g : B C we can dene a new function g f : A C by (g f)(x) = g(f(x)) for all
x A.
One useful function that can be dened for any set A is the identity function
i
A
: A A, dened by i
A
(x) = x for all x A. We can use identity functions to
dene inverse functions. Specically, if f : A B is a bijection, then its inverse
f
1
: B A is dened so that f
1
f = i
A
and f f
1
= i
B
. Of course, we havent
shown that f
1
even exists or that it is unique, but these properties do hold, assuming
that f : A B is a bijection. (This assumption is necessary.)
35
Another result that is sometimes used is the following: If f : A B and g : B
C are bijections then g f : A C is a bijection, and
(g f)
1
= f
1
g
1
.
We omit the proof.
Bijections and cardinality. Bijections allow us to rigorously dene when two sets
are of the same cardinality:
Denition 7.5.2. Two sets A and B have the same number of elements if and only
if there exists a bijection f : A B.
36
Chapter 8
Mathematical Logic
Perhaps the most distinguishing characteristic of mathematics is its reliance on logic.
Explicit training in mathematical logic is essential to a mature understanding of
mathematics. Familiarity with the concepts of logic is also a prerequisite to studying
a number of central areas of computer science, including databases, compilers, and
complexity theory.
8.1 Propositions and predicates
A proposition is a statement that is either true or false. For example, It will rain
tomorrow and It will not rain tomorrow are propositions, but It will probably
rain tomorrow is not, pending a more precise denition of probably.
A predicate is a statement that contains a variable, such that for any specic
value of the variable the statement is a proposition. Usually the allowed values for
the variable will come from a specic set, sometimes called the universe of the variable,
which will be either explicitly mentioned or clear from context. A simple example
of a predicate is x 2 for x R. Clearly, for any real value of x, this statement is
either true or false. We denote predicates in a similar way to functions, as in P(x).
In fact, the connection to functions runs deep: A predicate P(x) can be considered
a function, P : | 0, 1, where | is the universe of the variable x, 1 represents
truth, and 0 represents falsehood.
A predicate may have more than one variable, in which case we speak of predicates
in two variables, three variables, and so on, denoted as Q(x, y), S(x, y, z), etc.
8.2 Quantiers
Given a predicate P(x) that is dened for all elements in a set A, we can reason about
whether P(x) is true for all x A, or if its at least true for some x A. We can
state propositions to this eect using the universal quantier and the existential
quantier .
x A : P(x) is true if and only if P(x) is true for all x A. This proposition
can be read For all x A, P(x).
37
x A : P(x) is true if and only if P(x) is true for at least one x A. This
proposition can be read There exists x A such that P(x).
Given a predicate in more than one variable we can quantify each (or some) of
the variables. For example, the statement For every real x and y, it holds that
x
2
y
2
= (x y)(x +y) can be formalized as
x, y R : x
2
y
2
= (x y)(x +y).
Somewhat more interestingly, the statement There is no greatest integer might be
formulated as
n Z m Z : m > n.
It is crucial to remember that the meaning of a statement may change if the existential
and universal quantiers are exchanged. For example, m Z n Z : m > n means
There is an integer strictly greater than all integers. This is not only contrary to
the spirit of the original statement, but is patently wrong as it asserts in particular
that there is an integer that is strictly greater than itself.
Exchanging the order of two quantiers of the same type (either universal or
existential) does not change the truth value of a statement. We do not prove this
here.
8.3 Negations
Given a proposition P, the negation of P is the proposition P is false. It is true if
P is false, and false if P is true. The negation of P is denoted by P, read as not
P. If we know the meaning of P, such as when P stands for It will rain tomorrow,
the proposition P can be stated more naturally than not P, as in It will not rain
tomorrow. The truth-value of P can be represented by the following truth table:
P P
true false
false true
A truth table simply lists the truth values of particular statements in all possible
cases. Something interesting can be observed in we consider the truth values of Q,
which can be obtained by using the above table once with P = Q and once with
P = Q:
Q Q Q
true false true
false true false
38
We see that the statements Q and Q have the same truth values. In this case
we say that the two statements are equivalent, and write Q Q. If A B we
can freely use B in the place of A, or A instead of B in our logical derivations.
Negation gets really interesting when the negated proposition is quantied. Then
we can assert that
x A : P(x) x A : P(x)
x A : P(x) x A : P(x)
These can be interpreted as the claim that if P(x) is not true for all x A then it
is false for some x A and vice versa, and the claim that if P(x) is not false for any
x A then it is true for all x A and vice versa. What this means, in particular,
is that if we want to disprove a statement that asserts something for all x A, it is
sucient to demonstrate one such x for which the statement does not hold. On the
other hand, if we need to disprove a statement that asserts the existence of an x A
with a certain property, we actually need to show that for all such x this property
does not hold.
Looked at another way, the above equivalences imply that if we negate a quantied
statement, the negation can be pushed all the way inside, so that no negated
quantiers are left. Indeed, leaving any negated quantiers is often considered a
mark of poor style. Here is how how this elimination is done in a particular example:
n Z m Z : m > n
n Z m Z : m > n
n Z m Z : m n
This can be read as There exists an integer that is greater or equal to any other
integer, which is the proper negation of the original statement.
8.4 Logical connectives
The symbol is an example of a connective. Other connectives combine two propo-
sitions (or predicates) into one. The most common are , , , and . P Q is
read as P and Q; P Q as P or Q; P Q as P xor Q; P Q as P implies
Q or if P then Q; and P Q as P if and only if Q. The truth-value of these
compound propositions (sometimes called sentences) depends on the truth values of
P and Q (which are said to be the terms of these sentences), in a way that is made
precise in the truth-table below.
We will not concern ourselves much with the and connectives, as they are
encountered somewhat less frequently.
One interesting thing about the above table is that the proposition P Q is false
only when P is true and Q is false. This is what we would expect: If P is true but Q
is false then, clearly, P does not imply Q. The important thing to remember is that if
39
P Q P Q P Q P Q P Q P Q
T T T T F T T
T F F T T F F
F T F T T T F
F F F F F T T
P is false, then P Q is true. One way this can be justied is by remembering that
we expect a proposition to be either false or true. Now, P Q being false says that
P does not imply Q, which means precisely that P is true but Q is still false. In all
other cases we expect P Q to be true. (Did I succeed in turning something obvious
into a confusing mess? Well, we all know what is paved with good intentions...)
Now, there is another statement involving P and Q that is false precisely when
P is true and Q is false. It is, of course, P Q. As the following truth table
demonstrates, the proposition P Q is equivalent to P Q:
P Q P Q P Q
T T T T
T F F F
F T T T
F F T T
This means something rather interesting: We can replace a proposition that in-
volves implication by an equivalent one that instead has negation () and disjunction
(). Also, since P Q is false only when P is true and Q is false, the proposition
(P Q) is equivalent to P Q:
(P Q) P Q.
This means that in a negated implication, the negation can be pushed inside,
somewhat like with quantiers. In fact, similar equivalences exist for other negated
compound statements, as can be veried using truth tables (do it!):
(P Q) P Q
(P Q) P Q
These are the famous DeMorgans laws. What they mean is that we can eliminate
negated compounds (sounds like a military operation, doesnt it?) just as we can
eliminate negated quantiers.
Here is another important logical equivalence: The implication P Q is equiva-
lent to the contrapositive implication Q P:
(P Q) (Q P).
This is demonstrated by the following truth table:
40
P Q P Q Q P Q P
T T T F F T
T F F T F F
F T T F T T
F F T T T T
Indeed, an implication of the form If P then Q is sometimes proved by assuming
that Q does not hold and showing that under this assumption P does not hold. This
is called a proof by contrapositive. (Despite the similarity, it is dierent from a proof
by contradiction.)
8.5 Tautologies and logical inference
A sentence that is true regardless of the values of its terms is called a tautology, while
a statement that is always false is a contradiction. Another terminology says that
tautologies are valid statements and contradictions are unsatisable statements. All
other statements are said to be satisable, meaning they can be either true or false.
Easy examples of a tautology and a contradiction are provided by P P and
P P, as demonstrated by the following truth table:
P P P P P P
T F T F
F T T F
Note that by our denition of logical equivalence, all tautologies are equivalent.
It is sometimes useful to keep a special proposition T that is always true, and a
proposition T that is always false. Thus any tautology is equivalent to T and any
contradiction is equivalent to T.
Here is another tautology: (P Q) P:
P Q P Q (P Q) P
T T T T
T F F T
F T F T
F F F T
The statement (P Q) P is read P and Q implies P. The fact that this is
a tautology means that the implication is always true. Namely, if we know the truth
of P Q, we can legitimately conclude the truth of P. In such cases the symbol
is used, and we can write (P Q) P. There is a crucial dierence between
(P Q) P and (P Q) P. The former is a single statement, while the latter
indicates a relationship between two statements. Such a relationship is called an
inference rule. A similar inference rule, P P Q can be established analogously.
41
In general, any tautology of the form A B can be used to manufacture the
inference rule A B that says that if we know A we can conclude B. Similarly,
a tautology of the form A B can be converted into the equivalence A B,
which can be regarded as two inference rules, A B and B A. A particularly
important inference rule is called modus ponens, and says that if we know that P and
P Q are both true, we can conclude that Q is true. It follows from the tautology
(P (P Q)) Q:
P Q P Q P (P Q) (P (P Q)) Q
T T T T T
T F F F T
F T T F T
F F T F T
Weve already seen a number of inference rules above, like (P Q) (Q
P), without calling them that. Here are three others, all corresponding to tautologies
that you are invited to verify using truth tables:
(P T) P
(P Q) (P Q) (Q P)
(P Q) (P Q) (P Q)
These three rules are of particular importance. The rst formally establishes the
validity of proofs by contradiction, and the second and third provide two means for
proving if and only if statements. Weve been using these all along, but now we
know why they are justied.
42
Chapter 9
Counting
9.1 Fundamental principles
The subject of enumerative combinatorics is counting. Generally, there is some set A
and we wish to calculate the size [A[ of A. Here are some sample problems:
How many ways are there to seat n couples at a round table, such that each
couple sits together?
How many ways are there to express a positive integer n as a sum of positive
integers?
There are a number of basic principles that we can use to solve such problems.
The sum principle: Consider n sets A
i
, for 1 i n, that are pairwise disjoint,
namely A
i
A
j
= for all i ,= j. Then

n
_
i=1
A
i

=
n

i=1
[A
i
[ .
For example, if there are n ways to pick an object from the rst pile and m ways to
pick on object from the second pile, there are n+m ways to pick an object altogether.
The product principle: If we need to do n things one after the other, and there
are c
1
ways to do the rst, c
2
ways to do the second, and so on, the number of
possible courses of action is

n
i=1
c
i
. For example, the number of possible three-
letter words in which a letter appears at most once that can be constructed using the
English alphabet is 26 25 24: There are 26 possibilities for the rst letter, then 25
possibilities for the second, and nally 24 possibilities for the third.
The bijection principle: As we have seen, there exists a bijection from A to B if
and only if the size of A equals the size of B. Thus, one way to count the number of
elements in a set A is to show that there is a bijection from A to some other set B
43
and to count the number of elements in B. Often there is no need to explicitly specify
the bijection and prove that it is such: At this point in the course, you can omit some
low-level details from the written proofs in your homework solutions, as long as you
are certain that you could reproduce these details if asked to do so. For example, you
can simply state and use the observation that the number of ways to seat n people
in a row is the same as the number of ways to order the integers 1, 2, . . . , n, which
is the same as the number of n-element sequences that can be constructed from the
integers 1, 2, . . . , n (without repetition), which is the same as the number of bijections
f : A A, for A = 1, 2, . . . , n. You should always make sure that you yourself
fully understand why such equalities hold whenever you use them! Obviously, if you
dont, youll end up relying on equalities that are simply not true, which is not such
a great idea. If in doubt, write down a complete proof to make sure your reasoning
is correct.
9.2 Basic counting problems
Choosing an ordered sequence of distinct objects with repetition. How
many ways are there to pick an ordered sequence of k objects from a pool with n
types of objects, when repetitions are allowed? (That is, we can pick an object of
the same type more than once.) Well, by the product principle, there are n options
for the rst object, n options for the second, and so on. Overall we get n
k
possible
sequences. What follows is a somewhat more formal argument by induction. Observe
that the number of sequences as above is the same as the number of functions from
a set of k elements to a set of n elements. (Make sure you understand this.)
Theorem 9.2.1. Given sets A and B, such that [A[ = k and [B[ = n, the number of
functions f : A B is n
k
.
Proof. Induction on k. If k = 0 the set A has no elements and there is only one
mapping from A to B, the empty mapping. (Recall that a function f : A B is a
subset of A B, and if A = then A B = .) We suppose the claim holds for
[A[ = m and treat the case [A[ = m+ 1. Consider some element a A. To specify a
function f : A B we can specify f(a) B and a mapping f

: A a B. There
are n possible values of f(a) B, and for each of these there are n
m
mappings f

by
the induction hypothesis. This results in n
m+1
mappings f and completes the proof
by induction.
Choosing an ordered sequence of distinct objects without repetition. How
many ways are there to pick an ordered sequence of k objects from a set of n objects
when only one copy of each object is available, so there can be no repetitions? Again
we can use the product principle. Observe that the rst object in the sequence can
be chosen from n distinct objects. Once the rst one is picked, there are only n 1
possibilities for the second object. After that there are n 2 objects to choose from,
44
and so on. Overall we get that the desired quantity is
n(n 1) (n k + 1) =
k1

i=0
(n i).
This is called a falling factorial and denoted by (n)
k
or n
k
. We again provide a more
formal proof by induction, observing that the number of ways to pick an ordered
sequence of k objects from a collection of n distinct ones without replacement is
equal to the number of one-to-one functions f : A B, where [A[ = k and [B[ = n.
Theorem 9.2.2. Given sets A and B, such that [A[ = k and [B[ = n, the number of
one-to-one functions f : A B is (n)
k
.
Proof. Induction on k. When [A[ = 0, there is one mapping f as described, the
empty mapping, and (n)
k
is the empty product, equal to 1. Suppose the claim holds
for [A[ = m and consider the case [A[ = m + 1. Fix an element a A. To specify
f we specify f(a) and a mapping f

: A a B. There are n possible values for

f(a) B. Consider a specic such value f(a) = b. Since f is one-to-one, no element
of A a can be mapped to b. Thus f

has to be a one-to-one-mapping from A a

to B b. By the induction hypothesis, the number of such mappings is (n 1)
m
.
The number of possible mappings f is thus n (n 1)
m
= (n)
m+1
.
Permutations. How many ways are there to arrange n people in a row? How many
ordered n-tuples are there of integers from the set 1, 2, . . . , n? Haw many distinct
rearrangements are there of the integers 1, 2, . . . , n? How many bijections are there
from the set 1, 2, . . . , n to itself? The answer to these questions is the same, and
follows from Theorem 9.2.2. A bijection from a set A to itself is called a permutation
of A. The number of permutations of the set 1, 2, . . . , n is precisely the number of
one-to-one functions from this set to itself, and this number is (n)
n
= n(n1) 21.
This quantity is called n factorial and is denoted by n!. We can now observe that
(n)
k
=
n!
(n k)!
.
It is important to remember that 0! = 1, since 0! is the empty product. Here is a list
of values of n! for 0 n 10:
1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800
Seating at a round table. Weve arranged n people in a row, now its time to sit
them down. So how many ways are there to seat n people at a round table? Lets
be precise about what we mean: Two seating arrangements are considered identical
if every person has the same neighbor to her right. In other words, rotations around
the table do not matter. Here is how this problem can be tackled: Fix one person a
and sit her down anywhere. This now xes n 1 possible positions for the others:
rst person to the right of a, second person to the right of a, and so on until
(n 1)-st person to the right of a. The number of ways to arrange the others in
these n 1 positions is (n 1)!, which is also the answer to the original question.
45
Choosing an unordered collection of distinct objects without repetition.
How many ways are there to pick a set of k objects from a set of n objects? Since we
are picking a set, we do not care about order, and there are no repetitions. Notice
that every such set can be ordered in k! ways. That is, each set corresponds to k!
distinct ordered k-tuples. Now, we know that the number of ordered k-tuples that
can be picked from a collection of n distinct objects is (n)
k
. Thus if we denote by X
the number of sets of cardinality k that can be picked from a collection of n distinct
objects, we get
X k! = (n)
k
X =
(n)
k
k!
X =
n!
k!(n k)!
.
This quantity X is denoted by
_
n
k
_
, read n choose k. This is such an important
quantity that we emphasize it again: The number of k-element subsets of an n-element
set is
_
n
k
_
, dened as
_
n
k
_
=
n!
k!(n k)!
=

k1
i=0
(n i)
k!
.
We can see that
_
n
0
_
=
_
n
n
_
= 1, and we dene
_
n
k
_
= 0 when k > n or k < 0.
The number of subsets. We have seen that the number of k-element subsets of
an n-element set is
_
n
k
_
. How many subsets of an n-element set are there overall, of
any size? Yes, it is time to prove the neat formula weve been using all along:
Theorem 9.2.3. For a set A,

2
A

= 2
|A|
.
Proof. By induction. When [A[ = 0, A = . Hence, A has only one subset (itself)
and the formula holds since 2
0
= 1. Assume the formula holds when [A[ = k and
consider the case [A[ = k + 1. Fix an element a A. A subset of A either contains
a or not. The subsets of A that do not contain a are simply subsets of A a and
their number is 2
k
by the induction hypothesis. On the other hand, each subset of
A that does contain a is of the form a X, for X A a. Thus there is a
bijective mapping between subsets of A that contain a and subsets of A a. The
number of such subsets is again 2
k
. Overall we get that the number of subsets of A
is 2
k
+ 2
k
= 2
k+1
, which completes the proof by induction.
Here is another instructive way to prove Theorem 9.2.3: Consider the set of func-
tions f : A 0, 1. These functions assign a value of 0 or 1 to every element of A.
In this way, such a function f uniquely species a subset of A. Namely, the elements
x for which f(x) = 1 are the elements that belong to the subset of A specied by
f. This denes a bijection between such functions f and subsets of A. By Theorem
9.2.1, the number of functions f from A to 0, 1 is 2
|A|
, which proves Theorem 9.2.3.
46
We can use Theorem 9.2.3 to derive an interesting identity. We now know that
the overall number of subsets of an n-element set is 2
n
. Previously we have seen that
the number of k-element subsets of an n-element set is
_
n
k
_
. By the sum principle, we
get
n

i=0
_
n
i
_
= 2
n
.
Choosing an unordered collection of distinct objects with repetition. How
many ways are there to pick a collection of k objects from a pool with n types of
objects, when repetitions are allowed? We can reason as follows: The number of ways
to pick k objects from a pool with n types of objects is the same as the number of ways
to put k balls into n bins. Imagine these bins aligned in a row. A conguration
of k balls in n bins can be specied as a sequence of n 1 [ symbols and k *
symbols, as in
[[ [ [
This sequence encodes the conguration where k = 6 and n = 5, and there are two
balls in bin number 1, one ball in bin number 3, and three balls in bin number 4.
How many such congurations are there? A conguration is uniquely specied by the
positions of the k * symbols. Thus specifying a conguration amounts to choosing
which of the n + k 1 symbols are going to be *. This simply means we need to
choose a k-element subset from a set of size n + k 1. The number of ways to pick
a collection of k objects from a pool of n types of objects with repetitions is thus
_
n +k 1
k
_
.
47
48
Chapter 10
Binomial Coecients
10.1 Basic properties
Recall that
_
n
k
_
is the number of k-element subsets of an n-element set, and
_
n
k
_
=
n!
k!(n k)!
=

k1
i=0
(n i)
k!
.
The quantities
_
n
k
_
are called binomial coecients because of their role in the Binomial
Theorem, apparently known to the 11th century Persian scholar Omar Khayyam.
Before we state and prove the theorem let us consider some important identities
that involve binomial coecients. One that follows immediately from the algebraic
denition is
_
n
k
_
=
_
n
n k
_
.
This also has a nice combinatorial interpretation: Choosing a k-element subset B
from an n-element set uniquely identies the complement A B of B in A, which is
an (nk)-subset of A. This denes a bijection between k-element and (nk)-element
subsets of A, which implies the identity.
Another relation between binomial coecients is called Pascals rule, although it
was known centuries before Pascals time in the Middle East and India:
_
n
k 1
_
+
_
n
k
_
=
_
n + 1
k
_
.
49
This can be easily proved algebraically:
_
n
k 1
_
+
_
n
k
_
=
n!
(k 1)!(n + 1 k)!
+
n!
k!(n k)!
=
n!k
k!(n + 1 k)!
+
n!(n + 1 k)
k!(n + 1 k)!
=
n!k +n!(n + 1 k)
k!(n + 1 k)!
=
(n + 1)!
k!(n + 1 k)!
=
_
n + 1
k
_
.
Pascals rule also has a combinatorial interpretation:
_
n+1
k
_
is the number of k-element
subsets of an n-element set A. Fix an element a A. A subset of A either contains
a or it doesnt. k-element subsets of A that do not contain a are in fact k-element
subsets of A a and their number is
_
n
k
_
. k-element subsets of A that do contain a
bijectively correspond to (k 1)-element subsets of A a, the number of which is
_
n
k1
_
. The identity follows.
Another illuminating identity is the Vandermonde convolution:
_
m +n
l
_
=
l

k=0
_
m
k
__
n
l k
_
.
We only give a combinatorial argument for this one. We are counting the number of
ways to choose an l-element subset of an (m + n)-element set A. Fix an m-element
subset B A. Any l-element subset S of A has k elements from B and l k elements
from A B, for some 0 k l. For a particular value of k, the number of k-element
subsets of B that can be part of S is
_
m
k
_
and the number of (l k)-element subsets
of A B is
_
n
lk
_
. We can now use the sum principle to sum over the possible values
of k and obtain the identity. An interesting special case is
n

k=0
_
n
k
_
2
=
_
2n
n
_
.
It follows from the Vandermonde convolution by taking l = m = n and remembering
that
_
n
k
_
=
_
n
nk
_
.
10.2 Binomial theorem
Theorem 10.2.1. For n N and x, y R,
(x +y)
n
=
n

k=0
_
n
k
_
x
k
y
nk
.
50
Proof. By induction on n. When n = 0 both sides evaluate to 1. Assume the claim
holds for n = m and consider the case n = m + 1.
(x +y)
m+1
= (x +y) (x +y)
m
(10.1)
= (x +y)
m

k=0
_
m
k
_
x
k
y
mk
(10.2)
= x
m

k=0
_
m
k
_
x
k
y
mk
+y
m

k=0
_
m
k
_
x
k
y
mk
(10.3)
=
m

k=0
_
m
k
_
x
k+1
y
mk
+
m

k=0
_
m
k
_
x
k
y
m+1k
(10.4)
=
m+1

k=1
_
m
k 1
_
x
k
y
m+1k
+
m

k=0
_
m
k
_
x
k
y
m+1k
(10.5)
=
_
x
m+1
+
m

k=1
_
m
k 1
_
x
k
y
m+1k
_
+
_
y
m+1
+
m

k=1
_
m
k
_
x
k
y
m+1k
_
(10.6)
= x
m+1
+y
m+1
+
m

k=1
__
m
k 1
_
+
_
m
k
__
x
k
y
m+1k
(10.7)
= x
m+1
+y
m+1
+
m

k=1
_
m + 1
k
_
x
k
y
m+1k
(10.8)
=
m+1

k=0
_
m + 1
k
_
x
k
y
m+1k
. (10.9)
Here (5) follows from (4) by noting that
m

k=0
f(k) =
m+1

k=1
f(k 1)
and (8) follows from (7) by Pascals rule. The other steps are simple algebraic ma-
nipulation. This completes the proof by induction.
The binomial theorem can be used to immediately derive an identity we have seen
before: By substituting x = y = 1 into the theorem we get
n

k=0
_
n
k
_
= 2
n
.
Here is another interesting calculation: Putting x = 1 and y = 1 yields
n

k=0
(1)
k
_
n
k
_
= 0.
51
This implies

k odd
_
n
k
_
=

k even
_
n
k
_
= 2
n1
.
This means that the number of odd-size subsets of an n-element set A is the same
as the number of even-size subsets, and equals 2
n1
. This can be proved by a com-
binatorial argument as follows: Fix an element a A and note that the number of
subsets of A a is 2
n1
. There is a bijective map between subsets of A a and
odd-size subsets of A, as follows: Map an odd-sized subset of A a to itself, and
map an even-sized subset B A a to B a. Observe that this is a bijection
and conclude that the number of odd-sized subsets of A is 2
n1
. Even-size subsets
can be treated similarly, or by noting that their number is 2
n
minus the number of
odd-size ones.
52
Chapter 11
The Inclusion-Exclusion Principle
11.1 Statement and proof of the principle
We have seen the sum principle that states that for n pairwise disjoint sets A
1
, A
2
, . . . , A
n
,

n
_
i=1
A
i

=
n

i=1
[A
i
[ .
What happens when the sets are not pairwise disjoint? We can still say something.
Namely, the sum

n
i=1
[A
i
[ counts every element of

n
i=1
A
i
at least once, and thus
even with no information about the sets we can still assert that

n
_
i=1
A
i

i=1
[A
i
[ .
However, with more information we can do better. For a concrete example, con-
sider a group of people, 10 of whom speak English, 8 speak French, and 6 speak both
languages. How many people are in the group? We can sum the number of English-
and French-speakers, getting 10 +8 = 18. Clearly, the bilinguals were counted twice,
so we need to subtract their number, getting the nal answer 186 = 12. This argu-
ment can be carried out essentially verbatim in a completely general setting, yielding
the following formula:
[A B[ = [A[ +[B[ [A B[.
What if there are three sets? Suppose in addition to the above English and French
speakers, we have 14 German-language enthusiasts, among which 8 also speak English,
5 speak French, and 2 speak all three languages. How many people are there now?
We can reason as follows: The sum 10 +8 +14 = 32 counts the people speaking two
languages twice, so we should subtract their number, getting 32 6 8 5 = 13.
But now the trilinguals have not been counted: They were counted three times in
the rst sum, and then subtracted three times as part of the bilinguals. So the nal
answer is obtained by adding their number: 13 + 2 = 15. In general,
[A B C[ = [A[ +[B[ +[C[ [A B[ [A C[ [B C[ +[A B C[.
53
In the case of arbitrarily many sets we obtain the inclusion-exclusion principle:

n
_
i=1
A
i

=
n

k=1
(1)
k1

1i
1
<i
2
<<i
k
n
[A
i
1
A
i
2
. . . A
i
k
[ .
Proof. Each element in

n
i=1
A
i
is counted exactly once on the left side of the formula.
Consider such an element a and let the number of sets A
i
that contain a be j. Then
a is counted
_
j
1
_

_
j
2
_
+. . . + (1)
j1
_
j
j
_
times on the right side. But recall from our exploration of binomial coecients that
j

i=0
(1)
i
_
j
i
_
=
j

i=0
(1)
i1
_
j
i
_
= 1 +
j

i=1
(1)
i1
_
j
i
_
= 0,
which implies
_
j
1
_

_
j
2
_
+. . . + (1)
j1
_
j
j
_
= 1,
meaning that a is counted exactly once on the right side as well. This establishes the
inclusion-exclusion principle.
11.2 Derangements
Given a set A = a
1
, a
2
. . . , a
n
, we know that the number of bijections from A to
itself is n!. How many such bijections are there that map no element a A to itself?
That is, how many bijections are there of the form f : A A, such that f(a) ,= a
for all a A. These are called derangements, or bijections with no xed points.
We can reason as follows: Let S
i
be the set of bijections that map the i-th element
of A to itself. We are the looking for the quantity
n!

n
_
i=1
S
i

.
By the inclusion-exclusion principle, this is
n!
n

k=1
(1)
k1

1i
1
<i
2
<<i
k
n
[S
i
1
S
i
2
. . . S
i
k
[ .
Consider an intersection S
i
1
S
i
2
. . . S
i
k
. Its elements are the permutations that
map a
i
1
, a
i
2
, . . . , a
i
k
to themselves. The number of such permutations is (nk)!, hence
[S
i
1
S
i
2
. . . S
i
k
[ = (n k)!. This allows expressing the number of derangements
54
as
n!
n

k=1
(1)
k1

1i
1
<i
2
<<i
k
n
(n k)! = n!
n

k=1
(1)
k1
_
n
k
_
(n k)!
=
n

k=0
(1)
k
_
n
k
_
(n k)!
=
n

k=0
(1)
k
n!
k!
= n!
n

k=0
(1)
k
k!
.
Now,

n
k=0
(1)
k
k!
is the beginning of the Maclaurin series of e
1
. (No, you are not
required to know this for the exam.) This means that as n gets larger, the number
of derangements rapidly approaches n!/e. In particular, if we just pick a random
permutation of a large set, the chance that it will have no xed points is about 1/e.
Quite remarkable, isnt it!?
55
56
Chapter 12
The Pigeonhole Principle
12.1 Statements of the principle
In we put more than n pigeons into n pigeonholes, at least one pigeonhole will house
two or more pigeons. This trivial observation is the basis of ingenious combinatorial
arguments, and is the subject of this chapter. Lets begin with the various guises of
the pigeonhole principle that are encountered in combinatorics.
Basic form. If m objects are put in n boxes and n < m, then at least one box
contains at least two objects. The one-line proof is by contradiction: If every box
contains at most one object, there are at most n 1 = n objects. A more rigorous
formulation of the principle is as follows: Given two sets A and B, with [A[ = m >
n = [B[, for any function f : A B there exists b B such that

x A : f(x) = b

> 1.
General form. If m objects are put in n boxes, then at least one box contains at
least m/n| objects. The proof is again by contradiction: If every box contains at
most m/n| 1 < m/n objects, there are less than n(m/n) = m objects. The more
rigorous formulation is: Given two sets A and B, for any function f : A B there
exists b B such that

x A : f(x) = b

_
m
n
_
.
Dijkstras form. For a nonempty nite collection of integers (not necessarily dis-
tinct), the maximum value is at least the average value. It is a good exercise to verify
that this is equivalent to the general form above.
12.2 Simple applications
Lets begin with some easy applications of the pigeonhole principle.
57
First application. There are two San Franciscans with the exact same number
of hairs on their heads. Indeed, according to P&G Hair Facts, the average persons
head has about 100,000 hairs, while some people have as many as 150,000. So it
seems safe to bet that every San Franciscan has at most 700,000 hairs on his or her
head. On the other hand, the year 2000 US Census counted 776,733 San Francisco
residents. The pigeonhole principle implies that at least two of them have the exact
same number of hairs.
Second application. At a cocktail party with six or more people, there are three
mutual acquaintances or three mutual strangers. Indeed, pick an arbitrary person a.
By the pigeonhole principle, among the other ve or more people, either there are
three of as acquaintances, or three people who are strangers to a. Lets say there
are three that are as acquaintances, the other case is analogous. If those three are
mutual strangers we are done. Otherwise there are two among them, call them b and
c, who know each other. Then a, b and c are mutual acquaintances and we are done.
Third application. Consider an innite two-dimensional plane, every point of
which is colored either red or blue; then there are two points one yard apart that
are the same color. Indeed, take an arbitrary equilateral triangle with a side length
of one yard. By the pigeonhole principle, two of its vertices have the same color.
Fourth application. Consider the numbers 1, 2, . . . , 2n, and take any n + 1 of
them; then there are two numbers in this sample that are coprime. Indeed, consider
the pairs 1, 2, 3, 4, . . . , 2n 1, 2n. By the pigeonhole principle, both numbers
from one of these pairs are in the sample. These numbers dier by 1 and are thus
coprime. (This follows from the same argument as in Euclids proof of the innity of
primes.)
12.3 Advanced applications
The following lemma comes from a classical 1935 paper by Paul Erdos and George
Szekeres titled A combinatorial problem in geometry:
Lemma 12.3.1. In any ordered sequence of n
2
+1 distinct real numbers a
1
, a
2
, . . . , a
n
2
+1
,
there is either a monotone increasing subsequence of length n + 1 or a monotone de-
creasing subsequence of length n + 1. Namely, there is a set of indices 1 i
1
< i
2
<
< i
n+1
n
2
+1, such that either a
i
1
> a
i
2
> > a
i
n+1
or a
i
1
< a
i
2
< < a
i
n+1
.
Proof. For 1 i n
2
+ 1, let
i
be the length of the longest monotone increasing
subsequence that starts at a
i
. If some
i
> n, we are done. Otherwise, by the
pigeonhole principle, there exists 1 j n, and some set i
1
< i
2
< < i
m
of size
m (n
2
+ 1)/n| = n + 1, such that
i
1
=
i
2
= =
im
= j. Now, consider two
numbers a
i
k
and a
i
k+1
. If a
i
k
< a
i
k+1
, we get an increasing subsequence starting at
a
i
k
of length j + 1, which is a contradiction. Hence a
i
k
> a
i
k+1
in particular, and
58
a
i
1
> a
i
2
> > a
im
in general, giving us a decreasing subsequence of length at least
n + 1.
Here is another pigeonhole gem, the last one for today:
Proposition 12.3.2. Given a sequence of n not necessarily distinct integers a
1
, a
2
, . . . , a
n
,
there is a nonempty consecutive subsequence a
i
, a
i+1
, . . . , a
j
whose sum

j
m=i
a
m
is a
multiple of n. (The subsequence might consist of a single element.)
Proof. Consider the collection
_
0

i=1
a
i
,
1

i=1
a
i
,
2

i=1
a
i
, . . . ,
n

i=1
a
i
_
.
This collection has size n+1 and its rst element is the empty sum

0
i=1
a
i
= 0. There
are only n possible remainders modulo n, thus by the pigeonhole principle, there are
two numbers in the above collection of size n +1 that leave the same remainder. Let
these be

l
i=1
a
i
and

k
i=1
a
i
, with l < k. By a lemma we once proved, it follows that
n

_
k

i=1
a
i

i=1
a
i
_
,
which implies
n

i=l+1
a
i
.
59
60
Chapter 13
Asymptotic Notation
13.1 Denitions
Analysis of algorithms is concerned with estimating how many steps various algo-
rithms make while solving problems of various sizes. In particular, given an algorithm,
we want to make statements like For input of size n, the algorithm will terminate in
at most f(n) steps. If we try to accurately estimate the number of steps, a cumber-
some bound like
f(n) =
1
11
n
3
+ 12n
2
+ 15
1
2
n + log
3
n + 17
might arise. Such precision only complicates matters and does not add to our under-
standing of the algorithms eciency. The following notational convention allows to
simplify bounds by concentrating on their main terms.
Denition 13.1.1. For two functions f, g : N
+
R,
f(n) = O(g(n)) if and only if there exists a positive constant c R and a
constant n
0
N, such that [f(n)[ c[g(n)[ for all n n
0
.
f(n) = (g(n)) if and only if g(n) = O(f(n)).
f(n) = (g(n)) if and only if f(n) = O(g(n)) and f(n) = (g(n)).
Asymptotic notation does wonders to the above ugly bound: We can now say that
f(n) = (n
3
), which makes it easier to see how the number of steps performed by
the algorithm grows as n gets larger and larger. Notice how the asymptotic notation
swallowed all the constants and lower-order terms! To prove that f(n) = (n
3
) we
need to show that there exist positive constants c
1
, c
2
R and a constant n
0
N,
such that c
1
n
3
f(n) c
2
n
3
for all n n
0
. (We dropped the absolute values that
come from Denition 13.1.1 since f(n) and n
3
are nonnegative for n N
+
.) We can
take n
0
= 1, c
1
=
1
11
, and c
2
= 45.6. For the lower bound, clearly f(n)
1
11
n
3
when
n N
+
. For the upper bound, note that in this range n
3
n
2
n log
3
n, and
n
3
1. All these inequalities can be proved by elementary algebraic manipulation.
Thus we get
f(n)
1
11
n
3
+ 12n
3
+ 15
1
2
n
3
+n
3
+ 17n
3
45.6n
3
.
61
We can also perfectly well say that f(n) = O(n
4
) or that f(n) = O(n
25
); these
bounds are considerably less informative but correct. On the other hand, the bound
f(n) = O(n
2
) (or even f(n) = O(n
2.99
)) is not correct. Indeed, we have seen that
f(n)
1
11
n
3
. On the other hand, for any positive constant c R,
1
11
n
3
cn
2
for all
n 11c. Thus there is no positive constant c R and a constant n
0
N so that
f(n) cn
2
for all n n
0
.
Asymptotic notation is asymmetric, so we never write a statement like O(g(n)) =
f(n); the O, , and are always present on the right side of the equality sign.
(However, we can write n
2
+ O(n) = (n
2
), for example.) The right way to think
of statements like f(n) = O(g(n)) and f(n) = (g(n)) is as inequalities; always
remember what the notation means according to Denition 13.1.1.
13.2 Examples and properties
The following asymptotic inequalities can all be easily proved and are very useful. Do
the proofs as an exercise. You might nd induction or tools from elementary calculus
helpful for some of these. Youll also need simple properties of logarithms, like the
identity
log
a
n =
log
b
n
log
b
a
.
For two constants u, v R, if u < v then n
u
= O(n
v
). (A bigger power
swallows a smaller one.)
If f(n) is a degree-d polynomial in n then f(n) = O(n
d
). If the coecient of n
d
in f(n) is nonzero then f(n) = (n
d
).
For any real constants b > 1 and p, n
p
= O(b
n
). (An exponential swallows a
power.)
For any real constants q > 0 and p, (ln n)
p
= O(n
q
). (A power swallows a
logarithm.)
For any real constants a, b > 1, log
a
n = (log
b
n). This implies that we can
write bounds like O(log n), O(nlog n), etc., without specifying the base of the
logarithm. (Asymptotic notation swallows bases of logarithms.)
We conclude this lecture by demonstrating how new asymptotic inequalities can
be derived from existing ones. These are often used in the analysis of algorithms,
although they are so much a part of the folklore that they are rarely referred to
explicitly.
Proposition 13.2.1. The following hold:
(a) If f(n) = O(g(n)) and p N is a constant then p f(n) = O(g(n)).
(b) If f(n) = O(h(n)) and g(n) = O(w(n)) then f(n)+g(n) = O(max([h(n)[, [w(n)[)).
62
(c) If f(n) = O(h(n)) and g(n) = O(w(n)) then f(n) g(n) = O(h(n) w(n)).
Proof. We prove each claim individually.
(a) If f(n) = O(g(n)) then there exists a positive constant c R and a constant
n
0
N, such that [f(n)[ c[g(n)[ for all n n
0
. Thus for p N, [p f(n)[ =
p[f(n)[ (pc)[g(n)[ for all n n
0
, and by Denition 13.1.1, p f(n) = O(g(n)).
(b) If f(n) = O(h(n)) and g(n) = O(w(n)) then there exist two positive constants
c
1
, c
2
R and constants n
1
, n
2
N, such that [f(n)[ c
1
[h(n)[ for all n n
1
and [g(n)[ c
2
[w(n)[ for all n n
2
. Then
[f(n)+g(n)[ [f(n)[+[g(n)[ c
1
[h(n)[+c
2
[w(n)[ = (c
1
+c
2
) max([h(n)[, [w(n)[)
for all n max(n
1
, n
2
), and by Denition 13.1.1, f(n)+g(n) = O(max([h(n)[, [w(n)[)).
(c) If f(n) = O(h(n)) and g(n) = O(w(n)) then there exist two positive constants
c
1
, c
2
R and constants n
1
, n
2
N, such that [f(n)[ c
1
[h(n)[ for all n n
1
and [g(n)[ c
2
[w(n)[ for all n n
2
. Then
[f(n) g(n)[ = [f(n)[ [g(n)[ (c
1
[h(n)[) (c
2
[w(n)[) = (c
1
c
2
)[h(n) w(n)[
for all n max(n
1
, n
2
), and by Denition 13.1.1, f(n) g(n) = O(h(n) w(n)).
63
64
Chapter 14
Graphs
14.1 Introduction
A graph G is an ordered pair (V, E), where V is a set and E is a set of two-element
subsets of V . That is,
E
_
x, y : x, y V, x ,= y
_
.
Elements of V are the vertices (sometimes called nodes) of the graph and elements of
E are the edges. If e = x, y E we say that x and y are adjacent in the graph G,
that y is a neighbor of x in G and vice versa, and that the edge e is incident to x and
y.
What are graphs good for? Graphs are perhaps the most pervasive abstraction in
computer science. It is hard to appreciate their tremendous usefulness at rst, because
the concept itself is so elementary. This appreciation comes through uncovering the
deep and fascinating theory of graphs and its applications.
Graphs are used to model and study transportation networks, such as the net-
work of highways, the London Underground, the worldwide airline network, or the
European railway network; the connectivity properties of such networks are of great
interest. Graphs can also be used to model the World Wide Web, with edges corre-
sponding to hyperlinks; Google uses sophisticated ideas from graph theory to assign a
PageRank to every vertex of this graph as a function of the graphs global properties.
In this course we will introduce the basic concepts and results in graph theory, which
will allow you to study and understand more advanced techniques and applications
in the future.
14.2 Common graphs
A number of families of graphs are so common that they have special names that are
worth remembering:
Cliques. A graph on n vertices where every pair of vertices is connected is called
a clique (or n-clique) and is denoted by K
n
. Formally, K
n
= (V, E), where V =
1, 2, . . . , n and E = i, j : 1 i < j n. The number of edges in K
n
is
_
n
2
_
.
65
Paths. A path on n vertices, denoted by P
n
, is the graph P
n
= (V, E), where
V = 1, 2, . . . , n and E = i, i +1 : 1 i n 1. The number of edges in P
n
is
n 1. The vertices 1 and n are called the endpoints of P
n
.
Cycles. A cycle on n 3 vertices is the graph C
n
= (V, E), where V = 1, 2, . . . , n
and E = i, i + 1 : 1 i n 1 1, n. The number of edges in C
n
is n.
14.3 Some important concepts
Graph isomorphism. If the above denition of a cycle is followed to the letter, a
graph is a cycle only if its vertices are natural numbers. So, for example, the graph
G = (V, E) with V = A, B, C and E = A, B, B, C, C, A would not be a
cycle. This seems wrong, because G looks like a cycle, and for all practical purposes
it is exactly like C
3
. The concept of graph isomorphism provides a way to formally
say that C
3
and G are the same.
Denition 14.3.1. Two graphs G = (V, E) and G

= (V

, E

) are said to be isomor-

phic if there exists a bijection f : V V

such that
x, y E if and only if f(x), f(y) E

.
In this case we write G G

and the function f is called an isomorphism of G and

G

.
We generally regard isomorphic graphs to be essentially the same, and sometimes
do not even draw the distinction. Hence graphs that are isomorphic to cliques, cycles
and paths are themselves said to be cliques, cycles and paths, respectively.
Size. The number of edges of a graph is called it size. The size of an n-vertex graph
is at most
_
n
2
_
, achieved by the n-clique.
Degree. The degree (or valency) of a vertex v in a graph G = (V, E), denoted by
d
G
(v), is the number of neighbors of v in G. More formally, this degree is
d
G
(v) =

u V : v, u E

.
A graph in which every vertex has degree k is called k-regular and a graph is said to
be regular if it is k-regular for some k.
The following is sometimes called the Handshake lemma. It can be interpreted as
saying that the number of people at a cocktail party who shake hands with an odd
number of others is even.
Proposition 14.3.2. The number of odd-degree vertices in a graph is even.
66
Proof. For a graph G = (V, E), consider the sum of the degrees of its vertices:
s =

vV
d
G
(v).
Observe that this sum counts every edge e twice, once for each of the vertices incident
to e. Thus s = 2[E[, and, in particular, s is even. Subtracting from s the degrees of
even-degree vertices of G, we see that the resulting quantity is the sum of the degrees
of odd-degree vertices and is still even. This implies the proposition.
Subgraphs and Connectivity.
Denition 14.3.3. Given a graph G = (V, E),
A graph G

= (V

, E

) is said to be a subgraph of G if and only if V

V and
E

E.
A graph G

= (V

, E

) is said to be an induced subgraph of G if and only if

V

V and E

= u, v E : u, v V

.
Given a graph G, a path, cycle, or clique in G is a subgraph of G that is a path,
cycle, or clique, respectively. Two vertices v and u of G are said to be connected if
and only if there is a path in G with endpoints u and v. A graph G as a whole is said
to be connected if and only if every pair of vertices in G is connected.
A subgraph G

of G is called a connected component of G if it is connected and no

other graph G

, such that G

G, is connected. Clearly, a graph is connected

if and only if it has a single connected component.
Finally, there is a related notion to a path that is also useful: Given a graph
G = (V, E), a walk W in G is a sequence W = (v
1
, e
1
, v
2
, e
2
, . . . , v
n1
, e
n1
, v
n
) of
vertices and edges in G that are not necessarily distinct, such that v
1
, v
2
, . . . , v
n

V , e
1
, e
2
, . . . , e
n1
E, and e
i
= v
i
, v
i+1
for all 1 i n1. A walk diers from
a path in that vertices and edges can be repeated. The set of edges e
1
, e
2
, . . . , e
n1

covered by W is denoted by E(W). Similarly, the set of vertices covered by W is

V (W) = v
1
, v
2
, . . . , v
n
.
14.4 Kinds of graphs
What we have been calling graph is actually only one of many kinds of graphs, namely
an undirected, unweighted, simple graph. Lets see how each of these qualities can
dier and what other kinds of graphs there are.
A directed (simple, unweighted) graph G is an ordered pair (V, E), where V is a
set and E is a set of ordered pairs from V . That is,
E
_
(x, y) : x, y V, x ,= y
_
.
Directed graphs are suitable for modeling one-way streets, non-reexive relations,
hyperlinks in the World Wide Web, and so on. The notion of degree as dened above
67
is no longer applicable to a directed graph. Instead, we speak of the indegree and the
outdegree of a vertex v in G, dened as [u V : (u, v) E[ and [u V : (v, u)
E[, respectively.
A graph that is not simple can have multi-edges and self-loops. Multi-edges are
multiple edges between the same pair of vertices. (Their presence means that the
collection of edges is no longer a set, but a so-called multiset.) A self-loop is an edge
to and from a single vertex v.
Finally, a graph can also be weighted, in the sense that numerical weights are
associated with edges. Such weights are extremely useful for modeling distances in
transportation networks, congestion in computer networks, etc. We will not dwell on
weighted graphs in this course. In fact, unless specied otherwise, the word graph
will continue to refer to undirected, unweighted, simple graphs.
68
Chapter 15
More GraphsEulerian, Bipartite,
and Colored
15.1 Eulerian graphs
Ever seen those puzzles that ask you to trace some shape without lifting the pencil o
the paper? For graph theory initiates such questions present no diculty, separating
this select elite from the rest of the human race who are doomed to spend their Sunday
afternoons hunched over, putting page after page out of commission, searching in vain
for the ever-elusive drawing.
Given a graph G = (V, E), dene a tour of Gas a walk T = (v
1
, e
1
, v
2
, e
2
, . . . , v
n
, e
n
, v
n+1
)
in G, such that T does not trace any edge more than once. (That is, e
i
,= e
j
for all
1 i < j n.) The tour is said to be Eulerian if, in addition, v
n+1
= v
1
, V (T) = V ,
and E(T) = E. Thus an Eulerian tour traverses all the edges of G, walking along
each exactly once, eventually coming back to where it started. (Particular vertices
may and generally will be visited more than once.) A graph is said to be Eulerian if
and only if it has an Eulerian tour.
Eulerian graphs were discussed by the great Leonhard Euler, the most prolic
mathematician of all time. Eulers analysis of these graphs, presented in 1736, marks
the birth of graph theory.
Theorem 15.1.1. A graph is Eulerian if and only if it is connected and each of its
vertices has even degree.
Proof. We rst prove that if G is Eulerian its vertices all have even degree. Indeed,
trace an Eulerian tour of G starting and ending at a vertex v. Every time the tour
enters an intermediate vertex it also leaves it along a dierent edge. In the very rst
step the tour leaves v and in the last step it enters v. Thus we can label the edges
incident to any vertex as entering and leaving, such that there is a bijection
between these two sets. This shows that the degree of every vertex is even.
To prove that a graph G = (V, E) with all vertex degrees being even is Eulerian,
consider the longest tour T = (v
1
, e
1
, v
2
, e
2
, . . . , v
n
, e
n
, v
n+1
) in G. (The length of a
tour is measured by its number of edges.) We prove below that T is Eulerian. Namely,
we prove that:
69
(a) v
1
= v
n+1
(b) n = [E[
Proof of (a). Assume for the sake of contradiction that v
1
,= v
n+1
. Then the number
of edges of T incident to v
1
is odd. (After T rst leaves v
1
, it enters and leaves
it an even number of times.) Since the degree of v
1
in G is even, there is an
edge e of G that is incident to v
1
but not part of T. We can extend T by this
edge, obtaining a contradiction.
Proof of (b). We can assume that v
1
= v
n+1
. Suppose V (T) ,= V . Consider a
vertex v V V (T) and a vertex u V (T). Since G is connected, there
is a path P between v and u in G. Consider the rst time a vertex of T is
encountered along P; this vertex is v
i
for some 1 i n. Let e

= v

, v
i
be
the edge along which P arrives at v
i
and note that v

, V (T). This implies that

we can augment T by v

and e

, and obtain a longer tour T

, namely
T

= (v

, e

, v
i
, e
i
, . . . , v
n
, e
n
, v
1
, e
1
, . . . , v
i1
, e
i1
, v
i
).
We have reached a contradiction and can therefore assume that V (T) = V .
That is, T visits all the vertices of G. Assume for the sake of contradiction that
E(T) ,= E, so there exists an edge e

= v
i
, v
j
of G, for some 1 i < j n,
that is not part of T. Then we can augment T by the edge e

, and obtain a
longer tour T

, namely
T

= (v
i
, e

, v
j
, e
j
, v
j+1
, e
j+1
, . . . , v
n
, e
n
, v
1
, e
1
, . . . , v
i
, e
i
, . . . , v
j1
, e
j1
, v
j
).
T

is longer than T by one edge, which is a contradiction that proves the theo-
rem.
Proof technique: Considering an extremal conguration. In the above proof
the crucial idea was to consider the longest tour in the graph. This is an instance of a
common proof technique: If we need to prove that some conguration with particular
properties exists (like an Eulerian tour), consider the extremal (longest, shortest, etc.)
conguration of a related type (usually one that has some but not all of the required
properties), and prove that this extremal conguration has to satisfy all of the required
properties. Some steps in the proof usually proceed by contradiction: If the extremal
conguration wasnt of the required type we could nd a more extremal one, which
is a contradiction.
15.2 Graph coloring
Consider a wireless company that needs to allocate a transmitter wavelength to each
of its users. Two users who are suciently close need to be assigned dierent wave-
lengths to prevent interference. How many dierent wavelengths do we need? Of
70
course, we can just assign a new wavelength to every user, but that would be waste-
ful if some users are far apart. So whats the least number of wavelengths we can get
away with?
We can model the users as vertices in a graph and connect two vertices by an edge
if the corresponding users are suciently close. A coloring of this graph G = (V, E)
is an assignment of colors to vertices, such that no two adjacent vertices get the same
color. The above question can now be restated as asking for the minimum number of
colors that are needed for a coloring of G.
Let us be a bit more precise in dening colorings: A k-coloring of G is said to
be a function c : V 1, 2, . . . , k, such that if v, u E then c(v) ,= c(u). The
smallest k N for which a k-coloring of G exists is called the chromatic number of
G. If a k-coloring of G exists, the graph is said to be k-colorable. There are many
deep results concerning colorings and the chromatic number. At this point we only
give the simplest one:
Proposition 15.2.1. If the degree of every vertex in a graph G is at most k, then
the chromatic number of G is at most k + 1.
Proof. By induction on the number of vertices in G. (The degree bound k is xed
throughout the proof.) If G has a single vertex, then the maximal degree is 0 and
the graph is 1-colorable. Since 1 k +1, the proposition holds. Suppose every graph
with at most n vertices and all vertex degrees at most k is (k +1)-colorable. Consider
a particular graph G = (V, E) with n + 1 vertices, and all degrees at most k. Let
G

be the graph obtained from G by deleting a particular vertex v and all the edges
incident to v. That is, G

is the incident subgraph of G on the vertices V v. G

has n vertices, all of degree at most k, and is thus (k +1)-colorable. Let c

be such a
coloring of G

. We extend it to a coloring c of G as follows. For every vertex u G

such that u ,= v we dene c(u) = c

(u). The vertex v has at most k neighbors in G

and there is at least one color i among 1, 2, . . . , k + 1 that has not been assigned
to any of them. We dene c(u) = i. This is a (k + 1)-coloring, and the proposition
follows.
15.3 Bipartite graphs and matchings
A bipartite graph is a graph that can be partitioned into two parts, such that edges
of the graph only go between the parts, but not inside them. Formally, a graph
G = (V, E) is said to be bipartite if and only if there exist U V , such that
E u, u

: u U and u

V U.
The sets U and V U are called the classes of G. A complete bipartite graph K
m,n
is
a graph in which all the edges between the two classes are present. Namely, K
m,n
=
(V, E), where V = 1, 2, . . . , m+n and E = i, j : 1 i m, m+1 j m+n.
The number of edges in K
n
is mn. From the denition of coloring, it follows that
a graph is bipartite if and only if it is 2-colorable. (Check!) Here is another useful
characterization of bipartite graphs:
71
Proposition 15.3.1. A graph is bipartite if and only if it contains no cycle of odd
length.
Proof. For one direction of the claim, let G be a bipartite graph and let C =
(v
1
, v
2
, . . . , v
n
, v
1
) be a cycle in G. Suppose without loss of generality that v
1
U,
where U is as in the denition of bipartiteness. Then by simple induction that we
omit, v
i
U for every odd 1 i n. Since v
n
, v
1
E, v
n
V U and thus n is
even. It follows that the number of edges in C is even.
Before proving the other direction, we need a simple lemma.
Lemma 15.3.2. Given a graph G = (V, E), let P = (v
1
, v
2
, . . . , v
n
) be a shortest path
between two vertices v
1
and v
n
in G. Then for all 1 i < j n, P
i
= (v
i
, v
i+1
, . . . , v
j
)
is a shortest path between v
i
and v
j
.
Proof. Proof by contradiction. Let Q
i
= (v
i
, u
1
, u
2
, . . . , u
l
, v
j
) be a shortest path
between v
i
and v
j
. Assume for the sake of contradiction that Q
i
is shorter than P
i
.
Consider the walk
Q = (v
1
, v
2
, . . . , v
i
, u
1
, u
2
, . . . , u
l
, v
j
, v
j+1
, . . . , v
n
).
Since Q
i
is shorter than P
i
, Q is shorter than P. Now consider the graph G

=
(V (Q), E(Q)). This graph is connected, and thus there is a shortest path P

between
v
1
and v
n
in G

. The number of edges in this shortest path cannot exceed the total
number of edges in G

, and thus P

is shorter than P. Since P

is also a path between

v
1
and v
n
in G, we have reached a contradiction.
We now turn to the other direction of the proposition. Assume that G = (V, E)
has no odd cycle. If G has more than one connected component we look at every
component separately. Clearly, if every component is bipartite, G as a whole is
bipartite. Thus assume that G is connected. Pick an arbitrary vertex v V and
dene a set U V as
U = x V : the shortest paths from v to x have even length.
Clearly, V U is the set
V U = x V : the shortest paths from v to x have odd length.
We prove that no two vertices in U are adjacent; the proof for V U is similar.
Consider for the sake of contradiction an edge e = u, u

E, such that u, u

U.
Denote a shortest path from v to u by P
1
and a shortest path from v to u

by P
2
.
Given two vertices s and t on a path P, let P
s,t
be the part of P that connects s and
t. Consider a vertex w that lies on both P
1
and P
2
. The above lemma implies that
P
v,w
1
and P
v,w
2
are shortest paths between v and w and thus have the same length,
which we denote by l(w). Consider the vertex w

shared by P
1
and P
2
that maximizes
l(w) among all such w. The paths P
w

,u
1
and P
w

,u

2
share no vertex in common other
than w

. Furthermore, the length of P

w

,u
1
is the length of P
1
minus l(w

) and the
length of P
w

,u

2
is the length of P
2
minus l(w

). Since the lengths of P

1
and P
2
are
72
both even, the lengths of P
w

,u
1
and P
w

,u

2
have the same parity (that is, they are
either both even or both odd). Now consider the cycle C composed of P
w

,u
1
, the edge
u, u

, and P
w

,u

2
. Since P
w

,u
1
and P
w

,u

2
share no vertex in common other than
w

, C really is a cycle in G. Moreover, since the lengths of P

w

,u
1
and P
w

,u

2
have the
same parity, the number of edges in C is odd! We have reached a contradiction that
completes the proof.
Bipartite graphs are particularly useful to model symmetric relations from one
set to another. For example, given a collection of boys and girls, we could model the
relation wants to go to the prom with by a bipartite graph. Given such preferences,
an interesting question is whether we can pair the boys up with the girls, so that they
all end up going to the prom with someone they actually want to go with. It turns
out that this question has a very precise answer. To state the theorem we need to
dene the notion of matching:
Denition 15.3.3. Given a bipartite graph G = (V, E), a matching B in G is a set
of disjoint edges. Namely, B E and e
1
e
2
= for any e
1
, e
2
B. A matching is
said to be perfect if

eB
e = V .
Consider now a set B of boys, a set G of girls, and a symmetric relation P from B
to G. Dene a graph W = (B G, b, g : (b, g) P). The above question simply
asks to characterize when there exists a perfect matching in W. The below result,
known as Halls theorem, provides such a characterization. To state the theorem, we
use another piece of notation: Given a subset S of the vertices of W, we let (S) be
the set of vertices of W adjacent to at least one of the vertices of S.
Theorem 15.3.4. A bipartite graph W = (V, E) with classes B and G has a perfect
matching if and only if [B[ = [G[ and [(S)[ [S[ for all S B.
Proof. One direction is easy: Assume W has a perfect matching and consider a
set S B. Every element of S is matched to a distinct element of G and hence
[(S)[ [S[. In particular, [G[ [B[. By a symmetric argument we get that
[B[ [G[ and thus [B[ = [G[.
For the other direction, assume that [B[ = [G[ and that [(S)[ [S[ for all
S B. We prove that there exists a perfect matching in W by strong induction on
[B[. For the base case, if [B[ = [G[ = 1, the matching consists of the single edge of
W. Assuming that the claim holds for all graphs with [B[ k, consider a graph W
as above with [B[ = k + 1. We distinguish between two possibilities:
(a) If for every S B, [(S)[ > [S[, we take an arbitrary x B and match it with
an adjacent y G. Then for every subset S

of B x, it still holds that the

number of vertices of G y adjacent to at least one of the vertices of S

is at
least [S

[. We can thus match the vertices of Bx with the vertices of Gy

by the induction hypothesis.
(b) If for some S B, [(S)[ = [S[, we note that for every S

S, the number
of vertices in (S) adjacent to at least one of the vertices of S

is at least [S

[.
73
Thus we can match S with (S) by the induction hypothesis. Now we need to
show that we can match B S with G (S). Consider a set S

B S and
the set T

of its neighbors in G (S). Note that the set of neighbors of S S

in G is (S) T

. Thus [S S

[ [(S) T

[. Since [S[ = [(S)[, we get that

[S

[ [T

[. Thus by the induction hypothesis we can also match B S with

G (S).
This shows that in both cases all the vertices of B can be matched with vertices of
G as required, and concludes the proof.
74
Chapter 16
Trees
16.1 Basic properties of trees
Trees in mathematics are graphs of a certain kind. In a sense, trees are the simplest
interesting graphs, in that they have a very simple structure, but possess a rich variety
of nontrivial properties. Trees have innumerable applications throughout computer
science.
Denition 16.1.1. A tree is a connected graph with no cycles. A vertex of degree
one in a tree is called a leaf.
An extensive theory of trees has been developed, and we give the tip of the iceberg
below: Four additional characterizations that each could have been used to dene
trees.
Theorem 16.1.2. Given a graph G = (V, E), the following conditions are equivalent:
(a) G is a connected graph with no cycles. (Thus G is a tree by the above denition.)
(b) For every two vertices u, v V , there exists exactly one path from u to v.
(c) G is connected, and removing any edge from G disconnects it. (Thus G is a
minimal connected graph.)
(d) G has no cycles, and adding any edge to G gives rise to a cycle. (Thus G is a
maximal acyclic graph.)
(e) G is connected and [E[ = [V [ 1.
Proof. We will prove for each of the conditions (b)(e) in turn that it is equivalent to
condition (a). This implies the equivalence of all the conditions. The proof proceeds
by induction on the number of vertices [V [ in G, and we relate a tree with n + 1
vertices to a tree with n vertices in the inductive step by tearing o a leaf. We
begin by proving two lemmas that will be useful in this process.
Lemma 16.1.3. Each tree with at least 2 vertices contains at least 2 leaves.
75
Proof. Given a tree T = (V, E), consider a path P of maximum length in T. We
claim that the two end-points of P are leaves of T. Indeed, assume for the sake of
contradiction that an end-vertex u of P has degree greater than 1 in T. Thus there
exists an edge u, u

E that is not part of P. If u

belongs to P then T contains

a cycle. Otherwise we can extend P by the edge u, u

and P is not a longest path

in T. This contradiction proves the lemma.
Lemma 16.1.4. Given a graph G = (V, E) and a leaf v V that is incident to an
edge e = v, v

E, the graph G is a tree if and only if G

= (V v, E e) is a
tree.
Proof. Assume that G is a tree and consider two vertices u, w V v. u and w
are connected by a path P in G. Every vertex of P other than u and w has degree
at least 2, and thus v cannot be a vertex of P. Therefore P is a path in G

, which
proves that G

is connected. Since G does not contain a cycle, G

cannot contain a
cycle and is thus a tree.
For the other direction, assume that G

is a tree. Since a cycle only contains

vertices with degree at least 2, a cycle in G must also be a cycle in G

. Therefore
there are no cycles in G. Also, any two vertices of G other than v can be connected
by the same path as in G

, and v can be connected to any vertex u in G by a path

that consists of the edge e and a path in G

between v

and u. Thus G is a tree.

We are now ready to employ induction to prove that condition (a) implies each of
(b)(e). For the induction basis, all ve conditions hold for the graph with a single
vertex. Consider a graph G = (V, E) with [V [ = n 2 and assume that (a) holds for
G. By Lemma 16.1.3, G has a leaf v V that is incident to an edge e = v, v

E.
By Lemma 16.1.4, condition (a) holds for G

. The inductive hypothesis states that

condition (a) implies conditions (b)(e) for the graph G

= (V v, E e). We
now need to prove that conditions (b)(e) also hold for G.
Condition (b) holds for G by a similar argument to the one employed in the proof
of Lemma 16.1.4. Condition (c) holds for G since removing any edge other than e
disconnects G by the induction hypothesis, and removing e disconnects the vertex v
from the rest of the graph. Condition (d) holds since G cannot have cycles by an
argument similar to the proof of Lemma 16.1.4; adding an edge that is not incident
to v creates a cycle by the inductive hypothesis, and adding an edge v, u, for some
u V v creates a cycle that consists of the edge v, u, the path from u to v

,
and the edge e. Finally, condition (e) holds since G is obtained from G

by adding
one vertex and one edge.
We now prove that each of (b)(d) imply (a). Conditions (b) and (c) on G each
imply connectedness of G. By contrapositive, assume that G contains a cycle. Then
taking two distinct vertices u, w on the cycle, there are two paths from u to w along
the cycle, which implies (b) (a). Furthermore, removing one edge of the cycle does
not disconnect G, which implies (c) (a). Condition (d) implies that G does not
contain a cycle. By contrapositive, assume that G is disconnected. Then there are
two vertices u and w that have no path connecting them and we can add the edge
u, w to G without creating a cycle. This implies (d) (a).
76
To prove (e) (a) we use induction on the number of vertices of G. The induction
basis is the graph with one vertex and the claim trivially holds. For the induction
hypothesis, assume that the claim holds for all graphs with [V [ 1 vertices. For
the inductive step, assume that condition (e) holds for G and hence [E[ = [V [ 1.
Therefore the sum of the degrees of the vertices of G is 2[V [ 2, and thus there is
some vertex v V of degree 1. The graph G

= (V v, E e) is connected and
satises [E e[ = [V v[ 1. By the induction hypothesis, G

is a tree. Lemma
16.1.4 now implies that G is a tree, which completes the proof.
16.2 Spanning trees
One of the reasons that trees are so pervasive is that every connected graph G contains
a subgraph that is a tree on all of the vertices of G. Such a subgraph is called a
spanning tree of G.
Denition 16.2.1. Consider a graph G = (V, E). A tree of the form (V, E

), where
E

E is called a spanning tree of G.

Proposition 16.2.2. Every connected graph G = (V, E) contains a spanning tree.
Proof. Consider a tree subgraph T = (V

, E

) of G with the largest number of vertices.

Suppose for the sake of contradiction that V

,= V , and thus there exists v V V

.
Take an arbitrary vertex u V

and consider a path P between v and u. Let u

be
the rst vertex along P that belongs to V

, and let v

be the vertex that immediately

precedes u

in P. Consider the graph T

= (V

, E

, u

). Lemma 16.1.4
implies that T

is a tree in G with a greater number of vertices than T, which is a

contradiction.
77
78
Chapter 17
Planar Graphs
17.1 Drawing graphs in the plane
As we have seen in class, graphs are often visualized by drawing them in the plane
vertices are drawn as points, and edges as curved segments (called arcs) that connect
the corresponding points. A graph together with a drawing of it in the plane is called
a topological graph.
A graph is called planar if there exists a drawing of it in which the interior of any
arc does not touch or intersect any other arc. That is, two distinct arcs are either
disjoint or touch at endpoints that they share. A planar graph together with a planar
drawing of it is called a plane graph.
It is easy to verify that paths, cycles and trees of any size are planar. Transporta-
tion networks often provide examples of planar graphs, and graph planarity became
important in computer science due to a connection with VLSI circuit design. Planar
drawings are often considered superior when visualizing graphs, as they have no edge
crossings that can be mistaken for vertices. In fact, a whole subeld of computer
science called graph drawing is devoted to the study of various kinds of drawings of
graphs.
It might not be obvious at rst that there are any nonplanar graphs at all. There
are, but well have to do some work to prove this, and well need two preliminary
steps just to approach this issue. The rst is to dene the faces of a plane graph and
the second is to mention the (in)famous Jordan curve theorem.
Let us begin with faces. Dene an equivalence relation on the plane as follows:
Two points a, b R
2
are equivalent if they can be connected by an arc that does not
intersect the edges of a given plane graph G. Then the set of all points that belong
to a particular equivalence class of this relation are said to be a face of G. Intuitively,
if we draw G on a white sheet of paper with a black pencil, the faces are the white
regions; alternatively, if we cut the paper along the edges of the drawing, the faces
are the resulting pieces. Note that faces are dened for plane graphs, but not for
planar graphs without a drawing: Dierent drawings of the same graph can produce
dierent sets of faces!
The second piece of mathematical equipment well need to study planar graphs
79
is the Jordan curve theorem.
1
It is a classical example of a mathematical statement
that is intuitively obvious, but exceedingly dicult to prove. (Related specimens
that arguably fall into this category are Keplers conjecture and the Kneser-Poulsen
conjecture.)
Theorem 17.1.1 (Jordan curve theorem). Every closed non-self-intersecting curve
in the plane separates the plane into exactly two regions, one bounded and one
unbounded, such that is the boundary of both. Alternatively, a plane drawing of any
cycle C
i
, for i 3, has exactly two faces.
To see why the Jordan curve theorem is not so easy to prove recall that there are
some crazy curves out therejust think about fractals like the Koch snowake. How
would you go about proving that such monsters have interior and exterior?
The following corollary follows from the Jordan curve theorem by routine argu-
ments.
Corollary 17.1.2. Consider a plane graph G and an edge e that is part of a cycle in
G. Then e lies on the boundary of exactly two faces of G.
17.2 Eulers formula
The fundamental tool in the study of planar graphs is Eulers formula, presented by
Euler in 1752.
2
Theorem 17.2.1 (Eulers formula). Let G be a connected plane graph with n vertices,
e edges, and f faces. Then
n e +f = 2.
Note that the theorem need not hold if the graph is not connectedJust think of
a collection of isolated vertices. On the other hand, the formula remains true even
for (non-simple) graphs with multiple edges and self-loops.
Proof. The proof proceeds by induction on the number of edges. If there are none,
the graph consists of a single vertex, the drawing has one face, and the formula holds
as 1 0 +1 = 2. Assume that the formula holds for all plane graphs having k edges.
Consider a plane graph G = (V, E) with n vertices, f faces, and k + 1 edges. We
distinguish between two cases:
G is a tree. In this case n = k + 2, due to a tree characterization we have seen
previously, and f = 1 since any planar drawing of a tree has exactly one face.
Then the formula holds as (k + 2) (k + 1) + 1 = 2.
1
Jordan gets all the press even though his proof of the theorem was wrong, and it took almost
20 years until Veblen found a correct one in 1905.
2
Caution: Due to Eulers prodigious output, there are multiple Eulers formulae, Eulers
theorems, etc.
80
G has a cycle C. Take an edge e that lies on C and consider a plane graph G

=
(V, E e), whose vertices and edges are drawn as in G. By Corollary 17.1.2,
the edge e is adjacent to two faces of G, and these faces merge into one in G

.
Thus G

has n vertices, f 1 faces, and k edges. By the induction hypothesis,

n k + (f 1) = 2, hence n (k + 1) +f = 2.
This completes the proof by induction.
Eulers formula implies that the number of faces of a plane graph does not depend
on the drawing, so even though the faces themselves are only dened for a particular
drawing, their number is xed a priori for any planar graph! The formula has a
number of other consequences that are frequently used in theoretical computer science.
These consequences say that planar graphs have few edges, and always have at least
one low-degree vertex. As they make abundantly clear, not only are not all graphs
planar, but most graphs arent. (Do you understand the sense in which the theorem
below implies this?)
Theorem 17.2.2. For any simple planar graph G with n vertices and e edges:
(a) If n 3 then e 3n 6. If e = 3n 6 then every face of G is a 3-cycle (a
triangle) and G is called a triangulation.
(b) There is a vertex of G that has degree at most 5.
Proof. The proofs of the two parts are similar in their clever use of Eulers formula:
(a) If G is not connected, we can add edges to connect G while maintaining its
planarity. Assume therefore that G is connected. Let f be the number of faces
of G. For such a face t, let (t) be the number of edges adjacent to t and
consider the sum

t
(t) that ranges over all faces t of G. As each edge is
adjacent to at most two faces, a particular edge is counted at most twice in the
above sum. Hence

t
(t) 2e.
On the other hand, each face has at least three edges on its boundary, so

t
(t) 3f.
We get 3f 2e, and, using Eulers formula, 3(2 n +e) 2e and
e 3n 6.
Finally, if e = 3n 6 then 3f = 2e and it must be that every face has exactly
three edges on its boundary.
(b) If the graph is disconnected we consider one particular connected component
of it, so assume that G is connected. If G has two vertices or less the result
is immediate, so assume that n 3. Recall that d
G
(x) denotes the degree of
81
a vertex x in G. The sum

x
d
G
(x), ranging over the vertices x of G, counts
every edge twice, so

x
d
G
(x) = 2e.
As we have seen, e 3n 6, so

x
d
G
(x) 6n 12.
If the degree of every vertex is at least 6, we get
6n 6n 12,
which is a contradiction. Therefore, there must be a vertex with degree at most
5.
An intuitive way to think about Theorem 17.2.2(a) is that once a graph has too
many edges, there is no more room for them in the plane and they start intersecting.
This gives a way to prove that a particular graph is not planar. Take K
5
, for example.
It has 5 vertices and 10 edges, and 10 > 3 5 6. Thus K
5
is not planar! In fact, no
K
n
is planar for n 5, since they all contain K
5
as a subgraph. On the other hand,
K
n
is planar for n 4, as can be demonstrated by their simple planar drawings. This
illustrates a point that might be obvious by now: proving a graph to be planar is
often easier than proving the opposite. (Just draw it!
tm
)
How about complete bipartite graphs? It is easy to verify that K
i,j
is planar when
i 2 or j 2. The smallest remaining suspect is K
3,3
. Playing around with drawings
doesnt help: There seems to be no way to draw K
3,3
without intersections. Lets try
the trick that worked for K
5
: The number of vertices of K
3,3
is 6, its number of edges
is 9, and 9 3 6 6. No luck. We need a stronger tool, and here it is:
Proposition 17.2.3. For any simple planar graph G with n vertices and e edges, if
G does not contain a cycle of length 3 then e 2n 4.
Proof. We can assume that G is connected as in Theorem 17.2.2. Let f be the number
of faces of G and let (t) be the number of edges adjacent to a face t. These edges
make up a cycle in G, and thus their number is at least 4, implying (t) 4. Consider
the sum

t
(t), over all faces t of G. Each edge is adjacent to at most two faces,
thus
4f

t
(t) 2e.
Using Eulers formula, we get 4(2 n +e) 2e and e 2n 4.
With this result were nally in business: K
3,3
does not contain an odd cycle since
it is bipartite, thus every cycle in the graph has length at least 4. Since 9 > 2 6 4,
K
3,3
is not planar. Lets summarize what weve learned.
82
Theorem 17.2.4. K
n
is planar if and only if n 4 and K
i,j
is planar if and only if
i 2 or j 2.
At this point we have laid the groundwork for one of the most striking results
concerning planar graphs, known as Kuratowskis theorem. To state it we need the
following denition:
Denition 17.2.5. Given a graph G = (V, E), an edge subdivision operation on an
edge u, v of G results in the graph (V x, (Eu, v) u, x, x, v), where
x , V is a new vertex. A graph G

is said to be a subdivision of G if it can be obtained

from G by successive applications of edge subdivision.
Kuratowskis theorem says that not only are K
5
and K
3,3
non-planar, but every
non-planar graph contains either a subdivision of K
5
or a subdivision of K
3,3
. That
is, the graphs K
5
and K
3,3
characterize the whole family of non-planar graphs!
Theorem 17.2.6 (Kuratowskis theorem). A graph is planar if and only if it does
not contain a subdivision of K
5
or a subdivision of K
3,3
as a subgraph.
17.3 Coloring planar graphs
You might have heard of the four-color problem. It was posed in the mid-19th century
and occupied some of the best discrete mathematicians since that time. The original
formulation is in terms of political maps. In such maps, neighboring countries are
drawn with dierent colors. The question is how many colors are needed. It is easy
to construct simple examples of maps that need at least four colors. The four color
problem asks whether four colors always suce, for any political map. (We require
that every country is connected, unlike, say, the US.)
This problem is equivalent to whether every planar graph can be colored with
four colors. (To see this, construct a graph whose vertices correspond to countries
and whose edges connect neighbors through border segments.) It took over a century
until Appel and Haken found a proof that four colors always suce, and even that
was possible only by using computers to conduct extensive case enumeration and
analysis. To this date no proof of the four color theorem is known that does not rely
on computers. On the other hand, in 1890 Heawood discovered a beautiful proof that
ve colors always suce. To prepare for his proof, let us warm up by showing that
every planar graph can be colored with 6 colors. The proof is surprisingly simple.
Theorem 17.3.1. The chromatic number of a planar graph G is at most six.
Proof. By induction on the number n of vertices of G. If n 6 the claim is trivial.
Assume every planar graph with at most k vertices can be colored with 6 colors or
less, and consider a graph G = (V, E) with k + 1 vertices. By Theorem 17.2.2(b),
there is a vertex v of G with degree at most 5. Let G

be the induced subgraph of

G on the vertices V v. By the induction hypothesis, G

can be colored with ve

colors or less. Color the vertices V v of G with the colors that they are assigned
83
in the coloring of G

. Assign to v the color that is not used by its neighbors. Since

the degree of v is at most ve, such a color exists. This species a valid coloring of
G.
We are now ready for Heawoods ve color theorem.
Theorem 17.3.2. The chromatic number of a planar graph G = (V, E) is at most
ve.
Proof. The proof proceeds by induction on the number n of vertices of G. The base
case is trivial. Assume every planar graph with at most k vertices can be colored with
5 colors or less, and consider a graph G = (V, E) with k+1 vertices. Let v be a vertex
of G with degree at most 5. If d
G
(v) < 5 we can produce a 5-coloring of G as in the
proof of Theorem 17.3.1. Assume d
G
(v) = 5 and let c : (V v) 1, 2, 3, 4, 5 be
a 5-coloring of the induced subgraph G

of G on the vertices V v. This coloring

exists by the induction hypothesis.
We consider a particular drawing of G in the plane and henceforth regard G as a
plane graph. Let v
1
, v
2
, v
3
, v
4
, v
5
be the neighbors of v in the order they appear around
v in G. (That is, according to one of the circular orders in which the corresponding
edges emanate from v in G.) Without loss of generality, assume that c(v
i
) = i for
1 i 5. (Note that if some color is unused by v
1
, v
2
, v
3
, v
4
, v
5
, we can simply assign
that color to v.) We distinguish between two cases: Either there does not exist a
path between v
1
and v
3
in G that uses only vertices of colors 1 and 3, or there does.
There is no such path. In this case consider the subgraph G

of G that is the
union of all paths that begin at v
1
and use only vertices with colors 1 and 3.
Note that neither v
3
nor its neighbors belong to G

. We produce a 5-coloring
of G as follows: All the vertices of G

of color 1 are assigned the color 3, all the

vertices of G

of color 3 are assigned the color 1, the vertex v is assigned the color
1, and all other vertices of G keep the color assigned by c. No monochromatic
edges are created by this assignment and the coloring is valid.
There is such a path. Consider a path P from v
1
to v
3
that uses only vertices with
colors 1 and 3. Together with the edges v, v
1
and v, v
3
this forms a cycle.
The vertices v
2
and v
4
lie on dierent sides of this cycle. (Here we use the
Jordan curve theorem.) Therefore there is no path between v
2
and v
4
that uses
only vertices with colors 2 and 4, and we can apply the reasoning of the previous
case.
17.4 Concluding remarks
There are many more amazing results associated with planar graphs. Two of the most
striking are Farys theorem and Koebes theorem. Farys theorem states that every
planar graph can be drawn in the plane without edge crossings, such that all the arcs
84
are straight line segments. Koebes theorem says that every planar graph is in fact
isomorphic to an incidence graph of a collection of nonoverlapping discs in the plane.
(The vertices of this graph correspond to the discs, and two vertices are adjacent if
and only if the corresponding disks are tangent.) Farys theorem is an immediate
consequence of Koebes theorem, although they were discovered independently. Both
are remarkable.
85