DISCRETE MATHEMATICS AND COMBINATORY

-FOR COMPUTER SCIENCE

CHAPTER 2: ELEMENTARY COUNTING PRINCIPLES

Objectives:-On completion of the chapter the students will be able to:

 Identify the elementary counting principle.

 Solve a counting problems using a counting method

 Identify the difference between the permutation and combination of a counting method

 Understand and differentiate the method of permutation with and without repetition.

 Understand and differentiate the method of combination with and without repetition.

 Understand the binomial theorem.

Introduction
Combinatorics is a fascinating branch of discrete Mathematics, which deals with the
art of counting. Very often we ask the question, In how many ways can a certain task
be done? Usually combinatorics comes to our rescue. In most cases, listing the
possibilities and counting them is the least desirable way of finding the answer to such
a problem. Enumeration, the counting of objects with certain properties is an important
part of combinatorics. We must count objects to solve many different type of problems.
Counting is also required to determine whether there are enough telephone numbers
or internet protocol addresses to meet demand. Furthermore, counting techniques are
used extensively when probabilities of events are computed.
The elementary counting principle, which we will study section 2.1 to 2.3 can solve a
tremendous variety of problems. We can phrase many counting problems in terms of
ordered or unordered arrangements of the objects and combinations are used in many
counting problems.
2.1 Addition principle
Objective: After completing this section the student should be able to:
 Understand the addition principle
 Solve some problems using addition principle.
 DISCRETE MATHEMATICS AND COMBINATORY

Theorem 2.1 (Addition principle)

Let � and � be two mutually exclusive tasks. Suppose task � can be done in � ways
and task � in � ways.Then there are � + � ways to do one of these tasks.
Example 2.1 Suppose that either a member of the mathematics faculty or a student
who is mathematics major is chosen as a representative to a university committee.
How many different choices are there for this representative if there are 37 members of
the mathematics faculty and 83 mathematics majors?
Solution: Let � be the task, choosing a member of the mathematics faculty, can be
done in 37 ways. Let � be the task, choosing a mathematics major, can be done in 83
ways. From the sum (addition) rule, it follows that there are 37 + 83 = 120 possible
ways to pick this representative.
The addition principle can be extended to any finite number of pair wise mutually
exclusive tasks, using induction, for instance, let �1, �2, �3,…, �� be � pair wise
mutually exclusive tasks. Suppose task �� can be done in �� ways, where1 ≤ i ≤ n.

Then task�1, �2, �3,…, �� can be done to �1 + �2 + ⋯ + �� ways.

Example 2.2: A freshman has selected four courses and needs one more course for the
next term. There are 15 courses in English, 10 in French and 6 in German. She is
eligible to task. In how many ways can she choose the fifth course?
Solution: Let � be the task of selecting a course in English, � be the task of selecting a
course in French and � that of selecting a course in German.
These tasks can be done in 15,10 and 6 ways, respectively, and are mutually exclusive,
so by addition principle, the fifth course can be selected in;
|�| + |�| + |�| = 15 + 10 + 6 = 31 way.
Example 2.3: A student can choose a computer project from one of three lists. The
three lists contain 23,15and 19 possible projects, respectively. How many possible
projects are there to choose from?
Solution: Let �, � ��� � be the first, second and third lists respectively. And the list
can be done 23, 15 and 19 ways respectively. Hence there are 23+15+19=57 projects
to choose from.
The sum can be phrased in terms of sets as: if �1, �2, … , �� are disjoint sets, then the
number of elements in the union of these sets is the sum of the number of elements in
them. To relate this to our statement of the sum rule, let �� be the task of choosing an

By: Wakuma MK Kumsa (MSc.) Page 1

 DISCRETE MATHEMATICS AND COMBINATORY

element from �� for � = 1,2, … , �. There are |��| (|��| is the notation for the cardinality of
��) ways to do ��. From the sum rule, since no two of the tasks can be done, at the same
time the number of ways to choose an element from one of the sets, which is the number
of elements in the union is
|�1 ∪ �2 ∪ … ��| = |�1| + |�2| + ⋯ + |��|
This equality applies only when the sets in question are disjoint.
Exercise 2.1
1. There are 18 mathematics majors and 325 computer science major at a college.
How many ways are there to pick one representative who is either mathematics
major or a computer science major?
2. Let � and � be finite disjoint sets, where |�| = �, and |�| = �. find |� ∪ �|
3. Let � be a universal set contain the disjoint set � and � such that
|�| = 2� +�, |�| = 2� + 3�. find |� ∪ �|

2.2. The inclusion- exclusion principle

Objective: After completing this section the student should be able to:
 Understand the method of inclusion-exclusion principle
 Understand the difference between the method of sum rule and
inclusion-exclusion principle.
 Solve some problems using inclusion-exclusion principle.
When two tasks can be done at the same time, we can’t use the sum rule to count the
number of ways to do one of the two tasks. Adding the number of ways to do one of the
two tasks. Adding the number of ways to do each task leads to an over count, since the
ways to do both tasks are counted twice.
Question: Let � ��� � be any two finite sets. How is |� ∪ �|related |�| ���|�| ?
Theorem 2.2 (Inclusion-exclusion principle)
Suppose a task � can be done in � ways, task � in � ways and both can be accomplished in �
different ways. Then task � �� � can be done in � + � − �
We can phrase this counting principle in terms of sets. Let � ��� � be two finite sets.
Then
|� ∪ �| = |�| + |�| − |� ∩ �|

By: Wakuma MK Kumsa (MSc.) Page 2

 DISCRETE MATHEMATICS AND COMBINATORY

Example 2.4: Find the number of positive integers ≤ 300 and divisible by 2 or 3.
Solution: Let � = {� ∈ ℕ: � ≤ 300 ��� ��������� �� 2}
� = {� ∈ ℕ: � ≤ 300 ��� ��������� �� 3}
Then � ∩ � consists of positive integers ≤ 300 that are divisible by 2 and 3. That is, divisible by 6.
Thus,
� = {2,4, … ,300}
� = {3,6, … ,300} and � ∩ � = {6,12, … ,300}.
Clearly,|�| = 150, |�| = 100 ��� |� ∩ �| = 50 . By theorem 1.2,
|� ∪ �| = |�| + |�| − |� ∩ �| = 150 + 100 − 50 = 200 Thus,
there are 200 positive integers ≤ 300 and divisible by 2or 3.
Example 2.5 Find the number of positive integers ≤ 3000 and not divisible by 7 or 8.
Solution: Let � = {� ∈ ℕ: � ≤ 3000 ��� ��������� �� 7}
� = {� ∈ ℕ: � ≤ 3000 ��� ��������� �� 8}
We need to find |�′ ∩ �′|

|�′ ∩ �′| = |(� ∪ �)′| = |�| − |� ∪ �| , Where � be the universal set.

= |�| − |�| − |�| + |� ∩ �|

= 3000 − 428 − 375 + 53 = 2250

Corollary 2.3: Let �, � ��� � be three finite sets.
Then |� ∪ � ∪ �| = |�| + |�| + |�| − |� ∩ �| − |� ∩ �| − |� ∩ �| + |� ∩ � ∩ �|
Proof:
|� ∪ � ∪ �| = |� ∪ (� ∪ �)|
= |�| + |� ∪ �| − |� ∩ (� ∪ �)| (By theorem 2.2)
= |�| + [|�| + |�| − |� ∩ �|] − [|� ∩ �| ∪ |� ∩ �|]
= |�| + |�| + |�| − |� ∩ �| − [|� ∩ �| + |� ∩ �| − |(� ∩ �) ∩ (� ∩ �)|]
= |�| + |�| + |�| − |� ∩ �| − |� ∩ �| − |� ∩ �| + |� ∩ � ∩ �|
Example 2.6: Find the number of positive integers ≤ 2076 and divisible by 3, 5 and 7.
Solution: Let �, � ��� � denote the sets of positive integers ≤ 2076 and divisible by
3, 5 and 7, respectively, by the corollary 1.3
|� ∪ � ∪ �| = |�| + |�| + |�| − |� ∩ �| − |� ∩ �| − |� ∩ �| + |� ∩ � ∩ �|

= 692 + 415 + 296 − 138 − 59 − 98 + 19 = 1127

By: Wakuma MK Kumsa (MSc.) Page 3

 DISCRETE MATHEMATICS AND COMBINATORY

Example 2.7: A survey among 100 students show that of the three ice-cream flavors
vanilla, chocolate and strawberry,50 students like vanilla, 43 like chocolate, 28 like
strawberry ,13 like vanilla and chocolate , 11 like chocolate and strawberry , 12 like
strawberry and vanilla and 5 like all of them. Find the number of students surveyed who
like each of the following flavors
a) Chocolate but not strawberry
b) Chocolate and strawberry but not vanilla
c) Vanilla or chocolate but not strawberry.
Solution: Let V, C and S symbolize the set of students who like vanilla, chocolate and
strawberry flavors, respectively, draw three intersecting circles to represent them in the
most general case as in figure 1.1
5 students like all flavors’, |� ∩ � ∩ �| = 5
12 students like both strawberry and vanilla, |� ∩ �| = 12
but 5 of them like chocolate also, therefore, |(� ∩ �) − �| = 5
11 students like chocolate and strawberry so, |� ∩ �| = 11 but 5 of them like vanilla ,
therefore, |(� ∩ �) − �| = 6
13 students like vanilla and chocolate, but 5 of them like strawberry also,
therefore, Of the 28 students who like strawberry we have already accounted
for 7+5+6=18

.
Figure 2.1
So, the remaining 10 students belongs to the set
Similarly,
Thus, we have accounted for 90 of the 100 students.
The remaining 10 students lie outside the region as in figure 1.Now,
a)
So, 32 students like chocolate but not strawberry

By: Wakuma MK Kumsa (MSc.) Page 4

 DISCRETE MATHEMATICS AND COMBINATORY

b) Therefore, 6 students like both chocolate and strawberry but not

vanilla.
c) students like vanilla or chocolate but not strawberry. They are
presented by the region .

Exercise 2.2 Let be two sets such that , , and

. Find the cardinality of each set.

a) b) c) ′
d) ′ ′

2. Let be finite disjoint set, where , . Find the cardinality

of each set
a) b) c)
3. Find the cardinality of each set in (2) where , B is finite
4. According to a survey among 160 college students, 95 students takes a course
in English , 72 takes a course in French, 67 takes a course in German , 35 take
a course in English and in French , 37 takes a course in French and in German,
40 takes a course in German and in English and 25 take a course in all three
language. Find the number of students in the survey who take a course in
a) English but not German b) English, French or German

2.3. Multiplication principle

Objective: After completing this section the student should be able to:

 Understand the multiplication principle

 Solve some counting problems using multiplication principle

The most important counting principle is the multiplication principle. It allows for
counting (like, example: the experiment consisting of both rolling a dice and tossing a
coin), and this principle apply when a procedure is made up of separate task.
Multiplication principle: if an experiment consisting of independent steps, in such a
way that:
 The first step has possible out come
 Any outcome of the first can be followed by outcome of the 2nd step,
 Any one of the first and the second step can be followed outcome of the 3rd step
.

By: Wakuma MK Kumsa (MSc.) Page 5

 DISCRETE MATHEMATICS AND COMBINATORY

Then the total number of

outcomes ,…,
�1 = 3 choices �2 = 2
choices �3 = 4 choices

In total �1�2�3 =
3 × 2 × 4 = 24
possible out coomes.

Figure 2. 2 Illustrate multiplication principles

Example 2.8 How many distinct phone numbers are there if we assume that a phone
number is made of 6 digits with the first digit begin different from 0 and 1?
Solution: Assume that �1 be the first digit, �2 be the second digits, �3, �4,�5,�6 be the
3rd , 4th ,5th and 6th digit respectively. But �1 ≠ 0 ��� 1. So we have 8 possible choice
of �1 and we have 10 possible choices for the digit �2 to �6.
Therefore, 8 × 105 = 800,000 distinct phone number.
Example 2.9 In how many ways can the letters of the word ‘CAR’ be reordered to
produce distinct ‘words’.
Solution: We have 3 possibilities for the first letter, 2 possibilities for the 2nd letter
and have to use the remaining letter. So, there are 3 × 2 × 1 = 6 distinct ‘words’.
Theorem 2.4 (Multiplication principle)
Suppose a task � is made up of two subtasks. Subtask �1 followed by subtask T2. If
subtask �1 can be done in �1 ways and subtask �2 in �2 different way for each way
subtask �1 can be done, then task � can be done in �1�2 ways.
Example 2.10 Find the number of two letter words that being with a vowel a, e, i, o or u.
Solution :The task of forming a two-letter word consists of two subtasks �1 ��� �2 ,
�1 consisting of the first letter and �2 selecting the second letter; as figure 2.3 shows
Number of choices

Subtask �1 Subtask �2
Figure 2.3

By: Wakuma MK Kumsa (MSc.) Page 6

 DISCRETE MATHEMATICS AND COMBINATORY

Since each word must begin with a vowel, �1 can be accomplished in five ways. There is
no restriction on the choice of the 2nd letter, so �2 can be done in 26 ways (figure 2.4).
Number of choices

5 26
Subtask �1 Subtask �2
Figure 2. 4
Therefore, by the multiplication principle the task can be performed in
5 × 26 = 130 different ways. In other words, 130 two letter words begin with a vowel.
The multiplication principle can also be extended to any finite number of subtasks.
Suppose a task � can be done by n successive subtasks, �1, �2, … , ��. If subtask �� can
be done in �� different ways after��−1 has been completed, where 1 ≤ � ≤ �, then task
� can be done in �1 × �2 × �3 × … × �� ways. The multiplication principle can be
applied to prove that a set with size n has 2� subsets, as shown below.
Example 2.11: Show that a set � with n elements has 2� subset.
Solution: Every subset of � can be uniquely identified by an � -bit words (see fig 2.5).
The task of forming an � –bit word can be broken down to n subtasks. Selecting a bit
for each of the n- positions. Each position in the word

…
? ? ? ? ? ? ? ?
Figure 2.5
has two choices 0 or 1: so by the multiplication principle, the total number of n-bit words that
can be formed is 2.2 .2…2=2n (see figure 2. 6)

2 2 2 2 2 2 2
Figure 2. 6

By: Wakuma MK Kumsa (MSc.) Page 7

 DISCRETE MATHEMATICS AND COMBINATORY

Example 2.12: How many one to one functions are there from a set with � elements to one with
� elements?
Solution: First note when � > � there is no one to one functions from a set with �
elements to a set with � elements. Now let � ≤ �. Suppose the elements in the
domain are �1, �2, … , ��. There are � ways to choose the value of the function at �1.
Since the function is one to one, the value of the function at �2 can be picked in (� −1)
ways (since the value used for �1 can’t be used again). In general, the value of the
function at �� can be choosen in � − � + 1 ways.

By the multiplication principle, there are �(� − 1)(� − 2) … (� − � + 1) one to one

functions from aset with � elements to one with � element.

For instance, there are 5 × 4 × 3 = 60 one to one functions from a set with three elements to a set
with five elements.

Exercise 2.3
1. How many bit strings are there of length eight.
2. How many bit strings of length ten begin and end with a 1?
3. How many different functions are there from a set with 10 elements to a set with
the following numbers of elements
a) 2 b) 3 c) 4 d) 5
4. How many one to one function are there from a set with five elements to a set
with the following number of element
a) 4 b) 5 c) 6 d) 7
5. A multi-choice test contains ten questions. There are four possible answer for
each question
a) How many ways can a student answer the questions on the test if every
question is answered?
b) How many ways can a student answer the question on the test if the student
can leave answers blank?

6. A particular brand of shirt comes in 12 colors, has a male version and a

female version and comes in three sizes for each sex. How many different types
of this shirt are made?

By: Wakuma MK Kumsa (MSc.) Page 8

 Discrete Mathematics And Combinatorics (Math 2052) 2016

2.4 Permutation and combination

Objective: After completing this section the student should be able to:
 Understand the method of permutation and combination
 Explain the definition of permutation with and without repetition
 Explain the definition of combination with and without repetition

 Solve the counting problems using these methods.

Most counting problems we will be dealing with can be classified into one of four categories.
We explain such categories by means of an example.
Example 2.13: Consider the set {�, �, �, �}. Suppose we “select” two letters from these
four. Depending on our interpretation, we may obtain the following answers.
i. Permutations with repetitions. The order of listing the letters is important,
and repetition is allowed. In this case there are 4 ·4 = 16 possible selections:
�� �� �� ��

�� �� �� ��

�� �� �� ��

�� �� �� ��

ii. Permutations without repetitions. The order of listing the letters is important, and
repetition is not allowed. In this case there are 4 ·3 = 12 possible selections:

�� �� ��

�� �� ��
�� �� ��
�� �� ��

iii. Combinations with repetitions. The order of listing the letters is not important, and
repetition is allowed. In this case there are

By: Wakuma MK kumsa (MSc.) Page 9

 Discrete Mathematics And Combinatorics (Math 2052) 2016

�� �� �� ��

�� �� ��
�� ��
��
iv. Combinations without repetitions. The order of listing the letters is not important,
and repetition is not allowed. In this case there are.

Possible selections: �� �� ��

�� ��
��

Permutations without Repetitions

Definition 2.4.1. A permutation of a set of distinct objects is an ordered arrangement
of these objects, we also are interested in ordered arrangements of some of the
elements of a set.
A permutation of a set of � (distinict) elements taken � (0 ≤ � ≤ �) at a time is an
arrangement of � elements of the set. For convenience, it is called a � − permutation.
If � = � then the � − permutation is called a � − permutation. The number of � − permutation
of a set of size � is denoted by �(�, �), � distinct objects can be
reordered in
�! = �(� − 1)(� − 2) … 2 × 1 different ways of doing so.
Note: we will use the convention that �! = 1.
Example 2.14 :Find the number of permutation, that is, 3 −permutations of the
elements of the set {�, �, �}
Solution: By the multiplication principle, the number of 3 −permutation of three elements is 3
× 2 × 1 = 6. Or can be obtained systematically using a tree diagram.

By: Wakuma MK kumsa (MSc.) Page 10

 Discrete Mathematics And Combinatorics (Math 2052) 2016

1st element 2nd element 3rd element permutation

b c abc
a c b acb
c ____________ a bca
b a ____________ c bac
a____________b cab
c
b ____ a cba

Figure 1.7
Example 2.15 .Eight runners take part in a race. How many different of ways of
allocating medals (gold, silver and bronze) are there?
Solution: We choose � = 3 medalists from the � = 8 runners (the order doesn’t
matter). The number of 3 −permutation of 8 runners is 8 × 7 × 6 = 336 ways the
medals can be handed out, thus, �(8,3) = 336.
If we went to choose only � ≤ � of the n objects and retain the order in which we
choose the object the there are �(�, �) = �(� − 1)(� − 2) … (� − � + 1) different
ways of doing so.
Theorem2.5: The number of � −permutation of a set of � (distinct) elements is given
by

Proof: The first elements of the permutation can be chosen in � ways, since there are
� elements in the set. There are (� − 1) ways to choose the second elements of the
permutation. Since there are (� − 1) elements left in the set after using the element
picked for the first position.Similarlly, there are (� − 2) ways to choose the third
element, as so on until there are exactly � − (� − 1) = � − � + 1 ways to choose the
nth element. Thus, by the multiplication principle,
�(�, �) = �(� − 1)(� − 2) … (� − � + 1)

By: Wakuma MK kumsa (MSc.) Page 11

 Discrete Mathematics And Combinatorics (Math 2052) 2016

In particular, suppose !
Example 2.16 How many ways are there to select a first-prize winner, a second prize
winner and a third-prize winner, from 100 different people who have entered contest?
Solution: The number of ways to pick the three prize winner (1st ,2nd and 3rd ) is the
number of ordered selections of three elements from a set of 100 elements, that is the
3 −permutations of a set of 100 elements.

Example 2.17: Find the number of words that can be formed by scrambling the letter
of the word SCRAMBLE (remember, a word is just an arrangement of symbols, it
need not make sense )?
Solution: The word SCRAMBLE contains eight distinct letters. Therefore, the
number of words that can be formed equals. The number of arrangement of the letters
in the word, namely
�(8,8) = 8! = 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 40,320

Combinations without Repetitions

Consider again the case that we want to choose � ≤ � from � objects, but this time
we do not want to retain the order. If we retained the order, there would be �(�, �) =

possibilities. But �! of these ways result in the same set of � objects. Since the
ordering is not important, only their membership is important. We will investigate
such unordered arrangements in this section.
Definition 2.2: An � −combination of elements of a set, where 0 ≤ � ≤ � , is an
unordered selection of � elements from the set. Thus, an � −combination is simply a
subset of the set with � −elements. The number of � −combinations of a set with �

elements is denoted by . Both notations frequently appear in

combinatorics. The number of combination is also called the binomial coefficient.

By: Wakuma MK kumsa (MSc.) Page 12

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Example 2.18: Find the number of � −combinations of the set {�, �, �} when � =
0,1,2 �� 3.
Solution:
 Exactly one subset contains zero element, the null set ombinations:
C
 Three subsets contain one elements each: .
Number of combinations:
 Three subset contains two elements each:
Number of combinations:
 Finally, exactly one subset contains three elements: the set itself
Number of compinations:
Theorem 2.6: The number of combinatios of a set with n elements, where is a
nonnegative integer and is an integer with equals

Proof: By definition, there are , combinations of a set of elements,

Each combination contains elements and contributes !;
permutation, so, the total number of permutation is . But by
definition, there are permutations.
Therefore,
That is,

Note:
1. , that is, the number of 0-combinations of a set with n
elements is one.
2. , that is, the number of n-combinations of a set with n
elements is also one.

Corollary 2.7 Let and be nonnegative integer with . Then

Proof: From theorem 2.6, it follows that

And

By: Wakuma MK kumsa (MSc.) Page 13

 Discrete Mathematics And Combinatorics (Math 2052) 2016

!
Hence, �(�, �) = �(�, � − �)
Example 2.19
John wants to go to the pub with 3 of his 5 best friends. How many options does John have?
Solution: 3-combination of 5 is

Permutations with Repetitions

The permutation and computation examined so far involved unrepeated items. For
instance, a letter or digit may be used more than once on a licenses plate. When a
dozen donuts are selected, each variety can be chosen repeatedly. This contrasts with
the counting problems discussed earlier in the chapter where we only be used at most
once. In this section we will show how to solve counting problems where elements
may use more than one. Counting permutation when repeated is allowed can easily
be done using the product rule.
Example 2.20: How many strings of � length can be formed from the English alphabet?
Solution: By the product rule, since there are 26 letters and since each letter can be used
repeatedly, we see that there are 26� strings of length n.

Theorem 2.8:
The number of � −permutation of a set of � objects with repetition allowed is ��
Proof: There are � ways to select an element of the set of each of the � position in the
� −permutation is allowed, since for each choice all � objects are available. Hence by
the multiplication principle there are �� � −permutation when a repetition is allowed.

Theorem 2.9: The number of permutation of � items of which �1 items are of one type, �2
are of a second type, and �� are of a kth type, is

By: Wakuma MK kumsa (MSc.) Page 14

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Example 2.21 Find the number of bytes contain exactly three 0’s
Solution:

=
!

= 56
Example 2.22. Find the number of different arrangement of the letter of the word
REFERENCE.
Solution: The word REFERENCE contain nine letters; two R’s and four E’s, the remaining
letters are distinct, now by theorem 2.9, the total number of words are 7560.
Combinations with Repetitions
Just as permutation can deal with repeated elements, so can combinations (called
selections).
Example 2.23 Find the number of 3 −combination of the set � = {�, �}
Solution: � contains � = 2 elements. Since each combination must contain three
elements � = 3. Since � > �, the elements of each combination must be repeated.
Consequently, a combination may contain three a’s, two a’s and one b’s, one a’s and two
b’s or three b’s. Using the set notation, the 3-combinations are
{�, �, �}, {�, �, �}, {�, �, �}, ��� {�, �, �}
So, there are four 3-combination of a set of two elements.

Theorem 2.10: The number of � −combinations with repetition from a set of � elements is
�(� + � − 1, �).
Proof: Each � −combination with repeated elements from a set of � elements can be
considered a string of � �′� and (� − 1) slashes (that means, for instance if � = 3 ��
∕ �� ∕ �� indicates that two elements select 1st task, two select 2nd and two select 3rd
task) each strings contains � + � − 1 symbols,of which � are alike (�’�) and are
alike (slashes).Therefore by theorem 2.9,the number of such strings, that is r-
combination equals

By: Wakuma MK kumsa (MSc.) Page 15

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Example 2.24. Suppose that a cookie shop has four different kinds of cooking. How
many different ways can six cookies be chosen? Assume that only the types of cookie
are not the individual cookies or the order in which they are chosen matter
Solution: The number of ways to chose six cookies is the number of 6-combinations
of a set with four elements. From theorem 1.10, this
equals . Since

There are 84 different ways to chosen the six cookies.

Table 2.1 gives a summary of the different ways how object can be drawn from object

With repetition Without

repetition
Retaining �!
�(�, �) =
order (� − �)

Not retaining order (

�+�−1
)
� �
�(�, �) = ( )
�
(� + � − 1)
�! =
= �! (� − 1)!
(� − �)! �!

Table 2.1 different ways of drawing from n objects.

Exerices 2.4
1. Make each sentence as true or false. When is an arbitrary non negative integer
and
a) f)
b) g)
c) ! h) !
d) ! i) !
e) ! j)
2. Find the number of two-digit numerals that can be formed using the digits
and that contain no repeated digits.

3. How many permutation are there of the set {�, �, �, �, �, �}?

4. Let � = {1,2,3,4,5}

By: Wakuma MK kumsa (MSc.) Page 16

 Discrete Mathematics And Combinatorics (Math 2052) 2016

a) List all the 3 −permutation of S

b) List of the 3 −combination of S
5. How many bit strings of length ten contain
a) Exactly four 1 s
b) At most four 1 s
c) An equal number of 0 s and 1 s
6. Solve the equation:
a) �(�, 1) = 6 c) �(�, � − 1) = 5040
b) �(�, 1) = 10 d) �(�, � − 2) = 55

7. In how many different ways can five elements be selected order from a set with
three elements when repetition is allowed?
8. How many ways are there to select five unordered elements from a set with three
elements when repetition is allowed.
9. How many different ways are there to choose a dozen dounts from the 21 varieties
at a dount shpo?
10. A bagel shop has onion bagels, poppy seed bagels, egg bagels, salty bagels and
plain bagels. How many ways are there to choose.
a. Six bagels
b. A dozen bagels
c. Two dozen bagels
d. A dozen bagels with at least one of each kind
e. A dozen bagels with at least three egg bagels and no more than two slaty
bagels
11. How many different strings can be made from the letters in MISSISSIPPI, using
all the letters.
12. How many different strings can be made from the letter in ORONO, using some or
all of the letters
13. How many strings with five or more characters can be formed from the letters in
SEERESS?

By: Wakuma MK kumsa (MSc.) Page 17

 Discrete Mathematics And Combinatorics (Math 2052) 2016

2.5 The Binomial Theorem

Objective: After completing this section the student should be able to:

 Explain the binomial theorem

 Explain the Pascal’s triangle and Pascal identity
 Understand the binomial theorem.
 Solve same problems using binomial theorem.

The binomial theorem gives the coefficients of the expansion of powers of binomial
expression. A binomial expression is simply the sum of terms, such as � + �.
Theorem 2.11(The Binomial Theorem)
If � is a nonnegative integer and � and � be a real variable, then

The notation ∑ means that the sum extends over all integers.
Proof: Since (� + �)� = (� + �)(� + �) … (� + �) to n factors. (� + �)� is expanded
by multiplying an � from some of the factors on the RHS and a � from the remaning
factors. That is, every term is obtained by selecting an � from any of the � − � factors
and a � from the remaining � factor. Thus, every term in the expansion is of the form
� ��−���, where c denotes the coefficient and 0 ≤ � ≤ �.
Notice that the coefficient of ��−��� is the number of ways of selecting an � from any
� − � of the � factors (and hence a � from the remaining � factors). Therefore
Coefficient of

So, every term in the expansion is of the form where 0 ≤ � ≤ �. Thus,

Example 2.25. Find the binomial expansion of (2� − 3�)4

Solution: Here � = 2� ��� � = 3b and � = 4 .using the binomial theorem

= (2�)4 + 4(2�)3(−3�) + 6(2�)2(−3�)2 + 4(2�)(−3�)3 + (−3�)4

By: Wakuma MK kumsa (MSc.) Page 18

 Discrete Mathematics And Combinatorics (Math 2052) 2016

= 16�4 − 96 �3� + 216 �2�2 − 216��3 + 81�4

Example 2.26: What is the coefficient of �12�13 in the expansion of (2� − 3�)25
Solution : (2� − 3�)25 = (2� + (−3�))25. By the binomial theorem, we have

.
Consequently, the coefficient of �12�13 in the expansion is obtained when
� = 13 ,namely,

We can prove some useful identities using the Binomial Theorem.

Corollary 2.12 Let � be a non negative integer. Then

That is, the sum of the binomial coefficients is 2� , in other words, a set with �
elements has 2� subsets. Proof: By the binomial theorem

Let � = � = 1, then

Thus,
Corollary 2.13 Let � be a positive integer. Then

Proof: By the binomial theorem it follows that

Corollary 2.14

Where � ≥ 1,that is, the sum of the “even” binomial coefficient equals that of the “odd”
binomial coefficients.
Proof: By using the corollary 2.13, we have

By: Wakuma MK kumsa (MSc.) Page 19

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Corollary 2.15 Let n be a non negative integer. Then

Proof: Again by the binomial theorem, put � = 1 ��� � = 2 , then

Hence ,

Pascal’s identity and triangle

Definition 2.3 The various binomial coefficients ,where 0 ≤
� ≤ �, can be arranged in the form of a triangle, called Pascal’s triangle [Although
Pascal’s triangle is named after pascal, it appeared in 1330 work by the Chinese
Mathematician Chushi-kie], as shown in figure 2.8 and figure 2.9

row 0

row 1

row 2

row 3

row 4

Figure 2.8

By: Wakuma MK kumsa (MSc.) Page 20

 Discrete Mathematics And Combinatorics (Math 2052) 2016

1 row 0
1 1 row 1
1 2 1 row 2
1 3 3 1 row 3
1 4 6 4 1 row 4

Figure 2.9
Theorem 2.16 (Pascal identity) Let � and � be positive integers with � ≥ �. Then

Pascal’s triangle has the following property

 Pascal’s identity, together with the initial condition for
all integers �, can be used to recursive define binomial coefficients.
 Pascal’s triangle is symmetric about a vertical line through the middle. This is so since
�(�, �) = �(�, � − �)

Theorem 2.17 (Vandermonde’s identity)

Let �, � and r be non negative integers with r not exceeding either � �� �. Then

Remark: This identity was discovered by Mathematician Alexander-Theophile Van demonde

in the eighteenth century
Proof: Suppose that there are � items in one set and � items in a second set. Then the total

number of ways to pick � elements from the union of these sets is .

Another way to pick � elements from the union is to pick � elements from the first set and
then � − � elements from the second set, where � is an integer with 0 ≤ � ≤ �
,this can be done ways, using the r elements from the union also equal.

This proved Vander -monde’s identity.

Corollary 2.18 If n is a non negative integer then
Proof: We use Vander-mode’s identity with � = � = � to obtain:

The last equality was obtained using the identity

By: Wakuma MK kumsa (MSc.) Page 21

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Theorem 2.19: Let � and � be non negative integers with � ≤ �. Then

Exercise 2.5

1. Using the binomial theorem expand each.

a) (� + �)6 b) (� + �)4 c) (2� − 1)5
2. Find the coefficient of �5�8 in (� + �)13
3. Find the coefficient of �4�5 in (2� − 3�)9
4. Find the middle in the binomial expansion of each

a) b) c)

5. Prove that if � and � are integers with 1 ≤ � ≤ � . then

2 � 2 �
6. ∑��=0 ( 2 �) = ∑��=1 (2� − 1) (hint use corollary 1.14 )

7. find a formula for

a) b)

Chapter summary
 Addition principle

If � and � are two mutually exclusive tasks and can be done in � and � ways, respectively,
then task a � or � can be done in � + � ways .
 Inclusion-exclusion principle
Suppose task � can be done in � ways and task � in � ways. If both can be done in �
ways, then task A or � can be done in � + � − � ways.
 Multiplication principle

If task �1 can be done in �1 ways and task �2 in �2 ways corresponding to each way
�1 can occur, these two tasks can be done in that order in �1�2 ways.
 An � −permutation of a set of � distinct element is an arrangement of r elements of the set.
 The number of � −permutations of a set of size � is denoted by �(�, �),

By: Wakuma MK kumsa (MSc.) Page 22

 Discrete Mathematics And Combinatorics (Math 2052) 2016

 The permutation of n distinct objects are n!, !

 The number of permutation of a set of objects with repetition allowed is .
 An r -combination of a set of n elements is a subset with size r, where .
 The number of r-combination is denoted by .


 The number of combinations with repetition from a set of elements is
.
 Let and be a real variable and n is a nonnegative integer, then

 .

Self Test Exercise 2

1. Find the number of positive integer and divisible by
a) c)
b) d)
2. Find the number of positive integers and divisible by
a) 2 or 3 c) 2,3 0r 5
b) 3 or 5 d) 3,5 or 7
3. In how many ways can the letters of the word AFFECTION be arranged,
keeping the vowels in their natural order and not letting the two F’s come
together?
4. In one version of BASIC a variable name consists of letters or a letter
followed by a digit. Find the total number of possible names.
5. Of 40 people, 28 smoke and 16 chew tobacco. It is also known that 10 both
smoke and chew. How many among the 40 neither smoke nor chew?
6. Consider the set

A = {2,4,6, . . . ,114}.
a) How many elements are there in A?
b) How many are divisible by 3?

By: Wakuma MK kumsa (MSc.) Page 23

 Discrete Mathematics And Combinatorics (Math 2052) 2016

c) How many are divisible by 5?

d) How many are divisible by 15
e) How many are divisible by either 3, 5 or both?
f) How many are neither divisible by 3 nor 5
g) How many are divisible by exactly one of 3 or 5?
7. Solve each of the following, where � ≥ 0
a) �(�, �) = 1 c) �(�, 1) = 10
b) �(�, 2) = 28 d) �(�, � − 2) = 55
8. Evaluate

a) c) �(6,6)

b) �(5,3) d) !

9. Find the number of ways of dividing a set of size � into two disjoint subsets of
sizes � and � − �
10. Find the number of three digit numerals that can be formed using the digit
2,3,5,6 and 9 if repetitions are not allowed
11. Find the number of ways seven boys and three girls can be seated in a row if
a) A boy sit at each end of the row
b) A girl sits at each end of the row
c) The girl sit together at one end of the row
12. Find the coefficient of each:
a) �3�5 in the expansion of (� + �)8
b) �4�6 in the expansion of (� − �)10
c) �2�6 in the expansion of (2� + �)8
13. Use the binomial theorem, expand each
a) (� + �)6 c) (2� − 1)6
b) (� − �)5 d) (� + 2�)5
14. Find the largest binomial coefficient in the expansion of each
a) (� + �)5 c) (� + �)6
b) (� + �)4 d) (� + �)8

By: Wakuma MK kumsa (MSc.) Page 24

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Reference:-
1. A. W.F.Edwards,Pascal’s Arithmeticical Triangle. The Johns Hopkins University Press,
Baltimore,MD, 2002.
2. Branislav Kisacanin, Mathematical problems and proof, combinatorics, number theory and
geometry
3. C.Oliver, “ The Twelve Days of Christmas,” Mathematics Teacher, Vol. 70
4. D .P.Acharjya Sreekumar, Fundamental Approach to Discrete Mathematics, 3rd eedition.
5. Discrete Mathematics, Handbook of discrete and Compinatorial Mathematics
6. Hewel Hus, Schaum’s outline, probability Random Variable
7. J.M.Harris.Jeffry L.Hirst.Michael J.Mossinghoff, Combinatorics and Graph Theory, 2nd
edition
8. Kenneth H.Rosen, Discrete Mathematics and its application, 3rd edition.
9. KOSHY, Discrete Mathematics with application
10. M.Eng and J.Casey, “Pascal’s Arithmetical Triangle-ASerendipitious Source for
programming Activities,’’ Mathematics Teacher, Vol 76
11. Mott, Knadel and Baker, Discreate Mathematics
12. P.Z.Chinn,’’inductive patterns, finite Difference, and a Missing Region,’’ Mathematics
Teacher, Vol.81(Sept.1988)
13. R.P.GRIMALDI and B.V.RAMANA pearson, Discreate combinatorial mathematics
14. Seymour Lipschutz,Schaum’s outline, Discrete Mathematics, 3rd edition
15. Steven G. Krantz, Discrete Mathematics

By: Wakuma MK kumsa (MSc.) Page 25

 Discrete Mathematics And Combinatorics (Math 2052) 2016

CHAPTER 3: ELEMENTARY PROBABILITY THEORY

Objective: At the end of this chapter the student should be able to:

 Explain the elementary property of a probability of an event.

 Calculate the probability of an event.
 Explain the conditional probability
 Calculate the conditional probability of an event
 Identify whether the given two events are dependent or independent event.
 Calculate the expected value

Introduction
Probability theory is a mathematical modeling of the phenomenon of chance or
randomness. If a coin is tossed in a random manner, it can land heads (�) or tails
(�),with equally likely. Each of them, � or � is an outcome of the experiment to
tossing the coin. The set {�, �} of the possible outcomes of the experiment is the
sample space of the experiment. A probabilistic mathematical model of random
phenomena is defined by assigning “probabilities” to all the possible outcomes of an
experiment. The reliability of our mathematical model for a given experiment
depends upon the closeness of the assigned probabilities to the actual limiting relative
frequencies.
In this chapter the basic concepts of probability theory are presented. We see the
definition of important terms that are used to solve the probability of a given
experiments. In section 3.1 we will study experiments with finitely many out comes
that are not necessary equally likely. From section 3.2 to 3.4 we introduce some
probability concepts in probability theory, including conditional probability and
independence of events. Finally we discussed the concept of the random variable and
the expectation and variance of a random variable.

3.1 Sample space and events

Objective: After study this section the student should be able to:
 Define the terms; random experiment, sample space and events
 Find the sample space of an experiment
 Find the events of an experiment

By: Wakuma MK kumsa (MSc.) Page 26

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Definition 3.1:
A) Random experiments:
An experiment is a procedure that yields one of a given set of possible outcomes. An
experiment is called a random experiment if its outcome cannot be predicted.
Typical experiments of a random experiment are the roll of a die, the toss of a coin or
drawing a card from a deck.
B) Sample space
The set � of all possible outcomes of a given experiment is called the sample space or
universal set (� is the notation for a sample space and assumes that � is non- empty).
A particular outcome, i.e., an element in S, is called a sample point. Each outcome of
a random experiment corresponding to a sample point.
Example 3.1 Find the sample space for the experiment of tossing a coin (a) one and (b)
twice
Solution: a) There are two possible outcomes, head or tails, thus
� = {�, �}
b) There are four possible outcomes. They are pairs of heads and tails.
Thus,
� = {��, ��, ��, ��}
Example 3.2: Find the sample space for the experiment of tossing a coin repeatedly and
of counting the number of tosses required until the first head appears.
Solution: Clearly all possible outcomes for this experiment are the terms of the sequence
1,2,3 …. Thus
� = {1,2,3, … }
Note that there are infinite number of outcomes (i.e. the sample space is infinite).
Example 3.3: Find the sample space for the experiment of toss a (six sided) die.
The sample consists of the six possible numbers, that is
� = {1,2,3,4,5,6} .
Note that: Any particular experiment can be often having many different sample spaces
depending on the observation of interest.
A sample space � is said to be discrete if it consists of a finite number of sample point
(as in example 3.1 and 3.3) or countable infinite sample point (as in example 3.2)

By: Wakuma MK kumsa (MSc.) Page 27

 Discrete Mathematics And Combinatorics (Math 2052) 2016

C) Event
Since we have identified a sample space � as the set of all possible outcomes of random
experiments, we will review some set notation in the following:
 If � is an element of � (or belongs to �), then we write � ∈ �.
 If � is not an element of � (or does not belongs to �) then we write� ∉ �.  A set �
is called a subset of �, denoted by � ⊂ �, if every element of � is also an element
of �.
An event � is a set of outcomes or, in other words, a subset of the sample space �. In
particular, the set {�} consisting of a single sample point � ∈ � is called an elementary
event. Furthermore, the empty set ∅ and � itself are subset of � and so ∅ and � are
also events. Since � is the set of all possible outcomes, it is often called the certain
event and ∅ is sometimes called the impossible event or the null event. An outcome
in � is favorable outcome (or success), an outcome not in � is an unfavorable
outcomes (or failure). Since an event is a set, we can combine events to form new
events using the various set operations:
I. � ∪ � is the event that occurs if and only if � occurs or � occurs (or both).
II. � ∩ � is the event that occurs if and only if � occurs and � occurs.
III. ��, the complement of �, is the event that occurs if and only if � does not occur.
Two events � and � are called mutually exclusive if they are disjoint, that is, if � ∩ �
= ∅. In other words, � and � are mutually exclusive if and only if they cannot occur
simultaneously. Three or more events are mutually exclusive if every two of them are
mutually exclusive.
Example 2.4: Consider the experiment of example 2.2. Let � be the event that the
number of tosses required until the first head appears is even. Let � be the event that
the number of tosses required until the first head appears is odd. Let � be the event
that the number of tosses required until the first head appears is less than 5. Express
events �, � ��� �
A={2,4,6, … } , B={1,3,5, … } , C={1,2,3,4}
EXAMPLE 3.5: Consider the experiment of toss a coin three times. Let be the event of
obtaining exactly two heads, let be that of obtaining at least two heads and
that of obtaining four heads. Express events and

By: Wakuma MK kumsa (MSc.) Page 28

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Solution: By the multiplication principle, the sample space S consists of 2�2�2 = 8

possible outcome: see figure 3.1
The sample space consists of the following eight elements:

H �
H T HHT
T H HTH
T
� T
T � � ���
H TTH
T
T TTT
Figure 3.1
and an impossible event.
Then
Example 3.6: Tossing a (six-sided) die. The sample space consists of the six
possible numbers, that is, . Let be the event that an even
number appears, that an odd number appears, and that a prime number appears.
That is, let

Then:
is the event that an even or a prime number occurs.
is the event that an odd prime number occurs.
is the event that a prime number does not occur.
Note that and are mutually exclusive: . In other words, an even number
and an odd number cannot occur simultaneously.
EXAMPLE 3.7 Consider the experiment toss a pair of dice. Let be the event that
the sum of two numbers is 6, and let be the event that the largest of the two number
is 4. Express the event and
Solution: There are six possible numbers, , on each die. Thus consists of
the pairs of numbers from 1 to 6, and hence . Figure 2.2 shows these 36

By: Wakuma MK kumsa (MSc.) Page 29

 Discrete Mathematics And Combinatorics (Math 2052) 2016

pairs of numbers arranged in an array where the rows are labeled by the first die and
the columns by the second die.

.
Then the event “ and ” consists of those pairs of integers whose sum is and whose
largest number is 4 or,in other words, the intersection of and .
Thus

Similarly, “ or ,” the sum is 6 or the largest is 4, shaded in Fig. 3.2, is the union A

1 2 3 4 5 6
1 (1,1) (1,2) (1,3) (1,4) (1,5) (1,6)
2 (2,1) (2,2) (2,3) (2,4) (2,5) (2,6)
3 (3,1) (3,2) (3,3) (3,4) (3,5) (3,6)
4 (4,1) (4,2) (4,3) (4,4) (4,5) (4,6)
5 (5,1) (5,2) (5,3) (5,4) (5,5) (5,6)
6 (6,1) (6,2) (6,3) (6,4) (6,5) (6,6)

Figure 3.2
Exercise 3.1
1. Consider a random experiment of tossing a coin three times.
a. Find the sample space , if we wish to observe the number of heads and
tails obtained.
b. Find the sample space , if we wish to observe the number of heads in the
three tosses.

2. Consider an experiment of drawing two cards at random from a bag containing

four cards marked with the integer 1 through 4.

a) Find the sample space of the experiment if the first card is replaced
before the second is drawn.
b) Find the sample space of the experiment if the first card is not replaced.
4. Consider the experiment of selecting items from a group consisting of three
.

By: Wakuma MK kumsa (MSc.) Page 30

 Discrete Mathematics And Combinatorics (Math 2052) 2016

a) Find the sample space of the experiment in which two items are selected
without replacement.
b) Find the sample space of the experiment in which two items are selected
with replacement.
5. Find the sample space for experiment consisting of measurement of the voltage
from a transducer, the maximum and minimum of which are and volts,
respectively.
6. An experiment consists of tossing two dice.
a) Find the sample space
b) Find the event that the sum of the dotes on the dice is greater than
c) Find the event that the sum of the dotes on the dice is greater than
d) Find the event that the sum of the dotes on the dice is greater than

3.2 Probability of an event

Objective: After study this section the student should be able to:
 Define the probability of an event
 Explain the property of probability
 Calculate the probability of events
Definition 3.2: Let be a finite sample space, say . A finite
probability space, or probability model, is obtained by assigning to each point in S a
real number called the probability of satisfying the following properties: I. Each
is nonnegative, that is, ≥ 0.
The sum of the is 1, that is, is + +・ ・ ・+ =1
The probability of an event written , is then defined to be the sum of the
probabilities of the points in . The singleton set { } is called an elementary event
and, for notational convenience, we write P( ) for P({ }).

Definition 3.3: Let be an event of a finite sample space consisting of equally likely out
comes. Then the probability of the event, defined as

By: Wakuma MK kumsa (MSc.) Page 31

 Discrete Mathematics And Combinatorics (Math 2052) 2016

EXAMPLE 3.8: Suppose three coins are tossed, and the number of heads is recorded.
Let be the event that at least one head appears, and let B be the event that all heads
or tails appears. Find the probability of event and .
Solution: The sample space is . The probability of the elements of .

P
That is, each probability is nonnegative, and the sum of the probabilities is 1.
.

Then, by definition, and

Example 3.9: Let a card be selected from an ordinary deck of 52 playing cards. Let
A = {the card is a spade} and B = {the card is a face card}.
What is P(A), P(B), and P(A ∩ B).

Solution: Using definition 2.3,

Example 3.10 An urn contains four blue ball and five red ball. What is the probability that
a ball chosen from the urn is blue?
Solution: Calculate the probability, note that there are nine possible outcomes, and
four of these possible outcomes produce a blue ball, hence, the probability that a blue
is chosen is.

Elementary properties of probability:

Let be the sample space and be an event in . Then the probability function
defined on the class of all events in a finite probability space has the following
properties:
1. For every event .
2. P(S) = 1.
3.
4. �(∅) = 0
5. �(� ∪ �) = �(�) + �(�) − �(� ∩ �)

By: Wakuma MK kumsa (MSc.) Page 32

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Example 3.11: Find the probability of obtaining at least one head when three coins are
tossed.
Solution: Let A be the event of obtaining at least one head. Then Ac denotes the event of

obtaining no heads occur, , therefore ,

Let E = {a1, a2, a3, … , an} be an event of a finite sample space consisting of not
necessary equally likely out comes. Let p(ai) denote the probability that the outcome
ai will occur. Then the probability of E is defined by . Thus p(E) is
the sum of the probabilities of the outcomes in E.
Example 3.12: Suppose the probability of obtaining a prime number is twice that of
obtaining a non- prime number, when a certain loaded die is rolled. Find the
probability of obtaining an odd number when it is rolled.
Solution: There are six possible out comes when a die is rolled, of which there are
primes:2,3 and 5. The probability of obtaining a prime is twice that of a non-prime;
that is �(�����) = 2�(��� − �����). Since the sum of the probabilities of the
various possible outcome is 1. 3�(�����) + 3�(��� − �����) = 1
6�(��� − �����) + 3�(��� − �����) = 1
9�(��� − �����) = 1

Thus, .
Then, .

Definition 3.4: Suppose that � is a set with � elements. The uniform distribution

assigns the probability to each elements of �. The experiment of selecting an

element from a sample space with a uniform distribution is called selecting an
element of � at random.
We now define the probability of an event as the sum of the probabilities of the outcomes in
this event.
Definition 3.5: The probability of the event E is the sum of the probabilities of the outcomes
in E. that is, �(�) = ∑�∈� �(�)

By: Wakuma MK kumsa (MSc.) Page 33

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Example 3.13: Suppose that a die is biased (or loaded) so that 3 appears twice as
often as each other number but that the other five outcomes are equally likely. What is
the probability that an odd number appears when we roll is this die?
Solution: We want to find the probability of the event,{1,2,3,4,5,6} , � = {1,3,5} and
given that
�(3) = 2�(1) = 2�(2) = 2�(4) = 2�(5) = 2�(6)

�(�1) + �(�2) + �(�3) + �(�4) + �(�5) + �(�6) = 1

�(1) + �(2) + �(3) + �(4) + �(5) + �(6) = 1

It follows that .
1
Suppose that there are � equally likely outcomes; each possible outcome has probability � ,

since the sum of their probability is 1. Suppose the event E contains m out comes. According to

definition 3.5

. Since |�| = � ��� |�| = �, it follows that

Theorem 3.1 (Inclusion- exclusion principle). If A and B are any two events of a finite
sample space, S. The probability that at least one of them will occurs is given by
�(� ∪ �) = �(�) + �(�) − �(� ∩ �)
Proof: By the inclusion –exclusion principle on a set,
|� ∪ �| = |�| + |�| − |� ∩ �|
Then .

That �(� ∪ �) = �(�) + �(�) − �(� ∩ �).

In particular, if � and � are mutually exclusive � ∩ � = ∅ and hence
�(� ∩ �) = 0.
Therefore,

By: Wakuma MK kumsa (MSc.) Page 34

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Theorem 3.2: (Addition Principle): If and are mutually exclusive events of a finite
sample space. Then .
EXAMPLE 3.14: Suppose a student is selected at random from 100 students where
30 are taking mathematics,20 are taking chemistry, and 10 are taking mathematics and
chemistry. Find the probability p that the student is taking mathematics or chemistry.
Solution: Let M = {students taking mathematics} and C = {students taking
chemistry}.

Thus, by the Addition Principle (Theorem 2.2),

Example 3.15 A survey among 50 house wives about the two laundry detergent
Lex(L) and Rex(R), shows that 25 like Lex, 30 like Rex, 10 like both, and 5 like
neither. A house wives is selected at random from the group surveyed. Find the
probability that she likes neither Lex nor Rex.
Solution: Using the Venn diagram in figure 3.2, we have
,

So,

Exercise 3.2
1. A card is drawn at random from a standard deck of cards. Find the probability
of obtaining
a) A king c) A king or a queen
b) A club d) A club or a diamond
2. What probability should be assigned to the out come of heads when a biased
coin is tossed, if heads is three times as likely to come up as tail. What
probability should be assigned to the outcome of tails?
3. Two dice are rolled. Find the probability of obtaining

By: Wakuma MK kumsa (MSc.) Page 35

 Discrete Mathematics And Combinatorics (Math 2052) 2016

a) Two five c) A five and a six

b) A sum of four d) A sum less than five
4. Two cards are drawn at random from a standard deck of card. Find the
probability that:
a) Both are king d) One is a king and the other a queen
b) Both are club
c) One is a club and the other a diamond.
5. Let be the sample space of an experiment, where the
outcomes are equally likely. Find the probability of each event
a) c)
b) d)
6. Let and . show that
7. A random experiment has sample space . Suppose that
and .Find the probability of the elementary events.
8. Let be three events in S

9. find
10. Consider a telegraph source generating two symbols, dots and dashes. We
observe that the dots were twice a likely to occur as the dashes. Find the
probability of dot’s occurring and the dash’s occurring.
11. The sample space of a random experiment is given by with
probability . let denote
the event , and .determine the following probabilities:
(a) ;
(b) P(A)
(c)
(d) and (e)

By: Wakuma MK kumsa (MSc.) Page 36

 Discrete Mathematics And Combinatorics (Math 2052) 2016

3.3. Conditional probability

objective: After study this section the student should be able to:
 Define conditional probability
 Calculate the conditional probability of an event
Suppose � be the event of rolling a sum of seven with two dice. Then
. Suppose a 3 comes up on one of the dice. This reduces the sample space to
{(1,3), (2,3), (3,1), (3,2), (3,3), (3,4), (3,5), (3,6), (4,3), (5,3), (6,3)}
consequently, a sum of 7 can be obtained in two ways: {(3,4), (4,3)}. Therefore, the

probability of getting a sum of seven, knowing that a three has been rolled is . Thus
the additional information has indeed affected the probability of �.
Accordingly, we make the following definition
Definition 3.6: The probability that an event � will occur, knowing that a certain
other event � (≠ ∅) has already occurred, is the conditional probability of �, given �,
denoted by �(�\�). And defined as

Suppose � is a sample space, and �(�) denotes the number of elements in �. Then

, and so on
EXAMPLE 3.16; (a) A pair of fair dice is tossed. The sample space � consists of the
36 ordered pairs (�, �), where � and � can be any of the integers from 1 to 6.(see

example 3.6 )Thus the probability of any point is . Find the probability that
one of the dice is 2 if the sum is 6.
Solution: Let � = {��� �� 6} and � = {2 ������� �� �� ����� ��� ���}
Now � consists of 5 elements and � ∩ � consists of two elements; namely
� = {(1, 5), (2, 4), (3, 3), (4, 2), (5, 1)} and � ∩ � = {(2, 4), (4, 2)}

By definition 3.6 .
On the other hand � itself consists of 11 elements, that is,
� = {(2, 1), (2, 2), (2, 3), (2, 4), (2, 5), (2, 6), (1, 2), (3, 2), (4, 2), (5, 2), (6, 2)}
Since � consists of 36 elements, �(�) = 11/36.

By: Wakuma MK kumsa (MSc.) Page 37

 Discrete Mathematics And Combinatorics (Math 2052) 2016

(b) A couple has two children; the sample space is � = {��, ��, ��, ��} with

probability for each point. Find the probability � that both children are boys if it is
known that:
�) �� least one of the children is a boy;
(��) the older child is a boy.
Solution: Let � be the set contain both children are boy, � = {��}
�) Here the reduced space consists of three elements, � = {bb, bg, gb}; then
�(�∩�) 1
� = �(�\�) = �(�)
=3

��) Here the reduced space consists of only two elements � = {bb, bg};
�(�∩�) 1
Then � = �(�\�) = �(�)
=2

Example 3.17: A bit strength of length four is generated at random, so that each of the
16 bit strings of length four is equally likely. What is the probability that it contains at
least two consecutive 0’s, given that its bit is a 0? (We assume that 0 bit
and 1 bit are equally likely)
Solution: Let � be the event that a bit strings of length four contains at least two
consecutive 0�, and � be the event that the first bit of a bit string of length four is a 0.
The probability that a bit string of length four has at least two consecutive 0s, given
�(�∩�)
that its first bit is a 0. Equals �(�\�) = �(�) .
Since � ∩ � = {0000,0010,0011,0100} (See figure 3.3) .We see that

. Since there are eight bit strings of length four that start with 0, we

have

By: Wakuma MK kumsa (MSc.) Page 38

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Theorem 3.3 (Multiplication Theorem for Conditional Probability):

Let � and � be any two events of a finite sample space. Then the probability that both �
and � will occure is given by :
P(A ∩ B) = P(A)P (B\A) = �(�)�(�\�)
From theorem 3.3 we can obtain the following Baye’s rule:

The multiplication theorem gives us a formula for the probability that events � and � both
occur. It can easily be extended to three or more eventsA1, A2, . . . Am; that is,

�(A1 ∩ A2 ∩ . . .∩ Am) = �(A1) ・ �(A2\A1) ・ ・ ・ �(Am\A1, A2, . . . Am−1)

EXAMPLE 3.17 A lot contains 12 items of which 4 are defective. Three items are
drawn at random from the lot one after the other. Find the probability p that all three
are non-defective.

Solution: The probability that the first item is non-defective is since 8 of 12 items
are non-defective. If the first item is non-defective, then the probability that the next

item is non-defective is since only 7 of the remaining 11 items are non-defective.

If the first 2 items are non-defective, then the probability that the last item is

nondefective is since only 6 of the remaining 10 items are now non-defective.

Thus by the multiplication theorem,

Example 3.18: Two marbles are drawn successively from a box of three black and
four white marbles. Find the probability that both are black if the first marble is not
replaced before the second drawing.

Solution: Let �1 be the event drawing the first black marble, then and
let �2 be the event of drawing a second black marble. Since the first marble is not
replaced before the second is drawn, there are only two black balls left in the box at

the second drawing. Therefore, . Consequently, the probability of

drawing two black balls successively without replacement is given by

By: Wakuma MK kumsa (MSc.) Page 39

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Exercise 3.3
1. What is the conditional probability that a family with two children has two
boys, given they have at least one boy.
2. Find �(�\�) if a) � ∩ � = ∅, b) � ⊂ � and c) � ⊂ �
3. Two manufacturing plants produce similar parts. Plant 1 produces 1000 parts,
100 of which are defective. Plant 2 produce 2000 parts, 150 of which are
defective. A part is selected at random and found be defective. What is the
probability that it came from plant 1?
4. Two cards are drawn at random from a deck. Find the probability that both are
aces.

3.4 Independent events

Objective: After study this section the student should be able to:
 Define the independent event
 Differentiate the dependant and independent events  Identify
whether the given events are dependant or not  Calculate the
probability of dependant events.
Definition 3. 6: Two events are dependent if the occurrence of one event affects the
probability of the other event occurring; otherwise, they are independent which
means , events � and � in a probability space � are said to be independent if the
occurrence of one of them does not influence the occurrence of the other. More
specifically, � is independent of � if �(�) is the same as �(�|�).
Now substituting �(�) for �(�|�) in the Multiplication Theorem,
�(� ∩ �) = �(�)� (�|�) yields �(� ∩ �) = �(�)� (�).
We formally use the above equation as our definition of independence.
Definition 2.7: The event A and B are independent if and only if
�(� ∩ �) = �(�)�(�)
Example 3.19: Suppose A is the event that a randomly generated bit string of length
four begins with 1 and B is the event that this bit string contains an even number of
ones. Are A and B independent, if the 16 bit strings of length four are equally likely?
Solution: There are eight bit strings of length four that begin with a one:
1000,1001,1010,1011,1101,1100,1110 ��� 1111

By: Wakuma MK kumsa (MSc.) Page 40

 Discrete Mathematics And Combinatorics (Math 2052) 2016

There are also eight bit strings of length four that contain an even number of ones:
.

Since there are 16 bit strings of length four, it follows that .

Because , we see that . Since

. We conclude that and are independent.

Example 3.20: A fire coin is tossed three times. Consider the events:

Show that and are independent. Solution: The sample space is

and the events are:

And
We have:

Accordingly,

, and so and are independent

, and so and are independent

, and so and are dependent

Example 3.21: Are the event , that a family with three children has children of both sexes,
and that a family with three children has at most one boy,
independent? Assume that the eight ways a family can have three children are equally likely.
Solution: By assumption, each of the eight ways a family can have three children.
, Where G represents girl and B

represents boy, has a probability . Since

and
� ∩ � = {���, ���, ���}

It follows that . Since

. We conclude that � and � are independent.

By: Wakuma MK kumsa (MSc.) Page 41

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Exercise 3.4
1. Consider the experiment of throwing two fair dice. Let A be the event that the sum
of the dice is 7, let B be the event that the sum of the dice is 6, and C be the event that
the first die is 4. Show that events A and C are independent, but event B and C are not
independent.
2. Suppose we draw a card from a standard deck of 52 cards, replace it, draw
another card, and continue for a total of ten draws. Is this an independent trials
process?
3. Suppose we draw a card from a standard deck of 52 cards, discard it (i.e. we do
not replace it), draw another card and continue for a total of ten draws. Is this an
independent trials process?
4. In three flips of a coin, is the event that we have at most one tail independent of
the event that not all flips are identical?

3.5 Random variable and expectation

Objective: After study this section the student should be able to:
 Define a random variable
 Calculate the expected value

A random variable for an experiment with a sample space � is a function that assigns
a number to each element of �. Typically instead of using � to stand for such a
function we use � (at first, a random variable was conceived of as a variable related to
an experiment, explaining the use of �, but it is very helpful in understanding the
mathematics to realize it actually is a function on the sample space).
For example, if we consider the process of tossing a coin � times, we have the set of
all sequences of � �� and �s as our sample space. The “number of heads” random
variable takes a sequence and tells us how many heads are in that sequence.
Somebody might say “Let � be the number of heads in tossing a coin 5 times.” In that
case �(�����) = 3 while X(THTHT) = 2. It may be rather jarring to see � used to
stand for a function, but it is the notation most people use.

By: Wakuma MK kumsa (MSc.) Page 42

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Definition 3.7
Consider a random experiment with sample space �. A random variable �(�) is a
single-valued real function that assigns a real number called the value of �(�) to each
sample point � of �.
Note: A random variable is not a variable at all in the usual sense, and it is a function.
The sample space � is termed the domain of the random variable �(�) , and the
collection of all numbers (values of �(�)) is termed the range of the random variable.
Thus the range of �(�) is a certain subset of the set of all real numbers (figure 2.4)

Fig.3.5 One random variable associated with coin tossed

Note that we could also define another random variable, say Y or Z, with
�(�) = 0, �(�) = 1 �� �(�) = 0, �(�) = 1
These events have probabilities that are denoted by
�(� = �) = �(�: �(�) = �)
�(� ≤ �) = �(�: �(�) ≤ �)
�(� > �) = �(�: �(�) > �)
�(�1 < � ≤ �2) = �(�: �1 < � ≤ �2)
EXAMPLE 3.23 In the experiment of tossing a fair coin three times, the sample
space �1 consists of eight equally likely sample points �1 = (���, . . . , ���). If � is
the random variable giving the number of heads obtained, find

By: Wakuma MK kumsa (MSc.) Page 43

 Discrete Mathematics And Combinatorics (Math 2052) 2016

(a)
(b)

Solution:
(a) Let be the event defined by . Then, we have
τ τ
Since the sample points are equally likely, we have

(b) Let be the event defined by . Then

and

Probability Distribution of a Random Variable

Let be a random variable on a finite sample space with range space
Then induces a function which assigns probabilities to the
points in as follows:

.
The set of ordered pairs is called the
distribution of the random variable ; it is usually given by a table as in Fig. 3.6. This
function has the following two properties:
(i) and
Thus with the above assignments of probabilities is a probability space.
(Sometimes we will use the pair notation to denote the distribution of instead
of the functional notation .
Out come . . .
Probability . . .

Fig. 3.6 Distribution of a random variable

In the case that is an a equiprobable (uniform distribution) space, we can easily obtain the
distribution of a random variable from the following result.
Theorem 3.4: Let be an equiprobable space, and let be the distribution of a random
variable on with the range space .

Then

By: Wakuma MK kumsa (MSc.) Page 44

 Discrete Mathematics And Combinatorics (Math 2052) 2016

EXAMPLE 3.24: A pair of dice is tossed. Let be assign to each point in the sum of
the numbers: is a random variable with range space

Note , and .
Using Theorem 3.4, we obtain the distribution of as follows:
, since there is one outcome, whose sum is 2.
, Since there are two outcomes, ) and , whose sum is 3.
, since there are three outcomes, and ,whose sum is 4.
Similarly, .
Thus the distribution of as follows.
2 3 4 5 6 7 8 9 10 11 12

Expected value:
The expected value of a random variable is the sum over all elements in a sample
space of the product of the probability of the element and the value of the random
variable at this element.
Definition 3.8 The expected value (or expectation) of the random variable on the
sample space Sis equal to
.
Note that when the sample space has n elements

Remark: We are concerned only with random variables with finite expected values here.
Example 3.25 A fair coin is tossed six times. Let be the sample space of the 64
possible outcomes, and let be the random variable that assigns to an outcome the
number of heads in this outcome. What is the expected value of ?

Solution: The number of heads which can occur with their respective probabilities follows:
�� 0 1 2 3 4 5 6
�� 1⁄64 6⁄64 15⁄64 20⁄64 15⁄64 6⁄64 1⁄64

Then the mean or expectation (or expected number of heads) is:

By: Wakuma MK kumsa (MSc.) Page 45

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Example 3.26 Three horses �, � and � are in a race, suppose their respective probabilities of

winning are . Let � denote the pay of a function for the

winning horse, and suppose � pay $2, $6 �� $9 according as �, � �� � wins the race.
What is the expected value of ?
Solution: Expected value of � is
�(�) = �(�)�(�) + �(�)�(�) + �(�)�(�)

Theorem 3.5: If � is a random variable and �(� = �) is the probability that

� = �, so that �(� = �) = ∑�∈�,�(�)=� �(�), then �(�) = ∑�∈�(�) �(� = �) Proof:

suppose that � is a random variable with range �(�) , and let �(� = �) be the
probability that the random variable � takes the value r. consequently,
�(� = �) is the sum of the probabilities of the outcomes s such that �(�) = �. it follows that
�(�) = ∑�∈�((�) �(� = �)�
Example 3.27 What is the expected value of the sum of the numbers that appear when a
pair of a fair dice?
Solution: Let X be the random variable equal to the sum of the numbers that appear
when a pair of dice is rolled. In example 2.25 we listed the value of X for the 36
possible outcomes. The range of X is {2,3,4,5,6,7,8,9,10,11,12}
Substitute the value in example 2.25 in the formula, we have
�(�) = 2�(� = 2) + 3�(� = 3) + 4�(� = 4) + 5�(� = 5) + 6�(� = 6)7�(� =
7) + 8�(� = 8) + 9�(� = 9) + 10�(� = 10) + 11�(� = 11) + 12�(� = 12)

Theorem 3.5: The expected number of successes when n Bernoulli trials are performed, where
the probability of success on each trial is .
Exercise 3.5
1. A random sample with replacement of size is drawn from the set
, yielding the following 9-element equiprobable sample space

By: Wakuma MK kumsa (MSc.) Page 46

 Discrete Mathematics And Combinatorics (Math 2052) 2016

a) Let denote the sum of the two numbers. Find the distribution of , and
find the expected value .
b) Let denote the minimum of the two numbers. Find the distribution of
,and find the expected value
2. A coin is weighted so that and . The coin is tossed
three times. Let denote the number of heads that appear
a) Find the distribution of of
b) Find the expected
3. A player tossed three fair coins. He wins if three heads occur, if two
heads occur, and if only one head occurs. On the other hand, he losses
if three tails occur. Find the value of the game to the player.
4. What is the expected sum of the tops of n dice when we roll them?

Chapter summary:
 An experiment is a procedure that yields one of a given set of possible outcome.
 A sample space is the set of all possible outcomes of a given experiment,denoted by .

 An event is a set of outcome.

 Two events and are called mutually exclusive if they are disjoint, i.e. .
 Let be an event of a finite sample space consisting of equally likely outcomes. Then

 Suppose that is a set with n elements. The uniform distribution assigns the probability to
each elements of .
 If and are any two events, then
(Inclusion exclusion principle)
 If A and B are mutually exclusive events, then (addition principle).
 The conditional probability of given , denoted by , defined as

.
 The conditional probability of B given A, denoted by ,defined as

.
 Two events are dependent if the occurrence of one event affects the probability of the event
occurring.
 The event and are independent if and only if

By: Wakuma MK kumsa (MSc.) Page 47

 Discrete Mathematics And Combinatorics (Math 2052) 2016

 A random variable for an experiment with a sample space is a function that assigns a number
to each element of .
 Consider a random experiment with sample space . A random variable is a single-valued
real function that assigns a real number called the value of to each sample point of .
 The expected value (or expectation) of the random variable on the sample space
S is equal to .

Self Test Exercise 3

1. A sample space S consists of four elements: that is . under
which of the following function does S become a probability space a)

b)

c)

d)
2. A coin is weighted so that head is three times as likely to appear as tails. Find
and
3. Suppose and are events with , and
. Find the probability that
a) does not occur
b) does not occur
c) or occur
d)
4. A fair die is tossed. Consider events .
Find
a) and and or
b) and
c) and
d) and
5. A pair of fair dice is tossed. If the numbers appearing are different. Find the
probability that

By: Wakuma MK kumsa (MSc.) Page 48

 Discrete Mathematics And Combinatorics (Math 2052) 2016

a) The sum is even

b) The sum exceeds nine
6. Two dice are rolled. Find the probability of obtaining each event
a) A sum of 11, knowing that a six has occurred on one dies.
b) A sum of 11, knowing that one die shows an odd number.
7. The Sealords have three children. Assuming that the outcomes are equally likely
and independent, find the probability that they have three boys, knowing that: a)
The first child is a boy c) at least one child is a boy
b) The first two children are boys. d) the second child is a boy

Reference:
1. A. W.F.Edwards,Pascal’s Arithmeticical Triangle. The Johns Hopkins University Press,
Baltimore,MD, 2002.
2. C.Oliver, “ The Twelve Days of Christmas,” Mathematics Teacher, Vol. 70

3. David A.Santos, Discrete Mathematics Note

4. Discrete Mathematics, Handbook of discrete and Compinatorial Mathematics

5. Hewel Hus, Schaum’s outline, probability Random Variable

6. J.M.Harris.Jeffry L.Hirst.Michael J.Mossinghoff, Combinatorics and Graph Theory,
2nd edition

7. J.Varnadore, “ Pascal’s Triangle and Fibonacci Numbers,” Mathematics Teacher, Vol,81.

8. Ken Bogart and Cliffstein, Discrete math in computer science

9. Kenneth H.Rosen, Discrete Mathematics and its application, 3rd edition.
10. M.Eng and J.Casey, “Pascal’s Arithmetical Triangle-ASerendipitious Source for
programming Activities,’’ Mathematics Teacher, Vol 76

By: Wakuma MK kumsa (MSc.) Page 49

 Discrete Mathematics And Combinatorics (Math 2052) 2016

CHAPTER 4: RECURRENCE RELATION

Objectives:- On completion of the chapter the students will be able to:
 Define recurrence relation.
 Solve linear homogeneous recurrence relation with constant coefficient.
 Solve linear nonhomogeneous recurrence relation with constant coefficient.

4.1 Introduction
Many counting problems cannot be solved easily using the methods discussed in
chapter 1. One such problem is: how many bit strings of length do not contain
two consecutive zeros? To solve this problem let be the number of such strings of
length . An argument can be given that shows . This equation,
called recurrence relation, and the initial conditions and determine the
sequence . Moreover the explicate formula can be found for from the
equation relating the terms of the sequence. As we will see, a similar technique can be
found to solve many different types of counting problems.
Definition 4.1: A recurrence relation for a sequence is an equation that
expresses in terms of one or more preceding terms . Moreover,
the sequence is called the solution to the recurrence relation if it satisfies the recurrence
relation.
The following are examples of recurrence relations :

For (1) we would need one initial value to find a particular or single . For example, if
then and .
For (2) we would need two initial values to find a particular or single . For example, if
and then and .
Example 4.1 Verify that the solution of the recurrence relation
with is
Solution: We have to do two things
(a) Check that the given formula gives the correct initial value
(b) Check that the given formula solves the recurrence relation.
Putting in gives as required.

By: Wakuma MK kumsa (MSc.) Page 50

 Discrete Mathematics And Combinatorics (Math 2052) 2016

To do (b) we evaluate using the given formula and show that it is equal to
.
Now so

Recurrence relations have many applications. Suppose that you put £100 into a savings
account yielding 4% compounded annually. Let be the amount (in pounds) in the
account after years. Then is equal to the amount in the account after years
plus the interest for the th year. For example, is equal to 100 plus the interest which
is 4. Hence .
In general,
so that
, with
.
Solving this we obtain

and in general

Exercises 4.1
1. Let with = 1 and = 1 . Find and .
2. Verify that the solution of the recurrence relation with is
.
3. Verify that the solution of with is .

4.2 Linear recurrence relation with constant coefficient

Objectives:- On completion of this section the students will be able to:
Define a linear recurrence relation with constant coefficient of degree
A wide variety of recurrence relations occur in models. Some of those recurrence
relations can be solved using iteration or some other technique. However, one
important class of recurrence relation can be explicitly solved in a systematic way.
These are recurrence relations that express the terms of the sequence as linear
combination of previous terms.

By: Wakuma MK kumsa (MSc.) Page 51

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Definition 4.2: A linear recurrence relation with constant coefficient of degree (order)
� is a recurrence relation of the form
�� + �1��−1 + �2��−2 + ⋯ + ����−� = �(�) (1)
where �1, �2, … , �� are constants and �� ≠ 0.
If �(�) is identically zero (�(�) = 0) in the recurrence relation (1) defined above, then
the recurrence relation (1) is called homogeneous, otherwise it is called
nonhomogeneous.
Exercise 4.2:
a. �� + 6��−1 = 0 is linear homogeneous recurrence relation with constant coefficient of
degree (order) 1.
b. �� − 5��−1 + 6��−2 = 0 is linear homogeneous recurrence relation with constant
coefficient of degree (order) 2.
c. �� + 4��−1 + 4��−2 = −5�2 + � is linear non-homogeneous recurrence relation with
constant coefficient of degree (order) 2.
d. �� − 5��−1 + 6��−2 − ��−3 = 4� is linear non-homogeneous recurrence relation with
constant coefficient of degree (order) 3.

4.3 Solution of linear recurrence relation with constant coefficient

4.3.1 Solving linear homogeneous recurrence relation with constant

coefficient
Objectives:- On completion of this section the students will be able to:
Solve linear homogeneous recurrence relation with constant coefficient.

The basic approach for solving linear homogeneous recurrence relations is to look for
the solutions of the form �� = ��, where � is constant. Note that �� = �� is the solution
of the recurrence relation
�� + �1��−1 + �2��−2 + ⋯ + ����−� = 0 (2)
if and only if
�� + �1��−1 + �2��−2 + ⋯ + ����−� = 0.

When both side of the equation is divided by ��−� we obtain the equation

�� + �1��−1 + �2��−2 + ⋯ + ��−1� + �� = 0 . (3)

By: Wakuma MK kumsa (MSc.) Page 52

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Consequently the sequence with �� = �� is the solution if and only if � is the

solution of the last equation (3), which is called the characteristic equation of the
recurrence relation (2). The solutions of the characteristic equation (3) are called
characteristic roots of the recurrence relation (2). As we will see, these characteristic
roots can be used to give an explicit formula for all the solutions of the recurrence
relation (2).
Let us first see the rule to find all the possible solutions (general solution)
homogeneous recurrence relation with constant coefficients of degree 1.
All the possible solutions or general solution to the linear homogenous recurrence relation with
constant coefficient of degree 1
�� + ���−1 = 0
is �� = �(−�)� , where � is a constant.
Example 4.2. Find the solution of the recurrence relation
�� − 5��−1 = 0
with initial condition �0 = 7
Solution. The general solution is �� = �(5�) .
Since �0 = 7,

⟹ �0 = �(50) = 7
Thus,
� = 7 and hence the solution is �� = 7(5�) .
Now we will develop rules that deal with linear homogeneous recurrence relation with
constant coefficients of degree 2. Then corresponding general rules when the degree
may be greater that two will be stated. Because the proofs needed to establish the
general rules in general case are more complicated. We now turn our attention to linear
recurrence relations of degree two.
Theorem 4.1: Consider a linear homogeneous recurrence relation with constant coefficient of
degree 2
�� + �1��−1 + �2��−2 = 0 (4)
for � ≥ 2, where �1 and �2 are constants, and consider its characteristic equation
�2 + �1� + �2 = 0 . (5)
i. If the characteristic equation (5) has two distinct roots �1 and �2, then the sequence
is the solution of the recurrence relation (4) if and only if

By: Wakuma MK kumsa (MSc.) Page 53

 Discrete Mathematics And Combinatorics (Math 2052) 2016

�� = �1�1� + �2�2� (6)

where �1 and �1 are constants.

ii. If the characteristic equation (5) has only one root �0, then the sequence is
the solution of the recurrence relation (4) if and only if
�� = �1�0� + �2� �0� (7)
where �1 and �1 are constants.
Proof:
i. We must do two things to prove the theorem. First it must be shown that if �1 and �2 are roots
of the characteristic equation, and �1 and �1 are constants, then the sequence
with �� = �1�1� + �2�2� is the solution of the recurrence relation. Second it
must be shown that if the sequence is the solution, then �� = �1�1� + �2�2� for
some constants �1 and �1.
Now we will show that if �� = �1�1� + �2�2� , then the sequence is the

solution of the recurrence relation. Since �1 and �2 are roots of �2 + �1� + �2 = 0, it

follows that �12 = −�1�1 − �2 and �22 = −�1�2 − �2.

From these equations , we see that

−�1��−1 − �2��−2 = −�1(�1(�1�−1) + �2(�2�−1)) − �2(�1(�1�−2) + �2(�2�−2))

= �1(�1�−2)[−�1�1 − �2] + �2(�1�−2)[−�1�2 − �2]

= �1(�1�−2)�12 + �2(�1�−2)�22

= ��
This shows that the sequence {��} with is the solution of the
recurrence relation. To show every solution {��} of the recurrence relation �� +
�1��−1 + �2��−2 = 0 has for � = 0,1,2, … and �1 and �2 are
constants, suppose that {��} is the solution of the recurrence relation, and the initial
conditions �0 = �0 and �1 = �1 hold. It will be shown that there are constants �1 and
�2 so that the sequence {��} with �� = �1�1� + �2�2� satisfies these the same initial conditions.
This requires that
�0 = �0 = �1 + �2

By: Wakuma MK kumsa (MSc.) Page 54

 Discrete Mathematics And Combinatorics (Math 2052) 2016

�1 = �1 = �1�1 + �2�1
We can solve these two equations for �1 and �2. From the first equation it follows that
�2 = �0 − �1. Inserting this equation in to the second equation gives �1 = �1�1 +

(�0 − �1)�2.
Hence,
�1 = �1(�1 − �2) + �0�2
This shows that

and

where these expressions for �1 and �2 depend on the fact that �1 ≠ �2. ( When �1 = �2, this
theorem is not true.)
Hence, with those values for �1 and �2 , the sequence {��} with satisfies the
two initial conditions. Since this recurrence relation and these initial conditions
uniquely determine the sequence, it follows that ii.
Exercise.

Note that: The solution (6) or (7) are all possible solutions of the recurrence relation
(4). And we call the solution general solution of the recurrence relation (4).
Example 4.3. Find the general solution of
�� − ��−1 − 2��−2 = 0 , for � ≥ 2
Solution: The characteristic equation of the given recurrence relation is �2 − � − 2 = 0.
Then, find the roots of the characteristic equation using quadratic formula
(factorization).
�2 − � − 2 = 0
⇒ (� + 1)(� − 2) = 0
So � = −1 and � = 2. Thus, the characteristic equation has two distinct roots � = −1
and � = 2
Hence, the general solution is
�� = �1(−1)� + �2(2)�
where �1 and �2 are constants.

By: Wakuma MK kumsa (MSc.) Page 55

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Example 4.4. Find the solution of

�� = −7��−1 − 12��−2 , for � ≥ 2
with initial condition �1 = 0 and �1 = 5.
Solution: �� = −7��−1 − 12��−2
⇒ �� + 7��−1 + 12��−2 = 0
Thus, the characteristic equation is
�2 + 7� + 12 = 0.
And finding the roots of the characteristic equation using quadratic formula or
factorization, we have � = 3 and = 4 .
Hence, the general solution is
�� = �1(3)� + �2(4)�
where �1 and �2 are constants.
Putting � = 0 and � = 1 in �� = �1(3)� + �2(4)� and using the initial conditions
gives, we have
�1 + �2 = 0 and 3�1 + 4�2 = 5.
Solving these gives �1 = −5 and �2 = 5.
Hence,
�� = −5(3)� + 5(4)� is the solution.
Example 4.5: Find the solution of

, for � ≥ 2
with �0 = 1 and �1 = 10.
Solution: The characteristic equation of the given recurrence relation is

.
Finding the roots of the characteristic equation using quadratic formula

So the characteristic equation has double root .

Hence, the general solution is

where �1 and �2 are constants.

By: Wakuma MK kumsa (MSc.) Page 56

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Putting and using the initial conditions gives, we have

�1 = 1 and .

Solving these gives .

Hence,

is the solution.
We will now state the general result about the solution of linear homogeneous
recurrence relation with constant coefficients of degree �, where the degree � ≥ 2
under the assumption that the characteristic equation has � distinct roots �1, �2, … , �� or
the characteristic equation has t distinct roots �1, �2, … , �� with multiplicity �1, �2, … ,
�� respectively, so that �� ≥ 1, for � = 1,2, … , � and �1 + �2 + ⋯ +

�� = �.
Theorem 3.2: Consider the linear homogeneous recurrence relation with constant
coefficient of degree k k k k k k k k k k k k k k k k k k k k k k k k k k k k k kk k k k k k
�� + �1��−1 + �2��−2 + ⋯ + ����−� = 0 (8)
and consider its characteristic equation I I ik ihh hh hbh hh h h n n n n
�� + �1��−1 + �2��−2 + ⋯ + ��−1� + �� = 0. (9)

i. If the characteristic equation (9) has � distinct roots �1, �2, … , �� , then the sequence
is the solution of the recurrence relation (8) if and only if
(10)
where �1, �2, … , �� are constants.
ii. If the characteristic equation (9) has t distinct roots �1, �2, … , �� with multiplicity
�1, �2, … , �� respectively, so that �� ≥ 1, for � = 1,2, … , � and �1 + �2 + ⋯ + �� = �,
then the sequence is the solution of the recurrence relation (8) if and only if

�� = (�10 + �11� + ⋯ + �1(�1−1)��1−1)�1� + (�20 + �21� + ⋯ +

�2(�2−1)��2−1)�2� + ⋯ + (��0 + ��1� + ⋯ + ��(��−1)���−1)��� (11)

where ��� are constants for 0 ≤ � ≤ � and 0 ≤ � ≤ �� − 1.

By: Wakuma MK kumsa (MSc.) Page 57

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Note that: The solution (10) or (11) are all possible solutions of the recurrence relation (8). And
we call the solution general solution of the recurrence relation (8).

Example 4.6. Find the general solution of the recurrence relation

, for � ≥ 4.
Solution: The characteristic equation the given recurrence relation is

So that with the multiplicity of 2 is 2, the multiplicity of

is 2 and the multiplicity of −5 is 1.
Hence the general solution of the recurrence relation

, for � ≥ 4
is

where �1, �2 , �3 and �4 are constants.

Exercise 4.3.1
1. Solve the recurrence relations together with the initial conditions given.
a. �� − 2��−1 = 0 , fo� � ≥ 1 , �0 = 3

b. �� − 5��−1 + 6��−2 = 0 , for � ≥ 2 , �0 = 1 , �1 = 0 .

c. �� + 8��−1 + 16��−2 = 0 , for � ≥ 2 , �0 = 1 , �1 = 1 .

2. Find the general solution (all solutions) of the recurrence relation
a. �� = 6��−1 , for � ≥ 1 .

b. �� + 10��−1 + 25��−2 = 0 , for � ≥ 2

c. �� − 2��−1 − ��−2 + 2��−3 = 0 , for � ≥ 3

4.3.2. Solving linear nonhomogeneous recurrence relation with constant coefficient

Objectives:- On completion of this section the students will be able to:

Solve linear nonhomogeneous recurrence relation with constant coefficient.

By: Wakuma MK kumsa (MSc.) Page 58

 Discrete Mathematics And Combinatorics (Math 2052) 2016

We have seen how to solve linear homogeneous recurrence relation with constant
coefficients. Is there a relatively simple technique for solving a linear, but not
homogeneous, recurrence relation with constant coefficients, such as �� = 3��−1 +
2� ? We will see that the answer is yes for a certain families of such recurrence relations.
The recurrence relation �� = 3��−1 + 2� is an example of linear nonhomogeneous
recurrence relations with constant coefficients, that is recurrence relation of the
form
�� + �1��−1 + �2��−2 + ⋯ + ����−� = �(�)
where �1, �2, … , �� are constants and �� ≠ 0 and �(�) is a function not identically zero
depending only on �. The recurrence relation
�� + �1��−1 + �2��−2 + ⋯ + ����−� = 0
is called the associated homogenous recurrence relation. It plays an important role in the
solution of the nonhomogeneous recurrence relation.
Theorem 4.3: Consider the linear nonhomogeneous recurrence relations with constant
coefficients of degree �
�� + �1��−1 + �2��−2 + ⋯ + ����−� = �(�) (12)
and its associated homogenous recurrence relation
�� + �1��−1 + �2��−2 + ⋯ + ����−� = 0 (13)

Then every solution of the recurrence relation (12) is of the form , where
is the particular solution of the recurrence relation ( is the solution of the
recurrence relation (13).
Proof: Let be the particular solution of the non homogeneous recurrence relation.
Thus,
. (14)
Now suppose that is any other solution of the nonhomogeneous recurrence relation.
Thus,
. (15)
Subtracting the equation (a) from equation (b)

It follows that is the solution of the associated homogeneous recurrence relation.

By: Wakuma MK kumsa (MSc.) Page 59

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Let . Thus, .

Therefore, every solution of the recurrence relation (12) is of the form ,

where is the particular solution of the recurrence relation (12) and is the solution
of the recurrence relation (13).
Problem: What is the general solution of the linear nonhomogeneous recurrence relation (12)?
The general solution (all solutions) of the linear nonhomogeneous recurrence

relation (12) is the sequence , where is the particular solution of

the linear nonhomogeneous recurrence relation ( is the general solution
of the associated homogenous recurrence relation (13).

Problem: How can we find or choose the particular solution for the linear nonhomogeneous
recurrence relation (12)?
�(�) Choice of ���

���� + ��−1��−1 + ⋯ + �1� + �0 ���� + ��−1��−1 + ⋯ + �1� + �0

�(��) �(��)
(���� + ��−1��−1 + ⋯ + �1� + �0)�� (���� + ��−1��−1 + ⋯ + �1� + �0)��

Rules:
If �(�) is one of the terms on the left side of the table choose the particular solution
��� from the right side of the table and determine the underdetermined coefficients by
using the original equation in (12).
If � is the root of the characteristic equation to the recurrence relation (13) with multiplicity �,
then multiply ��� by ��.
That is if � is the root of the characteristic equation to the recurrence relation (13)
with multiplicity �, choose the particular solution for the case
�(�) = �(��) and choose the particular solution

��� = ��(���� + ��−1��−1 + ⋯ + �1� + �0)��

for the case �(�) = (���� + ��−1��−1 + ⋯ + �1� + �0)��.

Example 4.7. Find a particular solution of the recurrence relation
�� − 4��−1 = − 15 , for � ≥ 1
Solution. The given recurrence relation is of the form �� − 4��−1 = �(�) , where

By: Wakuma MK kumsa (MSc.) Page 60

 Discrete Mathematics And Combinatorics (Math 2052) 2016

�(�) = −15. We choose particular solution , where � is a constant.

Then, we have to find � by substituting in to the given recurrence relation, that is
.
Observe that and . Thus, we have −4� = − 15 .
⟹ −3� = −15 ⟹�=5
Hence, is the particular solution of the recurrence relation.
Example 4.8 . Find a particular solution of the recurrence relation
�� = 6��−1 + 7��−2 + 7� , for � ≥ 2
Solution.
The given recurrence relation is of the form �� − 6��−1 − 7��−2 = �(�) , where
�(�) = 7�. The associated homogeneous recurrence relation to the given recurrence relation
is
�� − 6��−1 − 7��−2 = 0
and its characteristic equation is �2 − 6� − 7 = 0.
Thus,

So � = 7 and � = −1.
�(�) = 7� , and � = 7 is the root of the characteristic equation with multiplicity 1.
Thus we choose particular solution , where � is a constant.
Then, we have to find � by substituting in to the given recurrence relation, that is
.
Observe that .
Thus,
[��(7�)] − 6[�(� − 1)(7�−1)] − 7[�(� − 2)(7�−2)] = 7�
⟹ ��(7�) − 6��7�−1 + 6�7�−1 − 7��7�−2 + 14�7�−2 = 7�

Hence, is the particular solution of the recurrence relation.

Example 4.9 . Find the general solution of the recurrence relation
�� = ��−1 + ��−2 + 5� − 6 , for � ≥ 2

By: Wakuma MK kumsa (MSc.) Page 61

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Solution. �� = ��−1 + ��−2 + 5� − 6

⟹ �� − ��−1 − ��−2 = 5� − 6
⟹ �� − ��−1 − ��−2 = �(�) , where �(�) = 5� − 6
The associated homogeneous recurrence relation to the given recurrence relation is
�� − ��−1 − ��−2 = 0
and its characteristic equation is �2 − � − 1 = 0.
Thus,

1+√5 1−√5
and � =
So � = 2 2 .
Hence, the general solution to the associated homogeneous recurrence relation is

where �1 and �2 are constants.

�(�) = 5� − 6, so we choose the particular solution to the given nonhomogeneous
recurrence relation to be , where �1 and �2 are constants to be determined
by substituting in to the given recurrence relation.
Thus,
.
And and .
Thus,

⟹ (�1� + �2 ) − (�1(� − 1) + �2) − (�1(� − 2) + �2) = �(�)

⟹ �1� + �2 − �1� + �1 − �2 − �1� + 2�1 − �2 = 5� − 6

⟹ −�1� + (�2 + 3�1) = 5� − 6
⟺ −�1 = 5 and �2 + 3�1 = −6
Thus, �1 = −5 and �2 = 9.
Hence, the particular solution to the given nonhomogeneous recurrence relation is
.
Therefore, the general solution to the nonhomogeneous recurrence relation
�� = .
That is the general solution to the nonhomogeneous recurrence relation

By: Wakuma MK kumsa (MSc.) Page 62

 Discrete Mathematics And Combinatorics (Math 2052) 2016

�� = ��−1 + ��−2 + 5� − 6
is

where �1 and �2 are constants.

Example 4.10. Find the solution of the recurrence relation
�� − 6��−1 + 9��−2 = 2(3�) ,
for � ≥ 2 with initial condition �0 = −1 and �1 = 5.
Solution. We are given a recurrence relation
�� − 6��−1 + 9��−2 = �(�), where �(�) = 2(3�).
The associated homogeneous recurrence relation to the given recurrence relation is
�� − 6��−1 + 9��−2 = 0
and its characteristic equation is �2 − 6� + 9 = 0.
Thus, �2 − 6� + 9 = 0
⟹ (� − 3)2 = 0
So the characteristic equation has double root and is � = 3.
Hence, the general solution to the associated homogeneous recurrence relation is

where �1 and �2 are constants.

�(�) = 2(3�), and � = 3 is the root of the characteristic equation and the multiplicity of
3 is 2, so we choose the particular solution to the given nonhomogeneous recurrence
relation to be , where � is constant to be determined by substituting
in to the given recurrence relation.
That is . But,
1)2(3�−1) and .
Thus,

⟹ [��2(3�)] − 6[�(� − 1)2(3�−1)] + 9[�(� − 2)2(3�−2)] = 2(3�)

⟹ ��2(3�) − 6[�(�2 − 2� + 1)(3�−1)] +9[�(�2 − 4� + 4)(3�−2)] = 2(3�)
⟹ ��2(3�) − 6��2(3�−1) + 12��(3�−1) − 6�(3�−1) + 9��2(3�−2) −
36��(3�−2) + 36�(3�−2) = 2(3�)

By: Wakuma MK kumsa (MSc.) Page 63

 Discrete Mathematics And Combinatorics (Math 2052) 2016

⟹ ��2(3�) − 2��2(3�) + 4��(3�) − 2�(3�) + ��2(3�) − 4��(3�) + 4�(3�) =

2(3�)
⟹ 2�3� = 2(3�) ⟺ � = 1
Hence, the particular solution to the given nonhomogeneous recurrence relation is
.
Therefore, the general solution to the nonhomogeneous recurrence relation �� −
.
That is the general solution to the nonhomogeneous recurrence relation
�� − 6��−1 + 9��−2 = 2(3�)
is
�� = �1(3�) + �2�(3�) + �2(3�)
where �1 and �2 are constants.
Then, putting � = 0 and � = 1 in �� = �1(3�) + �2�(3�) + �2(3�) and using the
initial conditions gives,
we have
�1 = −1 and
3�1 + 3�2 + 3 = 5.
That is �1 = −1 and 3�1 + 3�2 = 2.

Solving these gives .

Hence,

is the solution.
Example 4.11. Find the general solution of the recurrence relation
�� + 9��−1 + 20��−2 = (�2 + � − 1 )5� , for � ≥ 2
Solution. We are given a recurrence relation
�� − 10��−1 + 25��−2 = �(�), where �(�) = (�2 + � − 1 )5�.
The associated homogeneous recurrence relation to the given recurrence relation is
�� − 10��−1 + 25��−2 = 0
and its characteristic equation is �2 − 10� + 25 = 0.
Thus, �2 − 10� + 25 = 0

By: Wakuma MK kumsa (MSc.) Page 64

 Discrete Mathematics And Combinatorics (Math 2052) 2016

⟹ (� − 5)2 = 0
So the characteristic equation has double roots and is � = 5.
Hence, the general solution to the associated homogeneous recurrence relation is
where �1 and �2 are constants.
�(�) = (�2 + � − 1 )5�, and � = 5 is the root of the characteristic equation and the
multiplicity of 5 is 2, so we choose the particular solution to the given
nonhomogeneous recurrence relation to be , where
�2 , �1 and �0 are constants to be determined by substituting in to the given recurrence
relation.

That is .
But,
�0 )5�−1 and .
Thus,

⟹ [�2(�2�2 + �1� + �0 )5�] − 10[(� − 1)2(�2(� − 1)2 + �1(� − 1) + �0 )5�−1] +

25[(� − 2)2(�2(� − 2)2 + �1(� − 2) + �0 )5�−2] = (�2 + � − 1 )5�

The rest of the steps of the solution are left as an exercise.
Example 4.12. Find the general solution of the recurrence relation
�� − ��−1 − 10��−2 + 8��−3 = �(�) , for � ≥ 3
where a. �(�) = 6� b. �(�) = (−1)�(4)�
Solution. The associated homogeneous recurrence relation to the given recurrence
relation is
�� − ��−1 − 10��−2 + 8��−3 = 0 , for � ≥ 3
and its characteristic equation is �3 − �2 − 10� + 8 = 0.
Thus
�3 − �2 − 10� + 8 = 0
⟹ (� − 1)(� − 2)(� + 4) = 0
⟺ � = 1 , � = 2 , � = −4
So the characteristic equation three distinct root � = 1 , � = 2 and � = −4.
Hence, the general solution to the associated homogeneous recurrence relation is

By: Wakuma MK kumsa (MSc.) Page 65

 Discrete Mathematics And Combinatorics (Math 2052) 2016

where �1 , �2 and �3 are constants.

a. �(�) = 6�, so we choose the particular solution to the given nonhomogeneous
recurrence relation to be , where �1 and �0 are constants to be
determined by substituting in to the given recurrence relation.

Thus,
, where �(�) = 6�
⟹ [�1(� − 1) + �0] − [�1� + �0] − 10[�1(� − 2) + �0] + 8[�1(� − 3) + �0] = 6�
⟹ −2�1� − 3�1 − �0 = 6�
⟺ −2�1 = 6 and −3�1 − �0 = 0
⟺ �1 = −3 and �0 = 9

Thus, is the particular solution of the given recurrence relation.

Hence, the general solution is
�� = �1(1�) + �2(2�) + �3(−4)� − 3� + 9

where �1 , �2 and �3 are constants.

b. �(�) = (−1)�(4)� = (−4)�, and � = −4 is the root of the characteristic equation and
the multiplicity of −4 is 1, so we choose the particular solution to the given
nonhomogeneous recurrence relation to be , where � is constant to be
determined by substituting in to the given recurrence relation.

Thus,
, where �(�) = (−4)�.
The rest of the steps are left as an exercise.
Exercise 4.3.2
1. Find the general solution (all the solutions) of the recurrence relation
a. �� = 3��−1 + 2� , for � ≥ 1

b. �� = −4��−1 − 3��−2 + 10�2 − 2� + 3 , for � ≥ 2

2. Solve the recurrence relation together with the initial conditions given.
a. �� − 2��−1 = −2� , for � ≥ 1 , �0 = 3

b. �� + 5��−1 + 6��−2 = 42(4�) , for � ≥ 2 , �0 = 4 , �1 = 1 .

3. Find the general solution (all the solutions) of the recurrence relation

a. �� − 6��−1 + 12��−2 − 8��−3 = �2 , for � ≥ 3

By: Wakuma MK kumsa (MSc.) Page 66

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Summary
A recurrence relation for a sequence is an equation that expresses �� in terms
of one or more preceding terms �0, �1, … , ��−2, ��−1.
A linear recurrence relation with constant coefficient of degree (order) � is a recurrence relation
of the form

�� + �1��−1 + �2��−2 + ⋯ + ����−� = �(�) (i)

where �1, �2, … , �� are constants and �� ≠ 0. If �(�) is identically zero (�(�) = 0), then the
recurrence relation (i) is called homogeneous, otherwise it is called nonhomogeneous.
Consider the linear homogeneous recurrence relation with constant coefficient of degree k
�� + �1��−1 + �2��−2 + ⋯ + ����−� = 0 (ii)
and consider its characteristic equation I I ik ihh hh hbh hh h h n n n n n n n nn
�� + �1��−1 + �2��−2 + ⋯ + ��−1� + �� = 0 . (iii).
If the characteristic equation (iii) has � distinct roots �1, �2, … , �� , then the sequence
is the solution of the recurrence relation (ii) if and only if
�� = �1�1� + �2�2� + ⋯ + ����� where
�1, �2, … , �� are constants.

iv. If the characteristic equation (iii) has t distinct roots �1, �2, … , �� with multiplicity
�1, �2, … , �� respectively, so that �� ≥ 1, for � = 1,2, … , � and �1 + �2 +
⋯ + �� = �, then the sequence is the solution of the recurrence relation
(ii) if and only if

�2(�2−1)��2−1)�2� + ⋯ + (��0 + ��1� + ⋯ + ��(��−1)���−1)���

where ��� are constants for 0 ≤ � ≤ � and 0 ≤ � ≤ �� − 1.

Consider the linear nonhomogeneous recurrence relations with constant coefficients of degree
�
�� + �1��−1 + �2��−2 + ⋯ + ����−� = �(�) (iv) and its
associated homogenous recurrence relation
�� + �1��−1 + �2��−2 + ⋯ + ����−� = 0 (v)

By: Wakuma MK kumsa (MSc.) Page 67

 Discrete Mathematics And Combinatorics (Math 2052) 2016

The general solution (all solutions) of the linear nonhomogeneous recurrence relation

(iv) is the sequence , where is the particular solution of the linear

nonhomogeneous recurrence relation (iv) and is the general solution (all possible
solutions) of the associated homogenous recurrence relation (v).

Self Test Exercise 4

1. Solve the recurrence relations together with the initial conditions given.
a. �� + 6��−1 = 0 , fo� � ≥ 1 , �0 = −4

b. �� − 7��−1 + 12��−2 = 0 , for � ≥ 2 , �0 = 1 , �1 = 0 .

c. .
d. �� = 7��−1 − 10��−2 , for � ≥ 2 , �0 = 2 , �1 = 1 .

e. �� = 2��−1 − ��−2 , for � ≥ 2 , �0 = 4 , �1 = 1 .

f. �� + 6��−1 + 9��−2 = 0 , for � ≥ 2 , �0 = 3 , �1 = −3

g. ��+2 = −4��−1 + 5�� , for � ≥ 0 , �0 = 2 , �1 = 8 . 2. Find the general solution (all solutions) of the
recurrence relation
a. �� + 6��−1 = 0 , for � ≥ 1 .

b.
c. �� − 2��−1 − ��−2 + 2��−3 = 0 , for � ≥ 3
3. Find the solution to the recurrence relation
�� = 5��−2 − 4��−4 = 0 for � ≥ 4 with
�0 = 3 , �1 = 2 , �2 = 6 and �3 = 8.
4. Find the general solution (all the solutions) of the recurrence relation
c. �� = 6��−1 + 2� , for � ≥ 1

d. �� = −2��−1 − ��−2 + 10�2 − 2� + 3 , for � ≥ 2

e. �� − 5��−1 − 6��−2 = 5� + 3� , for � ≥ 2

5. Solve the recurrence relation together with the initial conditions given.

By: Wakuma MK kumsa (MSc.) Page 68

 Discrete Mathematics And Combinatorics (Math 2052) 2016

c. �� − 4��−1 = −�2 , for � ≥ 1 , �0 = 1

d. �� − 5��−1 + 6��−2 = 42(4�) , for � ≥ 2 , �0 = 4 , �1 = 1 .

e. �� + 6��−1 + 9��−2 = �2� , for � ≥ 2 , �0 = 3 , �1 = −3 .

f. �� − 2��−1 + ��−2 = (�2 + 3)(5�) , for � ≥ 2 , �0 = 3 , �1 = −3 .

6. Find the general solution (all the solutions) of the recurrence relation

a. �� − 6��−1 + 12��−2 − 8��−3 = �2 , for � ≥ 3

b. �� − 6��−1 + 12��−2 − 8��−3 = �22� , for � ≥ 3

7. Solve the recurrence relation
�� = 8��−2 − 16��−4 + 2 , for � ≥ 3 with
initial condition �0 = 1 , �1 = 2 , �2 = 3 and �3 = 0.

Reference:
1. A. W.F.Edwards,Pascal’s Arithmeticical Triangle. The Johns Hopkins University Press,
Baltimore,MD, 2002.
2. C.Oliver, “ The Twelve Days of Christmas,” Mathematics Teacher, Vol. 70
3. Hewel Hus, Schaum’s outline, probability Random Variable.
4. J.M.Harris.Jeffry L.Hirst.Michael J.Mossinghoff, Combinatorics and Graph Theory, 2nd
edition

5. J.Varnadore, “ Pascal’s Triangle and Fibonacci Numbers,” Mathematics Teacher, Vol,81.

6. Kenneth H.Rosen, Discrete Mathematics and its application, 3rd edition.
7. M.Eng and J.Casey, “Pascal’s Arithmetical Triangle-ASerendipitious Source for
programming Activities,’’ Mathematics Teacher, Vol 76 mathematics
8. Mott, Knadel and Baker, Discreate Mathematics
9. P.Z.Chinn, “ inductive patterns, finite Difference, and a Missing Region,’’ Mathematics
Teacher, Vol.81(Sept.1988)
10. R.P.GRIMALDI and B.V.RAMANA pearson,Discreate combinatorial
11. Rosen , Discrete Mathematics
12. Seymour Lipschutz,Schaum’s outline, Discrete Mathematics, 3rd edition
13. Berman G.Fryer K.D, introduction to combinatorics 14. Andweson I, A first course in
Discrete Mathematics
15. D.P.Acharjya Sreekumar, Fundamental Approach to Discrete Mathematics.

By: Wakuma MK kumsa (MSc.) Page 69

 Discrete Mathematics And Combinatorics (Math 2052) 2016

CHAPTER 5

ELEMENTS OF GRAPH THEORY

Objectives: After studying this chapter, you should be able to:

 Introduce some basic definitions and concepts of graph theory
 Present useful result on the degree sequence of a graph.
 Know the terms graph, labelled graph, unlabelled graph, vertex, edge, adjacent, incident,
multiple edges, loop, simple graph and subgraph;
 Appreciate the idea of graph theory;
 Determine whether two given graphs are isomorphic;
 Know the terms degree, degree sequence and regular graph;
 State and use the handshaking lemma;
 Realize the terms walk, trail, path, closed walk, closed trail, cycle, connected graph,
disconnected graph and component;
 Understand what are meant by complete graphs, null graphs, cycle graphs, the Platonic
graphs, cubes and the Petersen graph;
 Distinguish between physical and conceptual tree structures.
 Understand what are meant by bipartite graphs, complete bipartite graphs, trees, path
graphs and cubes;
 Apply the concept of graph theory to the real world.

Introduction

You learn even in high school about graphs of functions. The graph of a function is
usually a curve drawn in the �� − plane. See Fig. (�). But the word “graph” has other
meanings. Infinite or discrete mathematics, a graph is a collection of points and edges
or arcs in the plane. Fig. (�) illustrates a graph as we are now discussing the concept.
Leonhard Euler (1707–1783) is considered to have been the father of graph theory. His
paper in 1736 on the seven bridges of Königsberg is considered to have been the
foundational paper in the subject. It is worthwhile now to review that topic.

Königsberg is a town, founded in 1256, that was originally in Prussia. Aftera stormy history, the
town became part of the Soviet Union and was renamed Kaliningrad in

By: Wakuma MK kumsa (MSc.) Page 70

 Discrete Mathematics And Combinatorics (Math 2052) 2016

1946. In any event, during Euler’s time the town had seven bridges (named Krämer, Schmiede,
Holz, Hohe, Honig, Köttel, and Grünespanning) spanning the Pregel River.
Fig. (�) gives a simplified picture of how the bridges were originally configured (two
of the bridges were later destroyed during World War II, and two others demolished by
the Russians). The question that fascinated people in the eighteenth century was
whether it was possible to walk a route that never repeats any part of the path and that
crosses each bridge exactly once.

Euler in effect invented graph theory and used his ideas to show that it is impossible to
devise such a route. We shall, in the subsequent sections, devise a broader version of
Euler’s ideas and explain his solution of the Königsberg bridge problem.

(�)A graph of a function in the plane. (�) A graph as a combinatorial object.

(�) The seven bridges at Königsberg.

5.1. Basic Terminologies

Objectives: After studying this chapter, you should be able to:

 Introduce some basic definitions and concepts of graph theory  Present useful
result on the degree sequence of a graph.
 Explain the terms degree, degree sequence and regular graph;

By: Wakuma MK kumsa (MSc.) Page 71

 Discrete Mathematics And Combinatorics (Math 2052) 2016

 Explain the terms graph, labelled graph, unlabelled graph, vertex, edge, adjacent,
incident, multiple edges, loop, simple graph and subgraph.
 State and use the handshaking lemma;

Definition 5.1: A graph G consists of a finite non-empty set V(G) of elements called
vertices together with a finite set E(G) of unordered pairs of (not necessarily distinct)
vertices called edges.

Example 5.1: The following are examples of graphs with vertices �(�) and edges
E(G)

Definition 5.2: In a graph, two or more edges joining the same pair of vertices are
multiple edges. An edge joining a vertex to itself is a loop. A graph with no multiple
edges or loops is a simple graph.

Thus, the graphs in example 5.1 (i) and (iii) are simple, that in (ii) is not, it is a nonsimple
graph. Graphs (such as those in examples (i) and (ii) ) which ‘come in one piece’ are said to
be connected. The graph in (iii) is not connected: it is the union of three connected subgraphs,
called the components of the graph.

Definition 5.3: Two vertices u and v of a graph G are adjacent if there is an edge uv joining
them and we then say that u and v are incident with the edge (or that the edge is incident with
u and v). Similarly, two edges are adjacent if they have a vertex in common.

By: Wakuma MK kumsa (MSc.) Page 72

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Example 5.2: v1 and v2 are adjacent in the following graph, each being incident with edge e1.
We call v1 and v2 the end-vertices of e1. Also edges e1 and e2 are adjacent.

In example 5.1 (ii), deg (v2) = 5 (count the loop twice), deg (v3) = 3.
In example 5.1 (iii), deg (v7) = 0. (An isolated vertex has degree 0.)
The order of a graph G is the number of vertices, |�|, where V is the set of vertices. If
there is more than one edge between the same pair of vertices, then the edges are
termed as parallel edges. Consider the graph G as

Here the edges �1 and �5 are parallel edges.

A vertex of degree 1 is called a leaf.

By the degree sequence of a graph, we mean the vertex degrees written in ascending
order with repeats where necessary. Thus the degree sequence in example 5.1 (i) is
1,2,2,3,4, that in (iii) is 0,1,1,1,2,2,3.

By: Wakuma MK kumsa (MSc.) Page 73

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Example 5.3: From the sequence 2, 2, 3, 3, 4, 4 we derive 1, 2, 2, 2, 3 and 1, 1, 1, 1.

The last sequence is the degree sequence of

Working backwards, we obtain a graph for the original sequence: (non-isomorphic answers are
possible).

By: Wakuma MK kumsa (MSc.) Page 74

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Subgraphs
In mathematics we often study complicated objects by looking at simpler objects of the
same type contained in them - subsets of sets, subgroups of groups, and so on. In graph
theory we make the following definition.

Definition 5.4: A subgraph of a graph G is a graph all of whose vertices are vertices of G
and all of whose edges are edges of G.

Remark 5.2: Note that G is a sub graph of itself.

Example 5.4: The following graphs are all subgraphs of the graph G on the left, with vertices
{�, �, �, �} and edges {1, 2, 3, 4, 5}.

The idea of a subgraph can be extended to unlabelled graphs.

Example 5.5: The following graphs are all subgraphs of the unlabelled graph H on the left;
the configuration in graph (c) occurs at each corner of H.

Union of graphs

If �1 and �2 be two graphs, then their union �1 ∪ �2is the graph with �(�1

∪ �2) = �(�1) ∪ �(�2) and �(�1 ∪ �2) = �(�1) ∪ �(�2).

By: Wakuma MK kumsa (MSc.) Page 75

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Intersection of graphs

If �1 and �2 be two graphs with at least one vertex in common, then their intersection
�1 ∩ �2is the graph with

�(�1 ∩ �2) = �(�1) ∩ �(�2) and �(�1 ∩ �2) = �(�1) ∩ �(�2).

√ Check-List
Put a tick (√) mark if you can perform the task and a cross (x) mark if you
can’t in the box against the following questions.

1. Can you define simple graph? .........................................................

2. Can you identify the difference between adjacent and incident? ..
3. Can a given graph is simple? ...........................................................

Exercise 5.1
1. Write down the vertices and edges of each of the following graphs. are these graphs simple
graphs?

2. Draw the graphs whose vertices and edges are as follows. Are these graphs simple graphs?
a. vertices: {�, �, �, �} edges: {��, ��, ��, ��}
b. vertices: {1, 2, 3,4, 5,6, 7, 8} edges: {12,22, 23,
34,35, 67,68, 78}

3. Draw, if possible, simple graphs with the following degree sequences:

(i) 2,3,3,4,5,5 (ii) 3,3,5,5,5,5 (iii) 2,2,3,3,4,5,5.

4. Which of the following statements hold for the graph on the right?
a. vertices � and ware adjacent;
b. vertices � and � are adjacent;
c. vertex � is incident with edge 2;

By: Wakuma MK kumsa (MSc.) Page 76

 Discrete Mathematics And Combinatorics (Math 2052) 2016

d. edge 5 is incident with vertex �.

5. Which of the following graphs are subgraphs of the graph G below?

6. Which of the following graphs are subgraphs of the graph H below?

7. Write down the degree sequence of each of the following graphs:

8. For each of the graphs in Problem 6, write down:the number of edges; the sum of the degrees

of all the vertices. What is the connection between your answers? Can you explain why this

connection arises?

9. (a) Use the handshaking lemma to prove that, in any graph, the number of vertices of odd
degree is even.
(b) Verify that the result of part (�) holds for each of the graphs in Pro. 6.

5.2 Isomorphism

Objectives: After studying this topic, you should be able to:

 Introduce some basic concepts of isomorphism

By: Wakuma MK kumsa (MSc.) Page 77

 Discrete Mathematics And Combinatorics (Math 2052) 2016

 Determine whether two given graphs are isomorphic

It follows from the definition that a graph is completely determined when we know its
vertices and edges, and that two graphs are the same if they have the same vertices and
edges. Once we know the vertices and edges, we can draw the graph and, in principle,
any picture we draw is as good as any other; the actual way in which the vertices and
edges are drawn is irrelevant - although some pictures are easier to use than others!

For example, recall the utilities graph, in which three houses A, Band Care joined to the
three utilities gas (g), water (w) and electricity (e). This graph is specified completely
by the following sets:

vertices: {A, B, C, g, w, e} edges: {Ag, Aw, Ae, Bg,

Bw, Be, Cg, Cw, Ce}, and can be drawn in many ways,

such as the following:

Each of these diagrams has six vertices and nine edges, and conveys the same
information - each house is joined to each utility, but no two houses are joined, and no
two utilities are joined. It follows that these two dissimilar diagrams represent the same
graph.

On the other hand, two diagrams may look similar, but represent different graphs. For
exan1ple, the diagrams below look similar, but they are not the same graph: for
example, AB is an edge of the second graph, but not the first.

By: Wakuma MK kumsa (MSc.) Page 78

 Discrete Mathematics And Combinatorics (Math 2052) 2016

We express this similarity by saying that the graphs represented by these two diagrams
are isomorphic. This means that the two graphs have essentially the same structure: we
can relabel the vertices in the first graph to get the second graph - in this case, we
simply interchange the labels wand B.

This leads to the following definition.

Definition 5.5: Two graphs G1 and G2 are isomorphic if there is a one-one

correspondence between their vertex sets V(G1) and V(G2) such that for every pair of
distinct vertices in G1 the number of edges joining them is equal to the number of
edges joining their corresponding vertices in G2. Such a one-one correspondence is an
isomorphism.

Example 5.6: The following two graphs are isomorphic with the following one-one
.
correspondence: v1 ↔ u1, v2 ↔ u4 , v3 ↔ u2 , v4 ↔ u3

Sometimes it is unnecessary to have labels on the graphs. In such cases, we omit the labels
and refer to the resulting object as an unlabelled graph.

By: Wakuma MK kumsa (MSc.) Page 79

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Example 5.7: The unlabelled graphcorresponds to either of the following isomorphic graphs:

Indeed, it also corresponds to either of the following graphs, which are isomorphic to the
above two:

We say that two unlabelled graphs such as

are isomorphic if labels can be attached to their vertices so that they become the same graph.

√ Check-List
Put a tick (√) mark if you can perform the task and a cross (x) mark if you can’t in the box

against the following questions.

1. Can you define isomorphic graphs?...................................................

2. Can you determine whether two graphs are isomorphic or not?..........
Exercise 5.2

1. By suitably relabelling the vertices, show that the following pairs of graphs are isomorphic:

By: Wakuma MK kumsa (MSc.) Page 80

 Discrete Mathematics And Combinatorics (Math 2052) 2016

2. Are the following two graphs isomorphic? If so, find a suitable one-one correspondence
between the vertices of the first and those of the second; if not, explain why no such one-one
correspondence exists.

3. By suitably labelling the vertices, show that the following unlabelled graphs are isomorphic:

5.3 Path and Connectivity

Objectives: After studying this topic, you should be able to:

 Explain the terms walk, trail, path, closed walk, closed trail, cycle, connected graph,
disconnected graph and component;
 Explain the terms edge connectivity, vertex connectivity, cutset and vertex cutset;
 Introduce concepts relating to how a connected graph can be disconnected.
 Apply the concept of path and connectivity to the real world.

Many applications of graphs involve getting from one vertex to another. For example,
you may wish to find the shortest route between one town and another. Other examples
include the routeing of a telephone call between one subscriber and another, the flow of
current between two terminals of an electrical network, and the tracing of a maze. We
now make this idea precise by defining a walk in a graph.

By: Wakuma MK kumsa (MSc.) Page 81

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Definition 5.6: A walk of length � in a graph is a succession of � edges of the form

��, ��, ��, … , ��.

This walk is denoted by ����. . . ��, and is referred to as a walk between � and �.

We can think of such a walk as going from � to �, then from � to �, then from � to �,
and so on, until we arrive eventually at the vertex �. Since the edges are undirected, we
can also think of it as a walk from � to � and on, eventually, to �, �, � and �. So we can
equally well denote this walk by ��. . . ����, and refer to it as a walk between � and �.
Note that we do not require all the edges or vertices in a walk to be different.

Example 5.8: In the following graph, ���������� is a walk of length 9 between the vertices
� and �, which includes the edge �� twice and the vertices �, �, � and � twice.

It is sometimes useful to be able to refer to a walk under more restrictive conditions in which
we require all the edges, or all the vertices, to be different.

Definition 5.7: A trail is a walk in which no edge has been traversed more than once
(in either direction) but repeated vertices are allowed. It is closed if the last vertex is the

By: Wakuma MK kumsa (MSc.) Page 82

 Discrete Mathematics And Combinatorics (Math 2052) 2016

same as the first, and open otherwise. A path is a walk in which all the edges and all the
vertices are different.

Example 5.9: In the following graph above, the walk ������� is a trail which is not a
path, since the vertices � and � both occur twice, whereas the walk ����� has no
repeated vertices, and is therefore a path.

Example 5.10: In the graph below,

- acbdce is an open trail
- acbdcea is a closed trail
- acbdcbe is not a trail, since edge cb has been traversed twice, it is a walk.

We can use the concept of a path to define a connected graph. Intuitively, a graph is connected if it
is ‘one piece’

By: Wakuma MK kumsa (MSc.) Page 83

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Example 5.11: The following graph is not connected, but can be split into four connected
subgraphs.

The observation that there is a path between x and y (which lie in the same subgraph),
but not between II and y (which lie in different subgraphs), leads to the following
definitions.

Definition 5.8: A graph is connected if there is a path between each pair of vertices,
and is disconnected otherwise. An edge in a connected graph is a bridge if its removal
leaves a disconnected graph. Every disconnected graph can be split up into a number of
connected subgraphs, called components.

Example 5.12: In the graph in exercise 5.3 (2), the edge �� is a bridge; and the following
disconnected graph has three components:

It is also useful to have a special term for those walks or trails that start and finish at the same
vertex. We say that they are closed.

Definition 5.9: A closed walk in a graph is a succession of edges of the form

��, ��, ��, . . . , ��, ��, that starts and ends at the same vertex. A closed trail is a closed
walk in which all the edges are different. A cycle is a closed walk in which all the edges are
different and all the intermediate vertices are different. A walk or trail is open if it starts and
finishes at different vertices.

By: Wakuma MK kumsa (MSc.) Page 84

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Example 5.13: Consider the following graph:

The closed walk ������� is a closed trail which is not a cycle, whereas the closed
trails ��, ����� and ������ are all cycles. A cycle of length 3, such as ���� or
����, is called a mangle. In describing closed walks, we can allow any vertex to be
the starting vertex. For example, the triangle ���� can equally well be written as
���� or ���� or (since the direction is immaterial) by ����, ���� or ����.

Disconnecting Sets (this involves edges)

Recall that a graph is connected if there is a path joining each pair of vertices. Let G be
a connected graph. By a disconnecting set we mean a set of edges whose deletion
results in a disconnected graph. A cutset is a disconnecting set, no proper subset of
which is a disconnecting set.

By: Wakuma MK kumsa (MSc.) Page 85

 Discrete Mathematics And Combinatorics (Math 2052) 2016

√ Check-List
Put a tick (√) mark if you can perform the task and a cross (x) mark if you
can’t in the box against the following questions.

1. Can you define walk? ..........................................................................

2. Do you know the difference between trail and path?...........................
3. Do you know the difference between closed trail and cycle?...............
4. Can a simple graph is connected graph? ...............................................

Exercise 5.3

1. Write down all the paths between � and � in the following graph:

2. Draw:
a. a connected graph with eight vertices;
b. a disconnected graph with eight vertices and two components;
c. a disconnected graph with eight vertices and three components.

By: Wakuma MK kumsa (MSc.) Page 86

 Discrete Mathematics And Combinatorics (Math 2052) 2016

3. For the graph on the right, write down:

a. a closed walk that is not a closed trail;
b. a closed trail that is not a cycle;
c. all the cycles of lengths 1,2,3 and 4.
4. Find the vertex connectivity and the edge connectivity for each of the following graphs,
giving reasons for your answers.

(i) (ii)

(iii) (iv)

By: Wakuma MK kumsa (MSc.) Page 87

 Discrete Mathematics And Combinatorics (Math 2052) 2016

5.4. Complete, regular and bipartite graphs

Objectives: After studying this topic, you should be able to:

 Explain what are meant by complete graphs, null graphs, cycle graphs, the Platonic
graphs, cubes and the Petersen graph;
 Explain what are meant by bipartite graphs, complete bipartite graphs and path
graphs .

Null graphs

These are graphs with no edges and are denoted by Nn.

Example 5.16: the null graph on 4 vertices

Complete graphs

Definition 5.10: The complete graph on n vertices, denoted by Kn, is the simple graph in
which every pair of vertices is joined by an edge.

Example 5.17: The following graphs are complete graphs

K3 K4

K5 K6

By: Wakuma MK kumsa (MSc.) Page 88

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Regular graphs

These are graphs in which every vertex has the same degree. For example, Kn is regular of
degree n-1. Regular graphs of degree 3 are called cubic graphs. The number of edges of a
regular graph with n vertices is given by n(n - 1)/2. The following regular graph, called
the Petersen graph is an interesting example.

Bipartite graphs

Definition 5.11: A graph G is bipartite if every vertex can be labelled with either a or b,
so that every edge is an ab edge. In these graphs, the vertex set is the union of two non-
empty disjoint sets A and B with each edge of the graph joining a vertex in A to a
vertex in B.

a b A a a a
b b a 

a b B b b b b

Complete bipartite graphs

Kr,s denotes the simple bipartite graph in which the sets A and B (as above) contain r and s
vertices and every vertex in A is adjacent to every vertex in B.

K3,4

By: Wakuma MK kumsa (MSc.) Page 89

 Discrete Mathematics And Combinatorics (Math 2052) 2016

The Platonic graphs

These are formed from the vertices and edges of the 5 regular (Platonic) solids:

The complement of a simple graph

Definition 5.12: The complement of a simple graph G is the simple graph with the same
vertex set as G with two vertices adjacent if and only if they are not adjacent in G.
It is denoted by G .

Example 5.18: if G is then is �

By: Wakuma MK kumsa (MSc.) Page 90

 Discrete Mathematics And Combinatorics (Math 2052) 2016

√ Check-List
Put a tick (√) mark if you can perform the task and a cross (x) mark if you can’t in the box

against the following questions.

1. Can you define complete graph? ........................................................

2. Can you define regular and bipartite graph? .......................................
3. Can you explain the relation between a simple graph and its complement?..
4. Can you define platonic graph? ...............................................................

Exercises 4.4

1. Give (if it exists) an example of each of the following:

i. A Platonic graph that is a complete graph.
ii. A bipartite Platonic graph.
iii. A bipartite graph that is regular of degree 4. iv. A cubic graph with 7
vertices.

By: Wakuma MK kumsa (MSc.) Page 91

 Discrete Mathematics And Combinatorics (Math 2052) 2016

2. Determine the number of edges of the following graphs:

(i) K8 (ii) K5,7 (iii) the Peterson graph.

3. Draw the complements of the following graphs:

4. Which of the following graphs are bipartite?

(i) Petersen
(ii) C6 (6 – cycle): (iii) C7 (7 – cycle):

(iv) (v)

5.5. Eulerian and Hamiltonian Graphs

Objectives: After studying this topic, you should be able to:

 Define Eulerian and Hamiltonian graphs;
 Discuss Semi-Eulerian graphs;
 introduce the idea of a Semi-Hamiltonian graph;
 Present some simple criteria for determining whether a graph is Hamiltonian.

Eulerian and Semi-Eulerian Graphs

Definition 5.13: A connected graph G is Eulerian if there is a closed trail containing every
edge of G. We call such a trail an Eulerian trail.

By: Wakuma MK kumsa (MSc.) Page 92

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Example 5.20: the following graphs are Eulerian

(i)

Theorem 5.4: (Euler 1736). A connected graph is Eulerian if and only if every vertex has
even degree.

To find an Eulerian trail in a given graph, start in an arbitrary vertex and traverse along the
edges, ensuring all the edges are traversed before returning to the starting vertex.

If G is not Eulerian, but there is an open trail containing every edge of G, then G is semi-
Eulerian.

Example 5.21:

Theorem 5.5: A connected graph is semi-Eulerian if and only if precisely two of its vertices
have odd degree.

To obtain a semi-Eulerian trail in a given graph, you must start at one of the odd degree vertices
and end in the other odd degree vertex.
The following is an example of a graph that is neither Eulerian nor semi-Eulerian.

Hamiltonian and semi-Hamiltonian Graphs

Definition 5.14: A graph G is Hamiltonian if there is a cycle that passes through every vertex
of G. Such a cycle is a Hamiltonian cycle.

If G is not Hamiltonian, but there is an open path which includes every vertex of G, then G
is semi- Hamiltonian, and such a path is a Hamiltonian path.

By: Wakuma MK kumsa (MSc.) Page 93

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Example 5.22:

Hamiltonian semi- Hamiltonian neither Hamiltonian

nor semi- Hamiltonian
Theorem 5.6: (Ore 1960): Let G be a simple graph with n 3 vertices. If deg(u) deg(v)
n for each pair of non-adjacent vertices u and v, then G is Hamiltonian.

Corollary 5.7: (Dirac 1952). Let G be a simple graph with n 3 vertices. If deg(v) n/ 2 for
every vertex v, then G is Hamiltonian.

Note that this is a necessary condition, but not sufficient.

Example 5.23: The Petersen graph is non-Hamiltonian but Kn , (n 3) graphs are Hamiltonian.

Bipartite graphs can only be Hamiltonian if sets A and B of vertices (as previously
defined) have the same number of vertices. It follows that if the total number of
vertices in a bipartite graph is odd then it cannot be Hamiltonian. There is no known
general criterion for testing whether a graph is semi-Hamiltonian.
Example 5.24: Consider the following four graphs:

graph (a) is both Eulerian and Hamiltonian, as we saw above; graph (b) is Eulerian - an
Eulerian trail is �������; it is not Hamiltonian; graph (c) is Hamiltonian -a Hamiltonian
cycle is ������; it is not Eulerian; graph (d) is neither Eulerian nor Hamiltonian.

By: Wakuma MK kumsa (MSc.) Page 94

 Discrete Mathematics And Combinatorics (Math 2052) 2016

√ Check-List
Put a tick (√) mark if you can perform the task and a cross (x) mark if you can’t in the box
against the following questions.

1. Can you define Eulerian graphs? ...............................................................

2. Can you define Hamiltonian graph? .........................................................
3. Can you explain the relation between a Eulerian and Hamiltonian graph? ......
4. Can you define semi-Eulerian and semi-Hamiltonian graph? ........................

Exercises 5.5
1. Determine whether the following graphs are Eulerian, semi-Eulerian or neither. For those that are
Eulerian or semi-Eulerian, find a suitable trail.

(i) ii) v1 v2 v3
v1 v5 v6 v2

v7
v8

v3 v7 v9 v8 v4 v4 v5 v6

(iii) (iv) (v)

v1 v6 v2 v1 v6 v2 v1 v6 v2

v9 v9 v9 v7
v5 v7 v5 v7 v5

v4 v8 v3 v4 v8 v3 v4 v8 v3

2. In the Petersen graph,

a. Find walks of lengths 5, 6 and 8.
b. Find cycles of lengths 5, 6, 8 and 9.

By: Wakuma MK kumsa (MSc.) Page 95

 Discrete Mathematics And Combinatorics (Math 2052) 2016

c. Can you find a cycle of length 10?

d. What is the size of the smallest cycle?
3. Determine whether the following graphs are Hamiltonian, semi- Hamiltonian or neither.
Find a Hamiltonian cycle or path if one exists.

(i) (i )
i

(ii) (i )
i v

(v) (vi)

4. Decide which of the following graphs are Eulerian and/or Hamiltonian, and write down an Eulerian
trail or Hamiltonian cycle where possible.

By: Wakuma MK kumsa (MSc.) Page 96

 Discrete Mathematics And Combinatorics (Math 2052) 2016

5. Determine which of the following graphs are Eulerian:

a. the complete graph K8;
b. the complete bipartite graph K8,8;
c. the cycle graph C8;
d. the dodecahedron graph;
e. the cube graph Q8.

5.6. Tree Graphs

Objectives: After working through this topic, you should be able to:
 state several properties of a tree, and give several equivalent definitions of a tree;
 distinguish between physical and conceptual tree structures, and give examples of
each type;
 appreciate the uss of rooted trees in different areas;
 construct the bipartite graph representation of a given braced rectangular frame-
work and use it to determine whether the system is rigid; if so, determine whether
the system is minimally braced. define tree.
In this topic we focus our attention on one particularly important and useful type of
graph - a tree. Although trees are relatively simple structures, they form the basis of
many of the practical techniques used to model and to design large-scale systems.

The concept of a tree is one of the most important and commonly used ideas in graph
theory, especially in the applications of the subject. It arose in connection with the work
of Gustav Kirchhoff on electrical networks in the 1840s, and later with Arthur Cayley's
work on the enumeration of molecules in the 1870s. More recently, trees have proved

By: Wakuma MK kumsa (MSc.) Page 97

 Discrete Mathematics And Combinatorics (Math 2052) 2016

to be of value in such areas as computer science, decision making, linguistics, and the
design of gas pipeline systems.

Trees are often used to model situations involving various physical or conceptual treelike structures.
These structures are also commonly referred to as 'trees'. In the following examples, we classify
such 'trees' in terms of the type of application in which they occur. Many trees have a physical
structure which may be either natural or artificial and either static or time-dependent. Two
examples of natural trees are the biological variety with trunk, branches and leaves, and the
drainage system of tributaries forming a river basin. Less obvious examples of tree structures are
provided by the chemical structure of certain organic molecules.

One of the most important classes of bipartite graphs is the class of trees. If G is a tree then G is
bipartite, i.e. all of its vertices can be labelled with either a or b so that every edge is an ab edge
(no aa or bb edges).

Definition 5.15: A tree is a connected graph without cycles.

Examples 5.25:

By: Wakuma MK kumsa (MSc.) Page 98

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Starting with the tree with just one vertex, we can build up any tree we wish by
successively adding a new edge and a new vertex. At each stage, the number of vertices
exceeds the number of edges by 1, so every tree with n vertices has exactly n - 1 edges.
At no stage is a cycle created, since each added edge joins an old vertex to a new vertex.
At each stage, the tree remains connected, so any two vertices must be connected by at
least one path. However, they cannot be connected by more than one path, since any
two such paths would contain a cycle (and possibly other edges as well).

We therefore deduce that any two vertices in a tree are connected by exactly one path.

In particular, any two adjacent vertices are connected by exactly one path - the edge
joining them. If this edge is removed, then there is no path between the two vertices.

It follows that the removal of any edge of a tree disconnects the tree. Moreover, any
two vertices v and w are connected by a path, and the addition of the edge vw produces
a cycle - the cycle consisting of the path and the added edge vw.

So joining any two vertices of a tree by an edge creates a cycle.

Several of the above properties can be used as definitions of a tree. In the following
theorem, we state six possible definitions. They are all equivalent: anyone of them can
be taken as the definition of a tree, and the other five can then be deduced.

By: Wakuma Masresha (MSc.) Page 99

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Theorem 5.8: Let G be a graph with n vertices. Then the following statements are
equivalent.
i. G is connected and has no cycles; ii. G has n-1 edges and
has no cycles; iii. Any two vertices in G are connected by
exactly one path; iv. G is connected and the removal of any edge
disconnects G;
v. G contains no cycle but the addition of any new edge to G creates exactly
one cycle;

Definition 5.16: Let G be a connected graph. Then a spanning tree in G is a subgraph

of G that includes every vertex and is also a tree.

Example 5.26: The following diagram shows a graph and three of its spanning trees.

Given a connected graph, we can construct a spanning tree by using either of the
following two methods. We illustrate these by applying them to the graph G above.

Building-up method: Select edges of the graph one at a time, in such a way that no
cycles are created; repeat this procedure until all vertices are included.

Example 5.27: In the above graph G, we select the edges ��, ��, ��, ��; then no
cycles are created. We obtain the following spanning tree.

Cutting-down method : Choose any cycle and remove any one of its edges; repeat this
procedure until no cycles remain.

By: Wakuma Masresha (MSc.) Page 100

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Example 5.28: From the above graph G, we remove the edges �� (destroying the
cycle ����), �� (destroying the cycle �����), �� (destroying the cycle ����). We
obtain the following spanning tree.

√ Check-List

Put a tick (√) mark if you can perform the task and a cross (x) mark if you can’t in the
box against the following questions.

1. Can you define a tree? ...............................................................

2. Can you construct the spanning tree of a given graph by using both

methods?

By: Wakuma Masresha (MSc.) Page 101

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Exercise 5.6

1. Draw the branching tree representing the outcomes of two throws of a six-sided die.
2. Give an example of a tree with seven vertices and
a. exactly two vertices of degree 1;
b. exactly four vertices of degree 1;
c. exactly six vertices of degree 1.
3. Use the handshaking lemma to prove that every tree with n vertices, where � ≥ 2, has
at least two vertices of degree 1.
4. Use a proof by contradiction to show that the removal of an edge cannot disconnect a
tree into more than two components.
5. Use a proof by contradiction to show that the addition of a new edge to a tree cannot
create more than one cycle.
6. Use each method to construct a spanning tree in the complete graph K5.

7. The graph G below has twenty-one spanning trees. Find as many of them as you can.

8. Find three spanning trees in the Petersen graph.

By: Wakuma Masresha (MSc.) Page 102

 Discrete Mathematics And Combinatorics (Math 2052) 2016

5.7. Planar Graphs

Objectives: After studying this topic, you should be able to:
 Introduce the topic of planar graphs, and to present some simple properties of
such graphs.
 Explain the terms planar graph, non-planar graph, plane drawing, face, infinite
face, degree of a face, subdivision of a graph and contraction of a graph;
 Use the handshaking lemma for planar graphs;
 State and use Euler's formula;
 Explain the term dual graph and describe its properties;
 Present the Kuratowski theorem and discuss its use in determining whether a
graph is planar.
In this chapter we investigate the properties of graphs that can be drawn in the plane
without any of their edges crossing; such graphs are called planar graphs. In particular,
we determine whether the complete bipartite graph K3,3 is planar, thereby solving the
utilities problem. We discuss Euler's formula and Kuratowski's theorem; the latter is an
important theoretical result which gives a necessary and sufficient condition for a graph
to be planar.

Definition 5.17: A graph G is planar if it can be drawn in the plane without its edges
crossing. Such a drawing is called a plane drawing or a plane graph. A graph G is non-
planar if no plane drawing of G exists.

Example 5.29:

(i) The graph K4 is planar.

Here are two plane drawings:

By: Wakuma Masresha (MSc.) Page 103

 Discrete Mathematics And Combinatorics (Math 2052) 2016

(ii) The graph K2,3 is planar.

Here is a plane drawing:

For some graphs, such as K3,3, it is impossible to find a drawing that involves no
crossings, therefore, K3,3 is an example of non planar graph.

Definition 5.18: A plane graph divides the plane into regions called faces. If we denote
the i-th face by fi , then fi represents the number of edges bordering fi .

Example 5.30:

(i) (ii)
f3
f1 f2 f3 f2 f3 f4 f5

f4
f1

Graph (i) has 4 faces and graph (ii) has 5.

Theorem 5.10( Euler’s Formula) (Euler 1750): Let G be a connected plane graph, and
let n, m and f be the respective number of vertices, edges and faces of G as before.
Then n – m + f = 2.

By: Wakuma Masresha (MSc.) Page 104

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Definition 5.19: A minor of G is a graph obtained from G by repeatedly deleting and/or

contracting edges.

Given an edge e in a graph G, by contracting the edge e, we mean combining its end
vertices by bringing them closer and closer together until they become one and
replacing multi-edges by a single edge. We denote the graph obtained in this by G\e.
Deletion of an edge is denoted by G-e.

Example 5.32:

e
 

G G–e G\e
e

 

G G–e G\e

Given a non-planar graph (such as K5 or K3,3 ) if we ‘reverse’ a contraction or deletion

(i.e. add an edge) then it still remains non-planar. This is the basis for the Kuratowski
theorem.
Theorem 5.12 (Kuratowski theorem): A graph G is non-planar then it MUST contain
either a K5 or K3,3 minor.

G is non-planar G has a K5 or K3,3 minor.

This is a useful result for determining whether a graph is planar or not. (For graphs with
not many vertices and edges it may be easier to try finding a plane drawing to show
planarity.)

By: Wakuma Masresha (MSc.) Page 105

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Example 4.33:
1. The Petersen graph is non-planar as it has a K5 minor. (It also has a K3,3 minor.)

e Contract e, f, g, h, i.
-->

i f

h g
Petersen K5

2. The following graph is non-planar as it has a K3,3 minor.

h f i
e g Delete e, f, g and
contract h, i. a

K3,3 a b

Dual Graphs

Given a plane drawing of a planar graph G, its dual G* is constructed as follows:

(i) Choose a point v* inside each face of G and make v* vertices of G*.

(ii) For each edge e of G draw a line e* joining the v* inside the faces on each
side of e and make e* the edges of G*.

√ Check-List

Put a tick (√) mark if you can perform the task and a cross (x) mark if you can’t in the

box against the following questions.

1. Can you define a planar graph? ...............................................................

2. Can you state Euler formula and Kuratowski theorem? ............................
3. Can you define minor? ............................................................................
4. Can you find the minors of a given graph? .................................................

By: Wakuma Masresha (MSc.) Page 106

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Exercise 5.7
2.Deduce that the Petersen graph is non-planar.
3.Show that the Petersen graph has a K3,3 minor.

4.Use Kuratowski’s theorem to show that the following graphs are non-planar.

(i) (ii)

(iii) (iv)

5. Draw the duals of the following graphs.

6. Draw G* and G** for the following disconnected graph G.

By: Wakuma Masresha (MSc.) Page 107

 Discrete Mathematics And Combinatorics (Math 2052) 2016

5.8 Graph Colouring

Objectives: After studying this section, you should be able to:

 Introduce the topic of vertex colouring and an application of it to a storage
problem.
 Define the term, chromatic number, and present methods of determining it.
 Explain the terms vertex colouring, k-colouring and chromatic number;
 State 4-colour Theorem;
 Apply Brooks' theorem;
 Explain what are meant by colouring problems, the map colouring problem and
domination problems, and how they can be represented as vertex decomposition
problems.

Introduction

A chemical company wants to ship 6 chemicals, C1,,C6, in such a way that those

which react violently together are stored in separate containers. The problem is how to
store the chemicals using minimum number of containers. Pairs of chemical that react
violently together are:

C1C2, C1C6, C1C5, C2C3, C2C6, and C5C6 .

The problem can be solved by drawing a ‘react violently’ graph, F, whose vertices are
Ci and its edges are CiC j (i, j =1,,6), where Ci and C j react together violently. If we
now assign colours to the vertices of F so that no two adjacent vertices have the same
colour, we see that we require at least three colours. This minimum number of colours
is called the chromatic number and is denoted by the Greek letter χ , (chi). For this
problem, therefore, χ(F) = 3, as two colours would not be sufficient to colour the
adjacent vertices differently. So three containers are required to transport the chemicals
safely.

By: Wakuma Masresha (MSc.) Page 108

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Definition 5.20: For a simple graph G, we say that G is k-colourable if we can colour
each vertex from a set of k colours in such a way that for every edge its two end
vertices have a different colour. The smallest k for which this is possible is called the
chromatic number of G, denoted by χ(G).

Remark 5.13: The above definitions are given only for simple graphs. Loops must be
excluded since, in any -colouring, the vertices at the ends of each edge must be
assigned different colours, so the vertex at both ends of a loop would have to be
assigned a different colour from itself. We also exclude multiple edges, since the
presence of one edge between two vertices forces them to be coloured differently, and
the addition of further edges between them is then irrelevant to the colouring. We
therefore restrict our attention to simple graphs.

By: Wakuma Masresha (MSc.) Page 109

 Discrete Mathematics And Combinatorics (Math 2052) 2016

We usually show a k-colouring by writing the numbers 1,2, ..., next to the appropriate
vertices. For example, diagrams (a) and (b) below illustrate a 4-colouring and a
3colouring of a graph G with five vertices; note that diagram (c) is 1lot a 3-colouring of
G, since the two vertices coloured 2 are adjacent.

Example 5.36: Let H be the path on 3 vertices. Then, H (1) 0, H (2) 2 , (so

(H) 2), H (3) 12, H (4) 36, and so on.

k k -1 k -1 k -1 k k -1
OR

So we have H (k) k(k 1)2 .

By: Wakuma Masresha (MSc.) Page 110

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Example 5.37:

1. Null graphs.

If G Nn is the null graph with n vertices, then (k)

G kn.

2. Trees.

If G Tn is any tree with n vertices, then G (k) k(k 1)n 1

.

For example, the graph H above is a T3 .

3. Complete graphs.

If G Kn is the complete graph with n vertices, then

G (k) k(k 1)(k 2)(k n 1).

For example, for the graph K4 we have

k -3 k -2

Theorem 5.14 (Brooks 1941): If G is a simple connected graph which is not an odd
cycle or a K n , then (G) (G). (That is, G is (G) -colourable.)

Remark 5.15:We have (Codd ) 3 2 (Codd ) and we have

(Kn ) n (Kn ) n 1, hence these two classes of graphs are excluded from
the

statement of Brook’s theorem above.

Theorem 5.16: (4-Colour theorem) (Appel and Haken 1976).Every simple planar
graph is 4-colourable. (i.e. (G) 4 for any planar graph G.)

By: Wakuma Masresha (MSc.) Page 111

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Definition 5.21: An independent set in a graph G is a set of vertices of G, no two of

which are adjacent. The independence number of a graph G, denoted by i(G), is the
size of the largest independent set. It is useful to know i(G) as it can be used to find the
lower bound for (G) as

i(G) (G) (G),

where n is the number of vertices of G and the symbol a means the smallest
integer greater than or equal to the real number a.

Definition 5.22: If G is an undirected graph, any subgraph of G that is a complete

graph is called a clique in G. A clique-partition of G is a partition of all vertices of G
into cliques. A graph can have many clique-partitions.

Example 5.38: for graph L below

i i

3 parts clique-partition K5, K3, K3 5 parts clique-partition K4, K3, K2, K1, K1

Given a clique-partition of a graph G with k parts, an independent set of G can have at

most one vertex from each part, since vertices from the same part are adjacent. So
i(G)k . For L above, we have found a clique-partition with 3 parts, and one with 5 parts;
so i(L) 3. Now try to use the clique-partition with 3 parts to find an independent set of
size 3. This is possible for L as the 3 vertices labelled i form an independent set of size
3, so i(L) 3.

By: Wakuma Masresha (MSc.) Page 112

 Discrete Mathematics And Combinatorics (Math 2052) 2016

In the above example, we had equality between i(L) and some k. This need not always

be the case. For example the Petersen graph, P, has no K3 's, K4 's, as subgraphs; only

K2 's (edges) and K1's (vertices). It has 10 vertices, so every clique-partition with k parts

must have k 5. But i(P) 4 k . So clique-partitions cannot always be used to find

the independence number M.

Chapter Summary
 A graph is a diagram consisting of points, called vertices, joined by lines, called
edges; each edge joins exactly two vertices.

 In a graph, two or more edges joining the same pair of vertices are multiple edges.
 An edge joining a vertex to itself is a loop.
 A graph with no multiple edges or loops is a simple graph.
 Two vertices adjacent if they have an edge in common.
 Two edges are adjacent if they have a vertex in common.
 A subgraph of a graph G is a graph all of whose vertices are vertices of G and all of
whose edges are edges of G.

 Handshaking Lemma states that in any graph, the sum of all the vertex degrees is
equal to twice the number of edges.

 Two graphs are isomorphic if there is a one-one correspondence between their

vertex sets.

 A walk in a graph G is a finite sequence of edges of the form

v0v1,v1v2 ,v2v3 ,,vm 1vm (also written v0v1v2v3 vm ).

 The number of edges in the walk is called its length.

 A trail is a walk in which no edge has been traversed more than once (in either
direction) but repeated vertices are allowed.

 A path is a walk in which all the edges and all the vertices are different.
 A graph is connected if there is a path between each pair of vertices, and is
disconnected otherwise

By: Wakuma Masresha (MSc.) Page 113

 Discrete Mathematics And Combinatorics (Math 2052) 2016

 A complete graph, denoted by Kn, is the simple graph in which every pair of
vertices is joined by an edge.

 A graph G is bipartite if every vertex can be labelled with either a or b, so that

every edge is an ab edge.

 A connected graph G is Eulerian if there is a closed trail containing every edge of G.

We call such a trail an Eulerian trail.

 A graph G is Hamiltonian if there is a cycle that passes through every vertex of G.

Such a cycle is a Hamiltonian cycle.

 A tree is a connected graph without cycles.

 A spanning tree in a connected graph G is a subgraph of G that includes every
vertex and is also a tree.

 A graph G is planar if it can be drawn in the plane without its edges crossing.
 A minor of G is a graph obtained from G by repeatedly deleting and/or contracting
edges.

 G is k-colourable if we can colour each vertex from a set of k colours in such a way
that for every edge its two end vertices have a different colour.The smallest k for
which this is possible is called the chromatic number of G, denoted by (G).

Self Test Exercise 4

1. Consider the graph G shown on the right. Which of the following statements hold
for G?
a. vertices v and x are adjacent;
b. edge 6 is incident with vertex w;
c. vertex x is incident with edge 4;

d. vertex wand edges 5 and 6 form a subgraph of G.

2. Draw an example of each of the following, each with 5 vertices and 8 edges:
i. a simple graph,
ii. a non-simple graph with no loops,
iii. a non-simple graph with no multiple edges.

By: Wakuma Masresha (MSc.) Page 114

 Discrete Mathematics And Combinatorics (Math 2052) 2016

3. Which of the following are possible degree sequences of simple graphs. Draw graphs for
those that are.
(i) 1,2,2,3 (ii) 1,2,3,4 (iii) 0,0,1,1,2,2
(iv)1,2,3,3,4 (v) 2,2,3,3,4,4 (vi) 2,3,3,4,5,5.
4. (a) Show that the following two graphs are isomorphic:

v2

u1 v3 v4

(b) Give a reason why the following two graphs cannot be isomorphic:
v1 v4 u1 u4
v5 v8 u8

v6 v7 u6 u7
v2 v3
u2 u3

5. By suitably labelling the vertices, show that the following graphs are isomorphic:

6. Draw the eleven unlabelled simple graphs with four vertices.

7. (a) If two graphs have the same degree sequence, must they be isomorphic?
(b) If two graphs are isomorphic, must they have the same degree sequence?
8. Let G be a graph with degree sequence (1, 2, 3, 4). Write down the number of vertices
and number of edges of G, and construct such a graph. Are there any simple graphs with
degree sequence (1, 2, 3, 4)?
9. Prove that, if G is a simple graph with at least two vertices, then G has two or more
vertices of the same degree.
10. For the graph shown on the right, write down:
a. a walk of length 7 between � and �;
b. all the cycles of lengths 1,2,3 and 4;

By: Wakuma Masresha (MSc.) Page 115

 Discrete Mathematics And Combinatorics (Math 2052) 2016

c. a path of maximum length.

11. Draw:
a. two non-isomorphic regular graphs with 8 vertices and 12 edges;
b. two non-isomorphic regular graphs with 10 vertices and 20 edges.
12. For which values of n, rand s are the following graphs Eulerian? For which values are
they semi-Eulerian?
a. the complete graph ��;
b. the complete bipartite graph ��,�;
c. the �-cube ��.
13. For which values of �, �and � are the graphs in Exercise 9 Hamiltonian? For which
values are they semi-Hamiltonian?
14. Draw two graphs each with 10 vertices and 13 edges: one that is Eulerian but not
Hamiltonian and one that is Hamiltonian but not Eulerian.
15. Decide which of the following graphs are planar.

For each planar graph, give a plane drawing.

16. By finding a plane drawing, show that the following graph is planar.

17. Let G be a planar graph with k components, and let �, � and � denote, respectively, the
numbers of vertices, edges and faces in a plane drawing of G.
a. Show that if each component has at least three vertices, then Euler's formula has the
form
� − � + � = � + 1.

By: Wakuma Masresha (MSc.) Page 116

 Discrete Mathematics And Combinatorics (Math 2052) 2016

b. Deduce that if G is simple and each vertex has degree at least 2, then
� < 311 − 3(� + 1).
18. Give an example of a connected planar graph G with 7 vertices such that its complement
is also planar.

REFERENCE

[1]. I. Anderson, A First Course in Discrete Mathematics,2002.

[2]. C. Berge, Graphs and Hypergraphs, North-Hoi Land Publishing
CompanyAmsterdam, 1976.
[3]. A. Bezdek, Discrete Geometry, Marcel Dekker, 2003.
[4]. N. L. Biggs, Discrete mathematics, Oxford University Press, 2002.
[5]. Eric W., "Discrete mathematics" from MathWorld.
[6]. S. Finch, Bipartite, k-Colorable and k-Colored Graphs, 2003.
[7]. Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied
Introduction 5th ed. Addison Wesley.
[8]. T. R. Hodkinson and John A. N. Parnell, Reconstructing the Tree of Life: Taxonomy and
systematics of species rich taxa, CRC Press, 2007.
[9]. B. Hopkins, Resources for Teaching Discrete Mathematics, Mathematical
Association of America, 2008.
[10]. R. Johnsonbaugh, Discrete Mathematics, New Jersey, 2005.
[11]. R. Johnsonbaugh, Discrete Mathematics, Prentice Hall, 2008.
[12]. S. G. Krantz, Discrete Mathematics Demystified, McGraw-Hill, 2009.
[13]. B. Mohar and C. Thomassen, Graphs on Surfaces, Johns Hopkins University
press, 2001.
[14]. K.H. Rosen &J.G. Michaels, Handbook of Discrete and Combinatorial Mathematics, CRC
Press, 2000.
[15]. K. H. Rosen, Discrete Mathematics and Its Applications 6th ed. McGraw Hill. [16].
R. J. Wilson, Introduction to Graph Theory, Longman, 1996.
[17]. D. B. West, Introduction to Graph Theory, 2005.

By: Wakuma Masresha (MSc.) Page 117

 Discrete Mathematics And Combinatorics (Math 2052) 2016

CHAPTER 5 DIRECTED GRAPHS

Objectives: After studying this chapter, you should be able to:

 Understand the terms digraph, labelled digraph, unlabelled digraph, vertex, arc,
adjacent, incident, multiple arcs, loop, simple digraph, underlying graph and
subdigraph;
 Appreciate the uses of rooted trees in different areas;
 determine whether two given digraphs are isomorphic;
 Understand the terms in-degree, out-degree, in-degree sequence and out-degree
sequence.
 state and use the handshaking dilemma;
 realize walk, trail, path, closed walk, closed trail, cycle, connected,
disconnected and strongly connected in the context of digraphs;
 Know the terms Eulerian digraph and Eulerian trail;
 State a necessary and sufficient condition for a connected digraph to be Eulerian;
 Know the terms Hamiltonian digraph and Hamiltonian Cycle;
 describe the use of digraphs in ecology, social networks, the rotating drum
problem, and ranking in tournaments.

Introduction

In this chapter we discuss digraphs and their properties. Our treatment of the subject is
similar to that of Chapters 4 for graphs, except that we need to take account of the
directions of the arcs.

By: Wakuma Masresha (MSc.) Page 118

 Discrete Mathematics And Combinatorics (Math 2052) 2016

5.1. Basic Terminologies

Objectives: After studying this section, you should be able to:

 define the terms digraph, labelled digraph, unlabelled digraph, vertex, arc,
adjacent, incident, multiple arcs, loop, simple digraph, underlying graph and
subdigraph;
 determine whether two given digraphs are isomorphic;
 explain the terms in-degree, out-degree, in-degree sequence and out-degree
sequence
 state and use the handshaking dilemma;

Definition 5.1: A directed graph (digraph) consists of a set of elements called vertices
and a set of elements called arcs. Each arc joins two vertices in a specified direction.

Example 5.1: the digraph shown below has four vertices {�, �, �, �} and six arcs

{1, 2, 3, 4, 5, 6}. Arc 1 joins � to �, arc 2 joins � to �, arcs 3 and 4 join � to �,

arc 5 joins � to �, and arc 6 joins the vertex � to itself.

We often denote an arc by specifying its two vertices in order; for example, arc 1 is
denoted by ��, arcs 3 and 4 are denoted by ��, and arc 6 is denoted by ��. Note that
�� is not the same as ux.

The above digraph contains more than one arc joining � to �, and an arc joining the
vertex � to itself. The following terminology is useful when discussing such digraphs.

By: Wakuma Masresha (MSc.) Page 119

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Definition 5.2: In a digraph, two or more arcs joining the same pair of vertices in the
same direction are multiple arcs. An arc joining a vertex to itself is a loop. A digraph
with no multiple arcs or loops is a simple digraph.

Example 5.2: digraph (a) below has multiple arcs and digraph (b) has a loop, so neither is
a simple digraph. Digraph (c) has no multiple arcs or loops, and is therefore a simple
digraph.

Adjacency and Incidence

The digraph analogues of adjacency and incidence are similar to the corresponding
definitions for graphs, except that we take account of the directions of the arcs.
Definition 5.3: The vertices � and � of a digraph are adjacent vertices if they are
joined (in either direction) by an arc �. An arc e that joins � to � is incident from v and
incident to �; � is incident to �, and � is incident from �.

Example 5.3: in the digraph below, the vertices � and � are adjacent, vertex � is
incident from arcs 2 and 5 and incident to arcs 3 and 4, and arc 6 is incident to (and
from) the vertex �.

By: Wakuma Masresha (MSc.) Page 120

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Isomorphism

It follows from the definition that a digraph is completely determined when we know
its vertices and arcs, and that two digraphs are the same if they have the same vertices
and arcs. Once we know the vertices and arcs, we can draw the digraph and, in
principle, any picture we draw is as good as any other; the actual way in which the
vertices and arcs are drawn is irrelevant - although some pictures are easier to use than
others!

We extend the concept of isomorphism to digraphs, as follows.

Definition 5.4: Two digraphs C and D are isomorphic if D can be obtained by

relabeling the vertices of C - that is, if there is a one-one correspondence between the
vertices of C and those of D, such that the arcs joining each pair of vertices in C agree
in both number and direction with the arcs joining the corresponding pair of vertices in
D.

Example 5.4: the digraphs C and D represented by the diagrams

are not the same, but they are isomorphic, since we can relabel the vertices in the
digraph C to get the digraph D, using the following one-one correspondence:

Note that arcs in C correspond to arcs in D - for example:

the two arcs from � to � in C correspond to the two arcs from 2 to 3 in D; the arcs
��and �� in C correspond to the arcs 41 and 14 in D; the loop �� in C corresponds to
the loop 44 in D.

By: Wakuma Masresha (MSc.) Page 121

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Sometimes it is unnecessary to have labels on the digraphs. In such cases, we omit the
labels, and refer to the resulting object as an ll1l1abelled digraph.
Example 5.5: The unlabelled digraph

corresponds to any of the following isomorphic digraphs:

We say that two unlabelled digraphs are isomorphic if labels can be attached to their
vertices so that they become the same digraph.

It is convenient to define a concept analogous to that of a subgraph of a graph.

Definition 5.5: A subdigraph of a digraph D is a digraph all of whose vertices are

vertices of D and all of whose arcs are arcs of D.

Remark 5.1: Note that D is a subdigraph of itself.

Example 5.6: The following digraphs are all subdigraphs of the digraph D on the left,
with vertices {�, �, �, �} and arcs {1, 2, 3, 4, 5, 6}.

By: Wakuma Masresha (MSc.) Page 122

 Discrete Mathematics And Combinatorics (Math 2052) 2016

The idea of a subdigraph can be extended to unlabelled digraphs.

Example 5.7: The following digraphs are all subdigraphs of the unlabelled digraph C
on the left:

It is also convenient to introduce the idea of the underlying graph of a digraph.

Definition 5.6: The underlying graph of a digraph D is the graph obtained by replacing
each arc of D by the corresponding undirected edge.

To obtain the underlying graph, we simply remove the arrows from the arcs.

Example 5.8:

We now give analogues of the degree of a vertex in a graph.

Definition 5.7: In a digraph, the out-degree of a vertex � is the number of arcs incident
from �, and is denoted by outdeg �; the in-degree of � is the number of arcs incident to
v, and is denoted by indeg �.

Remark 5.2: Each loop contributes 1 to both the in-degree and the out-degree of the
corresponding vertex.

Example 5.9: The digraph below has the following out-degrees and in-degrees:

By: Wakuma Masresha (MSc.) Page 123

 Discrete Mathematics And Combinatorics (Math 2052) 2016

outdeg � = 1 outdeg � = 3 outdeg � = 2

indeg � = 0 indeg � = 1 indeg � = 1
outdeg � = 0 outdeg � = 2 outdeg � = 2 indeg
�=0 indeg � = 6 indeg � = 2

There are also analogues of the degree sequence of a graph, corresponding to the
outdegree and in-degree of a vertex.

Definition 5.8: The out-degree sequence of a digraph D is the sequence obtained by

listing the out-degrees of D in increasing order, with repeats as necessary. The indegree
sequence of D is defined analogously.

Example 5.10: The above digraph has out-degree sequence (0, 1,2,2,2,3) and in-degree
sequence (0, 0, 1, 1, 2, 6).

Handshaking Dilemma

In the solution to Problem 4.10, you should have noticed that the sum of the outdegrees
and the SUI11 of the in-degrees of each digraph are both equal to the number of arcs. A
corresponding result holds for any digraph; we call it the handshaking dilemma!

Theorem 5.3( Handshaking Dilemma): In any digraph, the sum of all the out-degrees
and the sum of all the in-degrees are both equal to the number of arcs.

Proof: In any digraph, each arc has two ends, so it contributes exactly 1 to the sum of
the out-degrees and exactly 1 to the sum of the in-degrees. The result follows
immediately.

By: Wakuma Masresha (MSc.) Page 124

 Discrete Mathematics And Combinatorics (Math 2052) 2016

√ Check-List

Put a tick (√) mark if you can perform the task and a cross (x) mark if you can’t in the

box against the following questions.

1. Can you define a digraph? .........................................................................

2. Can you state Handshaking dilemma? .......................................................
3. Can you define isomorphic digraphs? ...............................................................
4. Can you distinguish the difference between in-degree and out-degree? .............

Exercise 5.1

1. Write down the vertices and arcs of each of the following digraphs. Are these digraphs
simple digraphs?

2. Which of the following statements hold for the digraph on the right?
a. vertices � and � are adjacent;
b. vertices � and � are adjacent;
c. vertex � is incident to arc 2;
d. arc 5 is incident from vertex �.

3. Draw the digraphs whose vertices and arcs are as follows. Are these digraphs simple
digraphs?
a. vertices: {�, �, �, �} arcs: {��, ��, ��, ��, ��}
b. vertices: {�, 2, 3, 4, 5,6,7,8} arcs: {�2,22,23,34,35,67,68,78}
4. By suitably labelling the vertices, show that the following unlabelled digraphs are
isomorphic:

By: Wakuma Masresha (MSc.) Page 125

 Discrete Mathematics And Combinatorics (Math 2052) 2016

5. By suitably relabelling the vertices, show that the following digraphs are isomorphic:

6. Are the following two digraphs isomorphic? If so, find a suitable one-one correspondence
between the vertices of the first and those of the second; if not, explain why no such oneone
correspondence exists.

7. Which of the following digraphs are subdigraphs of the digraph D below?

8. Which of the following digraphs are subdigraphs of the digraph C below?

9. Write down the out-degree and in-degree sequences of each of the following digraphs:

By: Wakuma Masresha (MSc.) Page 126

 Discrete Mathematics And Combinatorics (Math 2052) 2016

10. For each of the digraphs in Problem 9, write down:

a. the number of arcs;
b. the sum of the out-degrees of all the vertices;
c. the sum of the in-degrees of all the vertices.
d. What is the connection between your answers? Can you explain why this
connection arises?
11. Use the handshaking dilemma to prove that, in any digraph, if the number of vertices with
odd out-degree is odd, then the number of vertices with odd in-degree is odd.

5.2. Paths and Connectivity

Objectives: After studying this section, you should be able to:

 Explain the terms walk, trail, path, closed walk, closed trail, cycle, connected,
disconnected and strongly connected in the context of digraphs;
 explain the terms Eulerian digraph and Eulerian trail;
 state a necessary and sufficient condition for a connected digraph to be Eulerian;

By: Wakuma Masresha (MSc.) Page 127

 Discrete Mathematics And Combinatorics (Math 2052) 2016

 explain the terms Hamiltonian digraph and Hamiltonian Cycle;

Just as you may be able to get from one vertex of a graph to another by tracing the
edges of a walk, trail or path, so you may be able to get from one vertex of a digraph to
another by tracing the arcs of a 'directed' walk, trail or path. This means that you have
to follow the directions of the arcs as you go, just as if you were driving around a
oneway street system in a town. We make this idea precise, as follows.

Definition 5.9: A walk of length � in a digraph is a succession of � arcs of the form ��,
��, ��, ..., ��. This walk is denoted by ���� . . . ��, and is referred to as a walk from
� to �. A trail is a walk in which all the arcs, but not necessarily all the vertices, are
different. A path is a walk in which all the arcs and all the vertices are different.

Example 5.11: In the following diagram, the walk ���������� is a walk of length 9
from � to �, which includes the arc �� twice and the vertices �, �, � and � twice. The
walk ������ is a trail which is not a path, since the vertex � occurs twice, whereas the
walk ����� has no repeated vertices and is therefore a path.

The terms closed walk, closed trail and cycle also apply to digraphs.
Definition 5.10: A closed walk in a digraph is a succession of arcs of the form
��, ��, ��, . . . , ��, ��.
A closed trail is a closed walk in which all the arcs are different. A cycle is a closed trail
in which all the intermediate vertices are different.

In the digraph above, the closed walk ������� is a closed trail which is not a cycle
(since the vertex � occurs twice), whereas the closed trails ��, ���, ����� and
������� are all cycles. In describing closed walks, we can allow any vertex to be the
starting vertex. For example, the triangle ���� can also be written as ���� or ����.

By: Wakuma Masresha (MSc.) Page 128

 Discrete Mathematics And Combinatorics (Math 2052) 2016

As with graphs, we can use the concept of a path tell us whether or not a digraph is
connected. Recall that a graph is connected if it is 'in one piece', and this means that
there is a path between each pair of vertices. For digraphs these two ideas are not the
same, and this leads to two different definitions of the word connected for digraphs.

Definition 5.11: A digraph is connected if its underlying graph is a connected graph,

and is disconnected otherwise. A digraph is strongly connected if there is a path
between each pair of vertices.

Example 5.12: These three types of digraph are illustrated below:

Digraph (a) is disconnected, since its underlying graph is a disconnected graph.

Digraph (b) is connected but is not strongly connected since, for example, there is no
path from � to �. Digraph (c) is strongly connected, since there are paths joining all
pairs of vertices.

Alternatively, you can think of driving around a one-way street system in a town. If the
town is strongly connected, then you can drive from any part of the town to any other,
following the directions of the one-way streets as you go; if the town is merely
connected, then you can still drive from any part of the town to any other, but you may
have to ignore the directions of the one-way streets!

By: Wakuma Masresha (MSc.) Page 129

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Eulerian and Hamiltonian Digraphs

In Chapter 4, we discussed the problem of finding a route that includes every edge or
every vertex of a graph exactly once, and it is natural to consider the corresponding
problem for digraphs. This leads to the following definitions.

Definition 5.12: A connected digraph is Eulerian if it contains a closed trail that

includes every arc; such a trail is an Eulerian trail. A connected digraph is
Hamiltonian if it contains a cycle that includes every vertex; such a cycle is a
Hamiltonian cycle.

Example 5.13: Consider the following four digraphs:

digraph (a) is Eulerian - an Eulerian trail is ������������ and Hamiltonian - a

Hamiltonian cycle is ��������;
digraph (b) is Eulerian - an Eulerian trail is ������� it is not Han1iltonian;
digraph (c) is Hamiltonian - a Hamiltonian cycle is ��� � � � � it is not Eulerian;
digraph (d) is neither Eulerian nor Hamiltonian.

Much of the earlier discussion of Eulerian and Hamiltonian graphs can be adapted to
Eulerian and Hamiltonian digraphs. In particular, there is an analogue of Theorem 3.2.
We ask you to discover this analogue in the following problem.

Activity 5.1:

By: Wakuma Masresha (MSc.) Page 130

 Discrete Mathematics And Combinatorics (Math 2052) 2016

a. Guess a necessary and sufficient condition for a digraph to be Eulerian, involving the
in-degree and out-degree of each vertex.
b.Use the condition obtained in part (a) to check which of the digraphs in are Eulerian.

Theorem 5.4: A connected digraph is Eulerian if and only if, for each vertex, the
outdegree equals the in-degree.

Theorem 5.5: An Eulerian digraph can be split into cycles, no two of which have an
arc in common.

The proofs of these theoren1s are similar to those of Theorems 4.4 and 4.5. In the
sufficiency part of the proof of Theorem 5.4, the basic idea is to show that the digraph
contains a (directed) cycle, and then to build up the required Eulerian trail from cycles
step by step, as in the proof of Theorem 4.4. We omit the details. There is an analogue
of Ore's theoren1 for Hamiltonian graphs, but it is harder to state and prove than the
theorem for graphs, so we omit it.

√ Check-List
Put a tick (√) mark if you can perform the task and a cross (x) mark if you can’t in the

box against the following questions.

1. Can you define a walk in a digraph? .................................................................

2. Can you define Eulerian digraph and Eulerian trial? ...................................
3. Can you define Hamiltonian and Hamiltonian cycle? ....................................
Exercise 5.2

19. For the digraph on the right, write down:

a. all the paths from t to w;
b. all the paths from w to t;
c. a closed trail of length 8 containing t and z.
d. all the cycles containing both t and w.
20. Classify each of the following digraphs as disconnected, connected but not strongly
connected, or strongly connected:

By: Wakuma Masresha (MSc.) Page 131

 Discrete Mathematics And Combinatorics (Math 2052) 2016

21. Decide which of the following digraphs are Eulerian and/or Hamiltonian, and write down
an Eulerian trail or Hamiltonian cycle where possible.

5.3. Rooted Trees

Objectives: After studying this section, you should be able to:

 distinguish between physical and conceptual tree structures, and give examples
of each type;
 appreciate the uses of rooted trees in different areas;
 construct the bipartite graph representation of a given braced rectangular frame-
work and use it to determine whether the system is rigid; if so, determine
whether the system is minimally braced.

By: Wakuma Masresha (MSc.) Page 132

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Among the examples of tree structures, one particular type of tree occurs repeatedly.
This is the hierarchical structure in which one vertex is singled out as the starting point,
and the branches fan out from this vertex. We call such trees rooted trees, and refer to
the starting vertex as the root. For example, the tree representing the lines of
responsibility of a company is a rooted tree, with the managing director as the root.

A rooted tree is often drawn as follows, with the root indicated by a small square at the
top, and the various branches descending from it. When a path from the top reaches a
vertex, it may split into several new branches. Although a top-to-bottom direction is
often implied, we usually draw a rooted tree as a graph with undirected edges, rather
than as a digraph with arcs directed downwards. A rooted tree in which there are at
most two descending branches at any vertex is a binary tree.

Such trees are often called branching trees. We have already seen two instances of
branching trees - the family tree and the hierarchical tree. There are many further
examples, as we now show.

By: Wakuma Masresha (MSc.) Page 133

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Outcomes of Experiments

If we toss a coin or throw a die several times, then the possible outcomes can be
represented by a branching tree. In the case of tossing a coin, each possible outcome
has two edges leading from it, since the next toss may be a head (H) or a tail (T), and
we obtain a binary tree.

Example 5.13: if we toss a coin three times, then there are eight possible outcomes,
and we obtain the following branching tree.

Grammatical Trees
Branching trees occur in the parsing of a sentence in a natural language, such as
English. The tree represents the interrelationships between the words and phrases of the
sentence, and hence the underlying syntactic structure. Such a branching tree is
obtained by splitting the sentence into noun phrases and verb phrases, then splitting
these phrases into nouns, verbs, adjectives, and so on.
Example 5.14: The structure of the sentence Good students read books can be
represented by the following tree.

By: Wakuma Masresha (MSc.) Page 134

 Discrete Mathematics And Combinatorics (Math 2052) 2016

If a sentence is ambiguous, we can use branching trees to distinguish between the

different sentences constructions. For example, the newspaper headline Council rents
rocket can be interpreted in two ways, as illustrated by the following trees.

Computer Science

Rooted tree structures arise in computer science, where they are used to model and
describe branching procedures in programming languages (the languages used to write
algorithms to be interpreted by computers). In particular, they are used to store data in a
computer's memory in many different ways.
Example 5.15: Consider the list of seven numbers 7, 5, 4, 2, I, 6, 8. The following trees
represent ways of storing this list in the memory - as a stack and as a binary tree. Each
representation has its advantages, depending on how the data is to be manipulated, but
in both representations it is important to distinguish where the data starts, so the trees
are rooted trees.

By: Wakuma Masresha (MSc.) Page 135

 Discrete Mathematics And Combinatorics (Math 2052) 2016

We obtain the tree by writing the numbers in a string 7542168, 'promoting' every
second number (5, 2, 6) and then 'promoting' the new second number (2). √ Check-
List

Put a tick (√) mark if you can perform the task and a cross (x) mark if you can’t in the

box against the following questions.

1. Can you define a rooted tree? .................................................................

Exercise 5.3

1. Draw the branching tree representing the outcomes of two throws of a six-sided die.
2. The ambiguous sentence Help rape victims appeared as a newspaper headline l and can be
interpreted in two ways. Draw two tree structures that correspond to this sentence.

Chapter Summary

 A digraph consists of a set of elements called vertices and a set of elements

called arcs.
 In a digraph, two or more arcs joining the same pair of vertices in the same
direction are multiple arcs.
 An arc joining a vertex to itself is a loop.
 A digraph with no multiple arcs or loops is a simple digraph.
 The vertices � and � of a digraph are adjacent vertices if they are joined (in
either direction) by an arc �.

By: Wakuma Masresha (MSc.) Page 136

 Discrete Mathematics And Combinatorics (Math 2052) 2016

 An arc e that joins � to � is incident from v and incident to �; � is incident to �,

and � is incident from �.
 Two digraphs C and D are isomorphic if D can be obtained by relabeling the
vertices of C - that is, if there is a one-one correspondence between the vertices
of C and those of D.
 A subdigraph of a digraph D is a digraph all of whose vertices are vertices of D
and all of whose arcs are arcs of D.
 In a digraph, the out-degree of a vertex � is the number of arcs incident from �,
and is denoted by outdeg �;
 The in-degree of � is the number of arcs incident to v, and is denoted by indeg
�.
 Handshaking Dilemma states that in any digraph, the sum of all the out-degrees
and the sum of all the in-degrees are both equal to the number of arcs.
 A walk of length � in a digraph is a succession of � arcs of the form ��, ��,
��, ..., ��. This walk is denoted by ���� . . . ��, and is referred to as a walk
from � to �.
 A trail is a walk in which all the arcs, but not necessarily all the vertices, are
different.
 A path is a walk in which all the arcs and all the vertices are different.
 A closed trail is a closed walk in which all the arcs are different.
 A cycle is a closed trail in which all the intermediate vertices are different.
 A connected digraph is Eulerian if it contains a closed trail that includes every
arc; such a trail is an Eulerian trail.
 A connected digraph is Hamiltonian if it contains a cycle that includes every
vertex; such a cycle is a Hamiltonian cycle.
 The hierarchical structure in which one vertex is singled out as the starting point,
and the branches fan out from this vertex is called rooted trees.

Self Test Exercise 5

1. Consider the digraph D shown on the right. Which of the following statements hold for D?
a. vertices u and � are adjacent;

By: Wakuma Masresha (MSc.) Page 137

 Discrete Mathematics And Combinatorics (Math 2052) 2016

b. arc 2 is incident to vertex w;

c. vertex x is incident from arc 3;
d. vertex x and arc 7 form a subdigraph of D.

2. Of the following four digraphs, which two are the same, which one is isomorphic to these
two, and which is not isomorphic to any of the others?

3. Draw two non-isomorphic non-simple digraphs, each with 4 vertices and 7 arcs. Explain
why your digraphs are not isomorphic.
4. Write down the out-degree sequence and the in-degree sequence for each of the digraphs in
Exercise 2.
5. (a) If two digraphs have the same out-degree sequence and the same in- degree sequence,
must they be isomorphic?
(b) If two digraphs are isomorphic, must they have the same out-degree
sequence and the same in-degree sequence?
6. Draw a digraph with 4 vertices and 7 arcs such that the number of vertices with odd
outdegree is odd and the number of vertices with odd in-degree is odd.
7. For the digraph shown on the right, write down (if possible):
a. a walk of length 7 from � to �;
b. cycles of lengths 1, 2, 3 and 4;
c. a path of maximum length.

8. Draw four connected digraphs, D1, D2, D3 and D4, each with 5 vertices and 8 arcs,
satisfying the following conditions:
Dl is a simple digraph;
D2 is a non-simple digraph with no loops; D3 is a
digraph with both loops and multiple arcs; D4 is
strongly connected.
9. Classify each of the following digraphs as disconnected, connected but not strongly
connected, or strongly connected:

By: Wakuma Masresha (MSc.) Page 138

 Discrete Mathematics And Combinatorics (Math 2052) 2016

10. A graph is orientable if a direction can be assigned to each edge in such a way that the
resulting digraph is strongly connected. Show that K5 and the Petersen graph are
orientable, and find a graph that is not.

11. Are the following digraphs Eulerian? Hamiltonian?

12. In the digraph on the right, find:

a. all cycles of lengths 3, 4 and 5;
b. an Eulerian trail;
c. a Hamiltonian cycle.

REFERENCE

[1]. Anderson, A First Course in Discrete Mathematics,2002.

[2]. C. Berge, Graphs and Hypergraphs, North-Hoi Land Publishing
CompanyAmsterdam, 1976.
[3]. A. Bezdek, Discrete Geometry, Marcel Dekker, 2003.
[4]. N. L. Biggs, Discrete mathematics, Oxford University Press, 2002.
[5]. Eric W., "Discrete mathematics" from MathWorld.

By: Wakuma Masresha (MSc.) Page 139

 Discrete Mathematics And Combinatorics (Math 2052) 2016

[6]. Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction 5th
ed. Addison Wesley.
[7]. T. R. Hodkinson and J. A. N. Parnell, Reconstructing the Tree of Life: Taxonomy and
systematics of species rich taxa, CRC Press, 2007.
[8]. B. Hopkins, Resources for Teaching Discrete Mathematics, Mathematical
Association of America, 2008.
[9]. R. Johnsonbaugh, Discrete Mathematics, New Jersey, 2005.
[10]. R. Johnsonbaugh, Discrete Mathematics, Prentice Hall, 2008.
[11]. S. G. Krantz, Discrete Mathematics Demystified, McGraw-Hill, 2009.
[12]. B. Mohar and C. Thomassen, Graphs on Surfaces, Johns Hopkins University
press, 2001.
[13]. K.H. Rosen &J.G. Michaels, Handbook of Discrete and Combinatorial Mathematics,
CRC Press, 2000.
[14]. K. H. Rosen, Discrete Mathematics and Its Applications 6th ed. McGraw Hill.
[15]. R. J. Wilson, Introduction to Graph Theory, Longman, 1996.
[16]. D. B. West, Introduction to Graph Theory, 2005.

CHAPTER 6 MATRICES AND GRAPHS

Objectives: After studying this chapter, you should be able to:

 write down the adjacency matrix and incidence matrix of a given labelled graph
or digraph;
 draw the graph or digraph with a given adjacency or incidence matrix;
 use an adjacency matrix to determine the number of walks between two given
vertices in a graph or digraph;
 Utilize an adjacency matrix to determine whether a given graph/digraph is
connected/strongly connected;

By: Wakuma Masresha (MSc.) Page 140

 Discrete Mathematics And Combinatorics (Math 2052) 2016

 Illustrate the connections between adjacency matrices and problems in

archaeology and genetics;
 Illustrate the connections between adjacency matrices and Markov chains.
Introduction

Up to now, you have seen two ways of representing a graph or digraph - as a diagram
of points joined by lines, and as a set of vertices and a set of edges or arcs. The pictorial
representation is useful in many situations, especially when we wish to examine the
structure of the graph or digraph as a whole, but its value diminishes as soon as we
need to describe large or complicated graphs and digraphs. For example, if we need to
store a large graph in a computer, then a pictorial representation is unsuitable and some
other representation is necessary.

One possibility is to store the set of vertices and the set of edges or arcs. This method is
often used, especially when the graph or digraph is 'sparse', with many vertices but
relatively few edges or arcs. Another method is to take each vertex in turn and list those
vertices adjacent to it; by joining each vertex to its neighbours, we can reconstruct the
graph or digraph. Yet another method is to give a table indicating which pairs of
vertices are adjacent, or indicating which vertices are incident to which edges or arcs.

Each of these methods has its advantages, but the last one is particularly useful. Using
this method, we represent each graph or digraph by a rectangular array of numbers,
called a matrix. Such matrices lend themselves to computational techniques, and are
often the most natural way of formulating a problem. There are various types of matrix
that we can use to specify a given graph or digraph. Here we describe the two simplest
types - the adjacency matrix and the incidence matrix.

6.1 Adjacency Matrices

Objectives: After studying this topic, you should be able to:

 write down the adjacency matrix of a given labelled graph or digraph;
 draw the graph or digraph with a given adjacency matrix;
 use an adjacency matrix to determine the number of walks between two given
vertices in a graph or digraph;

By: Wakuma Masresha (MSc.) Page 141

 Discrete Mathematics And Combinatorics (Math 2052) 2016

 use an adjacency matrix to determine whether a given graph/digraph is

connected/strongly connected;
 describe the connections between adjacency matrices and problems in
archaeology and genetics;
 describe the connections between adjacency matrices and Markov chains.

Consider the following example:

On the left we have a graph with four labelled vertices, and on the right we have a
matrix with four rows and four columns - that is, a 4 � 4 matrix. The numbers
appearing in the matrix refer to the number of edges joining the corresponding vertices
in the graph. For example,

vertices 1 and 2 are joined by 1 edge, so 1 appears in row 1 column 2, and in row 2
column 1;
vertices 2 and 4 are joined by 2 edges, so 2 appears in row 2 column 4, and in row 4
column 2; vertices 1 and 3 are joined by 0 edges, so 0 appears in row 1 column 3, and
in row 3 column 1; vertex 2 is joined to itself by 1 edge, so 1 appears in row 2 column
2.

We generalize this idea, as follows.

Definition 6.1: Let G be a graph with n vertices labelled 1,2,3, . . . , �. The adjacency
matrix �( �) of G is the � � � matrix in which the entry in row � and column � is the
number of edges joining the vertices � and �.

The adjacency matrix of a graph is symmetrical about the main diagonal (top-left to
bottom-right). Also, for a graph without loops, each entry on the main diagonal is 0,

By: Wakuma Masresha (MSc.) Page 142

 Discrete Mathematics And Combinatorics (Math 2052) 2016

and the sum of the entries in any row or column is the degree of the vertex
corresponding to that row or column.

Example 6.1: For the graph

v1 e5 v4

e1 e3 e4

e6
e2
v2 v3

the adjacency matrix is

v1 v2 v3 v4
v1 0 1 0 1

v2 1 0 1 1
v3 0 1

2 v4

11 2

and the incidence matrix is

e1 e2 e3 e4 e5 e6
v1 1 0 0 0 1 0

v2 1 1 0 0 0 1 .

v3 0 1 1

1 0

0 v4 0

0 1 1

1 1

By: Wakuma Masresha (MSc.) Page 143

 Discrete Mathematics And Combinatorics (Math 2052) 2016

The representation of a graph by an adjacency matrix has a digraph analogue that is

frequently used when storing large digraphs in a computer. When defining the
adjacency matrix of a digraph, we have to take into account the directions of the arcs.

Consider the following example:

Example 6.2:

On the left we have a digraph with four labelled vertices, and on the right we have a
matrix with four rows and four columns. The numbers appearing in the matrix refer to
the number of arcs joining the corresponding vertices in the digraph. For example,

vertices 1 and 2 are joined (in that order) by 1 arc, so 1 appears in row 1 column 2;
vertices 2 and 4 are joined (in that order) by 2 arcs, so 2 appears in row 2 column 4;
vertices 4 and 1 are joined (in that order) by 0 arcs, so 0 appears in row 4 column 1;
vertex 2 is joined to itself by 1 arc, so 1 appears in row 2 column 2.

We generalize this idea, as follows.

Definition 6.2: Let D be a digraph with � vertices labelled. 1, 2, 3, . . . , �. The

adjacency matrix �(�) of D is the � � � matrix in which the entry in row � and column
� is the number of arcs from vertex � to vertex �.

The adjacency matrix of a digraph is not usually symmetrical about the main diagonal.
Also, if the digraph has no loops, then each entry on the main diagonal is 0, the sum of
the entries in any row is the out-degree of the vertex corresponding to that row, and the
sum of the numbers in any column is the in-degree of the vertex corresponding to that
column.

By: Wakuma Masresha (MSc.) Page 144

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Walks in Graphs and Digraphs

We can establish the existence of walks in a graph or digraph by using the adjacency
matrix. In the following, we restrict our attention to digraphs: similar results can be
derived for graphs.
Consider the following digraph and table:
Example 6.3:

The table shows the number of walks of length 1 between each pair of vertices. For
example, the number of walks of length 1 from a to c is 0, so 0 appears in row 1
column 3; the number of walks of length 1 from b to a is 1, so 1 appears in row 2
column 1; the number of walks of length 1 from d to b is 2, so 2 appears in row 4
column 2.

Now a walk of length 1 is an arc, so the table above is the adjacency matrix A of the
digraph:

Next, we consider walks of lengths 2 and 3. For example, there are two different walks
of length 2 from � to �, because there is one arc from a to � and two arcs from � to �.
Similarly, there are two different walks of length 3 from � to �, since there are two arcs
from d to b, and one walk of length 2 from � to d, namely, ���.

The solution to the above problem illustrates the following theorem;

Theorem 6.1: Let D be a digraph with � vertices labelled 1,2, . . . , �, let A be its
adjacency matrix with respect to this listing of the vertices, and let � be any positive

By: Wakuma Masresha (MSc.) Page 145

 Discrete Mathematics And Combinatorics (Math 2052) 2016

integer. Then the number of walks of length � from vertex � to vertex � is equal to the
entry in row � and column � of the matrix �� (the kth power of the matrix A).

Write down the adjacency matrix A, calculate the matrices A2 , A3 and A4 , and hence
find the numbers of walks of lengths 1, 2,3 and 4 from � to �. Are there walks of
lengths 1, 2, 3 or 4 from � to �?

Theorem 6.1 also gives a method of determining whether a digraph is strongly

connected, by working directly from its adjacency matrix.

Recall that a digraph is strongly connected if there is a path from vertex i to vertex j, for
each pair of distinct vertices i and j, and that a path is a walk in which all the vertices
are different. For example, in the digraph considered earlier, there are four vertices, so a
path has length 1, 2 or 3. We have seen that the numbers of walks (including the paths)
of lengths 1, 2 and 3 between pairs of distinct vertices are given by the non-diagonal
entries in the matrices

By examining these matrices, we can see that each pair of distinct vertices is indeed
joined by at least one path of length 1, 2 or 3, so the digraph is strongly connected.
However, we can check this more easily if we consider the matrix B obtained by adding
the three matrices together:

Let ��� denote the entry in row � and column � in the matrix B. Then each entry ��� is the
total number of walks of lengths 1, 2 and 3 from vertex � to vertex �. Since all the non-
diagonal entries are positive, each pair of distinct vertices is connected by a path, so the
digraph is strongly connected.

By: Wakuma Masresha (MSc.) Page 146

 Discrete Mathematics And Combinatorics (Math 2052) 2016

We generalize this result in the following theorem; the proof is given at the end of this
section.

Theorem 6.2: let D be a digraph with � vertices labelled 1,2, . . . , �, let A be its
adjacency matrix with respect to this listing of the vertices, and let B be the matrix

� = � + �2 + ⋯ + ��−1

Then D is strongly connected if and only if each non-diagonal entry in B is positive -

that is, ��� > 0 whenever � ≠ �.

Counting walks

Let A aij be the adjacency matrix of a graph G with vertex set {v1 ,v2 ,,vn}.
The

(i, j)th element of A2 is n

k a a and this is the number of walks of length 2 from vi
1 ik kj

to v j .

Example 6.4: If G is v1 v2

v3
v4 then
0 1 1 0 2 1 1 2

A 11101011 and A2 1 32 231 .

1 1

01 10 21 12

Hence, for example, the number of walks of length 2 from v2 to v3 is 2, and the number
of walks of length 2 from v2 to v2 is 3.

By: Wakuma Masresha (MSc.) Page 147

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Generally, for any positive integer r, the number of walks of length r from vi to vj is
given by the (i, j)th element of Ar .

√ Check-List

Put a tick (√) mark if you can perform the task and a cross (x) mark if you can’t in the

box against the following questions.

1. Can you define a adjacency matrix of a graph? ...........................................

2. Can you define a adjacency matrix of a digraph? ........................................
Exercise 6.1

1. Write down the adjacency matrix of each of the following graphs:

2. Draw the graph represented by each of the following adjacency matrices:

3. Write down the adjacency matrix of each of the following digraphs:

4. Draw the digraph represented by each of the following adjacency matrices:

By: Wakuma Masresha (MSc.) Page 148

 Discrete Mathematics And Combinatorics (Math 2052) 2016

5. Complete the following tables for the numbers of walks of lengths 2 and 3 in the above
digraph.

b. Find the matrix products A2 and A3 , where A is the adjacency matrix of the
above digraph.
c. Comment on your results.
6. Consider the following digraph:

7. Find B for the digraph in Problem 5.6, and hence determine whether the digraph is
strongly connected.
8. Determine whether the digraph with the following adjacency matrix is strongly connected:

6.2. Incidence Matrices

Objectives: After studying this topic, you should be able to:

By: Wakuma Masresha (MSc.) Page 149

 Discrete Mathematics And Combinatorics (Math 2052) 2016

 write down the incidence matrix of a given labelled graph or digraph;

 draw the graph or digraph with a given incidence matrix;
 use an incidence matrix to determine the number of walks between two given
vertices in a graph or digraph;

For convenience, in this section we restrict our attention to graphs all digraphs with out
loops.

Whereas the adjacency matrix of a graph or digraph involves the adjacency of vertices,
the incidence matrix involves the incidence of vertices and edges or arcs. To see what is
involved, consider the following example:

On the left we have a graph with four labelled vertices and six labelled edges, and on
the righ t we have a matrix with four rows and six columns. Each of the numbers
appearing in the matrix is 1 or 0, depending on whether the corresponding vertex and
edge are incident with each other. For example,

vertex ① is incident with edge 4, so 1 appears in row 1 column 4;

vertex ②is not incident with edge 4, so 0 appears in row 2 column 4.

We generalize this idea, as follows.

Definition 6.3: Let G be a graph without loops, with � vertices labelled ①, ②, ...,
and � edges labelled 1,2, 3, . . . , �. The incidence matrix I(G) of G is the n x m matrix
in which the entry in row � and column � is

By: Wakuma Masresha (MSc.) Page 150

 Discrete Mathematics And Combinatorics (Math 2052) 2016

In the incidence matrix of a graph without loops, each column contains exactly two 1s,
as each edge is incident with just two vertices; the sum of the numbers in a row is the
degree of the vertex corresponding to that row.

Whereas the adjacency matrix of a digraph involves the adjacency of vertices, the
incidence matrix of a digraph involves the incidence of vertices and arcs. Since an arc
can be incident from, incident to, or not incident with a vertex, we have to take account
of this when defining the matrix. To see what is involved, consider the following
example:

Example 6.5:

On the left we have a digraph with four labelled vertices and six labelled arcs, and on
the right we have a matrix with four rows and six columns. Each of the numbers
appearing in the matrix is 1, −1 or 0, depending on whether the corresponding arc is
incident from, incident to, or not incident with, the corresponding vertex. For example,

arc 4 is incident from vertex ①, so 1 appears in row 1 column 4;

arc 5 is incident to vertex ④, so -1 appears in row 4 column 5; arc
4 is not incident with vertex ②, so 0 appears in row 2 column 4.

We generalize this idea, as follows.

Definition 6.4: Let D be a digraph without loops, with n vertices labelled , , ...,
and arcs labelled . The incidence matrix I(D) of D is the matrix in
which the entry in row and column is

By: Wakuma Masresha (MSc.) Page 151

 Discrete Mathematics And Combinatorics (Math 2052) 2016

In the incidence matrix of a digraph without loops, each column has exactly one 1 and
one , since each arc is incident from one vertex and incident to one vertex; the
number of 1s in any row is the out-degree of the vertex corre- sponding to that row, and
the number of s in any row is the in-degree of the vertex corresponding to that row.

√ Check-List

Put a tick (√) mark if you can perform the task and a cross (x) mark if you can’t in the

box against the following questions.

3. Can you define a incidence matrix of a graph without loops? ..........................

4. Can you define a incidence matrix of a digraph without loops? .......................
Exercise 6.2

1. Write down the adjacency matrix A for K5 . By working out A3 determine

a. the number of walks of length 3 from a vertex u to a distinct vertex v;

b. the number of triangles (i.e. cycles of length 3).
2. Write down the incidence matrix of each of the following graphs:

3. Draw the graph represented by each of the following incidence matrices:

4. Write down the incidence matrix of each of the following digraphs:

By: Wakuma Masresha (MSc.) Page 152

 Discrete Mathematics And Combinatorics (Math 2052) 2016

5. Draw the digraph represented by each of the following incidence matrices:

Chapter Summary

 The adjacency matrix for a loopless graph G is the n n matrix whose ijth

element is the number of edges joining vi to v j .

 The adjacency matrix of a directed graph D is the matrix in which

the entry in row and column is the number of arcs from vertex to vertex .
 The incidence matrix of a loopless graph G is the n m matrix whose ijth

element is 1 if vi is incident with e j and 0 otherwise.

 The incidence matrix I(D) of a digraph D is the matrix in which the entry
in row and column is

Self Test Exercise 6

1. (a) Write down the adjacency and incidence matrices for the following graph:

v
e1 e2
e
e5

v2
v3 e6

(b) Draw the graph with the adjacency matrix

By: Wakuma Masresha (MSc.) Page 153

 Discrete Mathematics And Combinatorics (Math 2052) 2016

01111

1 0 1 0 1
11000 .

10001 11
010

(c) Draw the graph with the incidence matrix

0001010

1011001
1100000 .

0110110 000
0101

2. Write down the adjacency matrices of the following graph and digraph.

3. Draw the graph corresponding to adjacency matrix (a) and the digraph corresponding to
adjacency matrix (b).

4. The following matrix is the adjacency matrix of a graph G.

By: Wakuma Masresha (MSc.) Page 154

 Discrete Mathematics And Combinatorics (Math 2052) 2016

Which three of the following statements are TRUE?

(a) G is connected; (b) G is regular;
(c) G is bipartite; (d) G is a tree; (e)
G is Eulerian; (f) G is Hamiltonian.
5. Consider the following digraph:

Write down the adjacency matrix A, calculate the matrices A2, A3 and A4, and hence find
the numbers of walks of lengths 1, 2, 3 and 4 from � to �. Is there a walk of length 1, 2, 3
or 4 from � to �?
6. Write down the incidence matrices of the following graph and digraph.

7. Draw the digraph whose incidence matrix is

8. The following matrix is the incidence matrix of a graph G. What is the adjacency matrix of
G with the same labelling?

By: Wakuma Masresha (MSc.) Page 155

 Discrete Mathematics And Combinatorics (Math 2052) 2016

REFERENCE

[1]. C. Berge, Graphs and Hypergraphs, North-Hoi Land Publishing

CompanyAmsterdam, 1976.
[2]. A. Bezdek, Discrete Geometry, Marcel Dekker, 2003.
[3]. N. L. Biggs, Discrete mathematics, Oxford University Press, 2002.
[4]. Eric W., "Discrete mathematics" from MathWorld.
[5]. Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction 5th
ed. Addison Wesley.
[6]. T. R. Hodkinson and J. A. N. Parnell, Reconstructing the Tree of Life: Taxonomy and
systematics of species rich taxa, CRC Press, 2007.
[7]. B. Hopkins, Resources for Teaching Discrete Mathematics, Mathematical
Association of America, 2008.
[8]. R. Johnsonbaugh, Discrete Mathematics, New Jersey, 2005.
[9]. R. Johnsonbaugh, Discrete Mathematics, Prentice Hall, 2008.
[10]. S. G. Krantz, Discrete Mathematics Demystified, McGraw-Hill, 2009.
[11]. B. Mohar and C. Thomassen, Graphs on Surfaces, Johns Hopkins University
press, 2001.
[12]. K.H. Rosen &J.G. Michaels, Handbook of Discrete and Combinatorial Mathematics,
CRC Press, 2000.

[13]. K. H. Rosen, Discrete Mathematics and Its Applications 6th ed. McGraw Hill.
[14]. R. J. Wilson, Introduction to Graph Theory, Longman, 1996.
[15]. D. B. West, Introduction to Graph Theory, 2005.

By: Wakuma Masresha (MSc.) Page 156

 Discrete Mathematics And Combinatorics (Math 2052) 2016

By: Wakuma Masresha (MSc.) Page 157