Discrete Mathematics and Graph Theory - Module 1

Problem Sheet 1
Problems on propositions and truth tables

1. Find the negation of the following propositions:

(a) Michael’s PC runs Linux.

(b) Vandana’s smartphone has at least 32 GB of memory.
(c) Linda is younger than Sanjay.
(d) John makes more money than Isabella.
(e) Moshe is taller than Monica.
(f) Abby is richer than Ricardo.
(g) The summer in Maine is hot and sunny.
(h) 2+1=3.
(i) Zach blocks e-mails and texts from Jennifer.
(j) Diane rode her bicycle 100 miles on Sunday.

2. Let p and q be the propositions ”Swimming at the New Jersey shore is allowed” and
”Sharks have been spotted near the shore”, respectively. Express each of these compound
propositions as an English sentence.

(a) ¬q
(b) p ∧ q
(c) ¬p ∨ q
(d) p → ¬q
(e) ¬q → p
(f) ¬p → ¬q
(g) p ↔ ¬q
(h) ¬p ∧ (p ∨ ¬q)

3. Let p, q and r be the propositions.

p : You have the flu.
q : You miss the final examination.
r : You pass the course.
Express each of these propositions as an English sentences.

(a) p → q
(b) ¬q ↔ r
(c) q → ¬r
(d) p ∨ q ∨ r
(e) (p → ¬r) ∨ (q → ¬r)
(f) (p ∧ q) ∨ (¬q ∧ r)

1
4. Let p and q be the propositions:
p : You drive over 65 miles per hour.
q : You get a speeding ticket.
Write these propositions using p and q and logical connectives.

(a) You do not drive over 65 miles per hour.

(b) You drive over 65 miles per hour, but you do not get a speeding ticket.
(c) You will get a speeding ticket if you drive over 65 miles per hour.
(d) If you do not drive over 65 miles per hour, then you will not get a speeding ticket.
(e) Driving over 65 miles per hour is sufficient for getting a speeding ticket.
(f) You get a speeding ticket, but you do not drive over 65 miles per hour.
(g) Whenever you get a speeding ticket, you are driving over 65 miles per hour

5. Let p, q and r be the propositions.

p : Grizzly bears have been seen in the area.
q : Hiking is safe on the trail.
r : Berries are ripe along the trail.
Write these propositions using p and q and logical connectives.

(a) Berries are ripe along the trail, but grizzly bears have not been seen in the area.
(b) Grizzly bears have not been seen in the area and hiking on the trail is safe, but berries are ripe
along the trail.
(c) If berries are ripe along the trail, hiking is safe if and only if grizzly bears have not been seen in
the area.
(d) It is not safe to hike on the trail, but grizzly bears have not been seen in the area and the berries
along the trail are ripe.
(e) For hiking on the trail to be safe, it is necessary but not sufficient that berries not be ripe along
the trail and for grizzly bears not to have been seen in the area.
(f) Hiking is not safe on the trail whenever grizzly bears have been seen in the area and berries are
ripe along the trail.

6. Construct a truth table for each of these compound propositions and state whether it is
valid, satisfiable or unsatisfiable.

(a) p ∧ ¬p
(b) (p → q) ∧ (¬p → q)
(c) (p ∨ ¬q) → q
(d) (p ∨ q) → (p ∧ q)
(e) (p → q) ↔ (¬q → ¬p)
(f) (p → q) → (q → p)
(g) p → (¬q ∨ r)
(h) (p → q) ∨ (¬p → r)
(i) (p ↔ q) ∨ (¬q ↔ r)
(j) ((p → q) → r) → s

2
 Discrete Mathematics and Graph Theory - Module 1
Problem Sheet 2
Problems on Logical equivalence and normal forms

1. Prove the following equivalences:

(a) ¬(p → q) ≡ p ∧ ¬q.

(b) (p ∧ q) ∨ (p ∧ ¬q) ≡ p.
(c) (p ∨ q) ∧ (p ∨ ¬q) ≡ p.
(d) ¬(p ↔ q) ≡ (p ∧ ¬q) ∨ (¬p ∧ q).
(e) (p ∨ q) ∧ (¬p ∧ (¬p ∧ q)) ≡ (¬p ∧ q).
(f) p → (q ∨ r) ≡ (p → q) ∨ (p → r).
(g) (p ∨ q) → r ≡ (p → r) ∧ (q → r).
(h) (¬p → ¬q) → (q → p) ≡ T .

2. Prove the following implications without using truth tables:

(a) (p ∧ q) ⇒ (p → q).
(b) (q → p) ⇒ ¬p → ¬q.
(c) p → q ⇒ p → (p ∧ q).
(d) (p → q) → q ⇒ p ∨ q.
(e) (q → (p ∧ ¬p)) → (r → (p ∧ ¬p)) ⇒ (r → q).

3. Find the DNF of the following statements:

(a) ¬(p → (q ∧ r)).

(b) (¬p → r) ∧ (p ↔ q).
(c) (q ∨ (p ∧ r)) ∧ ¬((p ∨ r) ∧ q).

4. Find the CNF of the following statements:

(a) ¬(p ∨ q) ↔ (p ∧ q).

(b) ¬((p ∨ ¬q) ∧ ¬r).
(c) q ∨ (p ∧ r) ∧ ¬((p ∨ r) ∧ q).

1
5. Find the PDNF and PCNF of the following statements using both truth tables and logical
laws:

(a) (¬p → q) ∧ (q ↔ p).

(b) (p ∧ q) ∨ (¬p ∧ q) ∨ (q ∧ r).
(c) (p ∧ ¬(q ∧ r) ∨ (p → q).
(d) (p ∧ q) ∨ (¬p ∧ q ∧ r).
(e) (p ∨ q) ∧ (r ∨ ¬p) ∧ (q ∨ ¬r).
(f) (p → (q ∧ r)) ∧ (¬p → (¬q ∧ ¬r)).

2
 Discrete Mathematics and Graph Theory - Module 1
Problem Sheet 3
Problems on Theory of Inference

1 Symbolize and Translate

1. Symbolize the statement ”Given any positive integer, there is a greater positive integer”
i) with the positive integers as universe of discourse.
ii) without the positive integers as universe of discourse.
2. Consider the universe of discourse as integers. We define the following predicates over integers. We
present logical statements below, which are in turn represented using quantifiers
• N (x) : x is a non-negative integer.
• E(x) : x is even
• O(x) : x is odd
• P (x) : x is prime
Using the given propositional function, transform the following statements into expressions with the
help of quantifiers.
(a) There exist an even integer
(b) Every integer is even or odd
(c) All prime integers are non-negative
(d) There is one and only one even prime
(e) Not all integers are odd
(f) Not all primes are odd
3. Find the symbolic form of the statement ”Some boys in this class are taller than all the girls” where
the universe of discourse is the set of all students of this class.
4. Let P (x) be the statement ”x spends more than five hours every weekday in class,” where the domain
for x consists of all students. Express each of these quantifications in English.
i) ∃xP (x)
ii) ∀xP (x)
iii) ∃x¬P (x)
iv) ∀x¬P (x)
5. Translate these statements into English, where C(x) is ”x is a comedian” and F (x) is ”x is funny”
and the domain consists of all people.
i) ∀x(C(x) → F (x))
ii) ∀x(C(x) ∧ F (x))
iii) ∃x(C(x) → F (x))
iv) ∃x(C(x) ∧ F (x))

1
2 Problems on Statement Calculus using Rules of Inference
1. Show that ¬p follows logically from the premises ¬(p ∧ ¬q), (¬q ∨ r) and ¬r.

2. Prove that p → q, q → ¬r, r, p ∨ (j ∧ s) =⇒ (j ∧ s).

3. Show that the statement r ∨ s can be derived from the premises (c ∨ d), (c ∨ d) → ¬h, ¬h → (a ∧ ¬b)
and (a ∧ ¬b) → (r ∨ s)

4. Show that p → s can be derived from the premises ¬p ∨ q, ¬q ∨ r, and r → s using the rule CP.

5. Derive (p → (q → s)) from the following premises p → (q → r), q → (r → s).

6. Prove that p → q, p → r, q → ¬r and p are inconsistent.

7. Use indirect method and show that p → q, q → r, p ∨ r implies the conclusion r.

8. Show that the following premises are inconsistent:

a.) If John misses many classes through illness then he fails high school.
b.) If John fails high school, then he is uneducated.
c.) If John reads a lot of books then he is not uneducated.
s.) John misses many classes through illness and reads a lot of books.

9. Use rules of inference to show that the hypotheses “If it does not rain or if it is not foggy, then the
sailing race will be held and the life saving demonstration will go on,” “If the sailing race is held, then
the trophy will be awarded,”. “The trophy was not awarded” imply the conclusion “It rained.”

10. Construct an argument using rules of inference to show that the hypotheses “Radha works hard”, “If
Radha works hard, then she is a dull girl”. “If Radha is a dull girl, then she will not get the job”
imply the conclusion “Radha will not get the job”.

3 Problems on Predicate Calculus using Rules of Inference

1. ∃ x (P (x) ∧ Q(x)) =⇒ ∃ x P (x) ∧ ∃ x Q(x)

2. Show that ∃ x M (x) follows logically from the premises ∀ x (H(x) → M (x)) and ∃ x H(x).

3. Show that the premises “A student in this class has not read the book”. “Everyone in this class passed
the first examination” imply the conclusion “Someone who passed the first examination has not read
the book”.

4. Prove that ∀ x ((P (x) → Q(x)), ∀ x ((R(x) → ¬Q(x)) =⇒ ∀ x ((R(x) → ¬P (x)).

5. Use indirect method to prove that the conclusion ∃zQ(z) follows from the premises
∀x(P (x) → Q(x)) and ∃yP (y).

6. Check the validity of the following arguments:

i) All integers are rational numbers. Some integers are powers of 2. Therefore, some rational
numbers are powers of 2.
ii) All lectures are determined. Anyone who is determined and intelligent will give a good lecture.
Claire is an intelligent lecturer. Therefore, Claire will give a good lecture.

2
 Discrete Mathematics and Graph Theory - Module 2
Problem Sheet 4
Algebraic Structures and Group codes

1. If S = N × N , the set of ordered pairs of positive integers with the operation ∗ defined by

(a, b) ∗ (c, d) = (ad + bc, bd)

and if f : (S, ∗) → (Q, +) is defined by f (a, b) = ab , show that f is a semigroup homomorphism.

2. Let X be any set. Then verify that P (x), the power set of X is a semigroup under the operation of
taking union of two sets.

3. Check whether the following is a group or not under the stated binary operation. If so, determine the
identity and inverse.

i) {−1, 1} under multiplication.

ii) {−1, 1} under addition.
iii) {−1, 0, 1} under addition.
iv) {10n|n ∈ Z} under addition.
 
a b
4. Check whether the set of all 2 × 2 matrices where a, b, c, d ∈ R is a group under matrix
c d
addition.
       
1 0 −1 0 1 0 −1 0
5. Check whether G = , , , is a group under matrix multiplication.
0 1 0 1 0 −1 0 −1
√
6. Check whether G = {a + b 2 : a, b ∈ Z} is a group under usual addition.
 
x x
7. Check whether the set of all matrices of the form where x ∈ R∗ is a group under matrix
x x
multiplication.

8. Determine all cosets of subgroup H = {1, a2 } of a group G = {1, a, a2 , a3 } under multiplication where
a4 = 1.


9. Find the order of every element of the group G = {1, −1, i, −i}, × , for which the identity element is
1.

10. If C is the semigroup of non-zero complex numbers under multiplication and R is the semigroup
of non-zero real numbers under multiplication, show that g : C → R, defined by g(z) = |z| is a
homomorphism.

11. Let (R∗ , ×) be the group of non-zero real numbers under usual multiplication and G = {1, −1} be the
group under usual multiplication. Let f : R∗ → G be defined by
(
1, if x > 0
f (x) =
−1, if x < 0

Then prove that f is a homomorphism.

1
   
a b
12. Let G = : a, b ∈ R be a group with respect to matrix addition and (C, +) be another
−b a
group. Check whetherthe following
 mapping f : (G, +) → (C, +) where C is the set of complex
a b
numbers, defined by f = a + ib, is a group homomorphism or not.
−b a
a+b
13. Let G = {a ∈ R | − 1 < a < 1} and ∗ be the binary operation defined on G such that a ∗ b = 1+ab ,
for all a, b ∈ G. Examine if (G, ∗) is a commutative group.

14. Check whether the following set is a group or not:

i) Set of all polynomials of degree less than or equal to 2 such that the polynomials are positive at
0.
ii) Set of all 2 × 2 matrices with real entries such that the trace of a matrix is equal to the sum of
the first row.

15. Check whether the following is a group homomorphism or not:

i) T : R2 → R2 such that T (x, y) = (2x, 0).

ii) T : R2 → R2 such that T (x, y) = (x, y + 1).

16. If the minimum distance between code words is (i) 3 and (ii) 5, how many errors can be detected
and how many errors can be corrected in each case?
 
1 0 1 0 0
17. Find the code words generated by the parity check matrix H = 1 1 0 1 0, when the encoding
0 1 0 0 1
2
function is e : B → B .5
 
1 0 0 1 1 0
18. Given the generator matrix, G = 0 1 0 0 1 1, corresponding to the encoding function e :
0 0 1 1 0 1
B 3 → B 6 , find the corresponding parity check matrix and use it to decode the following received
words and hence to find the original message:

111101, 100100, 111100, 010100.

2
 Discrete Mathematics and Graph Theory
Module 3 - Problem Sheet 5
Counting Techniques

Principle of Inclusion-Exclusion, Pigeonhole principle,

Permutation and Combination
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

Problems on Permutations
1. Suppose that the license plates of a certain state require 3 English letters followed by 4 digits.

a) How many different plates can be manufactured if repetition of letters and digits are
allowed?
b) How many plates are possible if only the letters can be repeated?
c) How many are possible if only the digits can be repeated?
d) How many are possible if no repetitions are allowed at all?

2. There are 6 MCQs is an examination. If the first 3 questions have 4 choices each and the next
three questions have 5 choices each, how many sequences of answers are possibles?

3. In how many ways can 8 papers in an examination be arranged so that the two mathematics
papers are not consecutive.

4. In how many ways can 6 students and 4 teachers be arranged in a row for a photograph if

i.) No two teachers are together

ii.) the teachers are all together?

5. A salesman at a computer store would like to display 5 models of personal computers, 4 models
of computer monitors and 3 models of keyboards. In how many ways can he arrange them in
a row if the items of the same kind are together?

6. A number of 4 different digits is formed by using the digits 1, 2, 3, 4, 5, 6, 7 in all possible ways.

i.) How many such numbers can be formed?

ii.) How many of them are greater than 3400?
iii.) How many of them are divisible by 2?
iv.) How many of them are divisible by 4?

1
 v.) How many of them are divisible by 25?

7. How many strings of six letters of the English alphabet contains

i.) exactly one vowel

ii.) at least one vowel

8. How many positive integers n can be formed using the digits 3, 4, 4, 5, 5, 6, 7 if x has to exceed
5000000?

9. Find the number of permutations of the letters of the word MATHEMATICS. Also find the
number of arrangements beginning and ending with the same letter?

10. The password for a computer system consists of eight distinct alphabetic characters. Find the
number of passwords possible that

i.) End in The string MATH

ii.) Begin with the string CREAM
iii.) Contain the word COMPUTER as s sub-string.

11. How many strings of eight English alphabets are there

i.) that contain no vowels, if letters can be repeated?

ii.) that contain no vowels, if letters cannot be repeated?
iii.) that start with a vowel, if letters can be repeated?
iii.) that start with a vowel, if letters cannot be repeated?

12. A man, a woman, a boy, a girl, a dog and a cat are walking down a long and winding road one
after the other.

a) In how many ways can this happen?

b) In how many ways can this happen if the dog comes first?
c) In how many ways can this happen if the dog immediately follows the boy?
d) In how many ways can this happen if the dog (and only the dog) is between the man and
the boy?

13. There are 3 identical red balls, 5 identical blue balls, and 2 identical green balls. In how many
different ways can these balls be arranged if the first ball must be blue?

14. How many different strings can be made by ordering the letters of the word SUCCESS?

15. How many permutations of {a, b, c, d, e, f, g} i) end with a? ii) begin with c? iii) begin with c
and end with a? iv) c and a occupy the end places?

16. How many permutations of the letters A, B, C, D, E, F, G contain i) the string BCD ii) the
string CF GA iii) the strings BA and GF iv) the strings ABC and DE.

17. Five boys and five girls are to be arranged around in a circular table for a discussion so that
the boys and girls alternate. In how many ways can they be seated?

18. A rouond table conference is to be held between 10 delegates of 10 countries. In how many
ways can they be seated if

2
 (a) two particular delegates are always together
(b) two particular delegates are on either side of the chairperson.

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

Problems on Pigeonhole Principle

1. Seven members of a family have total Rs. 2886 in their pockets. Show that at least one of
them must have at least Rs. 413 in his pocket.

2. How many people must you have to guarantee that at least 9 of them will have birthdays in
the same day of the week.

3. If 9 colours are used to paint 100 houses, show that at least 12 houses will be of the same
colour.

4. A man hiked for 10 hours and covered a total distance of 45 km. It is known that he hiked 6
km in the first hour and only 3 km in the last hour. Show that he must have hiked at least 9
km within a certain period of 2 consecutive hours.

5. What is the minimum number of students, each of whom comes from one of the 50 states, who
must be enrolled in a university to guarantee that there are at least 100 who come from the
same state?

6. In a get-together party, every person present shakes the hand of every other person. If there
were 90 handshakes in all, how many persons were present at the party?

7. A bag contains beads of 2 colours: black and white. What is the smallest number of beads
which must be drawn from the bag, without looking, so that among these beads there are two
of the same colour.

8. Twenty five crates of apples are delivered to a store. The apples are of three different sorts,
and all the apples in each crate are of the same sort. Show that among these crates there are
at least nine containing the same sort of apples.

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

Problems on Principle of Inclusion-Exclusion

1. In a survey of 300 students, 64 had taken a Mathematics course, 94 had taken a English course,
58 had taken a Computer course, 28 had taken both Mathematics course and Computer course,
26 had taken both English and Mathematics course, 22 had taken both English and Computer
course, 14 had taken all the three courses.

a) How many students were surveyed who had taken none of the three courses?
b) How many had taken only a Computer course?

3
 2. In a survey of 200 musicians, it was found that 40 wore gloves on the left hand and 39 wore
gloves on the right hand. If 160 wore no gloves at all, how many wore a glove on only the right
hand? Only the left hand? On both hands?

3. A large software development company employs 100 computer programmers. Of them, 45 are
proficient in Java, 30 in C, 20 in Python, six in C and Java, one in Java and Python, five in
C and Python, and just one programmer is proficient in all three languages above. Determine
the number of computer programmers that are not proficient in any of these three languages.

4. How many positive integers not exceeding 1000 are divisible by 7 and 11?

5. There are 2500 students in a college of these 1700 have taken a course in C, 1000 have taken
a course in Pascal and 550 have taken a course in networking. Further 750 have taken course
in both C and Pascal, 400 have taken course in both C and Networking and 275 have taken
courses in both Pascal and networking. If 200 of these students have taken courses in C, Pascal
and networking,

i) How many of these 2500 students have taken a course in any of these courses C, Pascal
and networking?
ii) How many of these 2500 students have not taken any of these three courses C, Pascal and
networking?

6. In a survey of 270 college students, it is found that 64 like brussels sprouts, 94 like broccoli,
58 like cauliflower, 26 like both brussels sprouts and broccoli, 28 like both brussels sprouts and
cauliflower, 22 like both broccoli and cauliflower, and 14 like all three vegetables. How many
of the 270 students do not like any of these vegetables?

7. Finding the number of integers between 1 and 1000 both inclusive that are divisible by any of
the integers 5, 7, 11 and 13.

8. Find the number of integers between 100 and 1000 that are

i) divisible by 7
ii) not divisible by 7

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

Problems on Combinations
1. A candidate is required to answer 7 questions out of 12 questions which are divided into two
groups, each containing 6 questions. He is not permitted to attempt more than 5 questions
from either group. In how many ways can he choose the 7 questions?

2. From 7 women and 9 men a committee of 5 is to be formed. How many ways the selection can
be made if i) at least one woman must be on the committee. ii) at least one woman and one
man must be on the committee?

3. In how many ways can we form a software development group consisting of 1 project leader,
5 programmers and 6 data entry operators from a group of 5 project leaders, 20 programmers
and 25 data entry operators?

4. From a group of 12 workers, a group of 4 are to be selected for a two weeks training programme.

4
 i.) In how many ways four can be selected?
ii.) In how many ways four can be selected if two particular workers refuse to go together for
training?
iii.) In how many ways four can be selected if two particular workers want to be together?

5. A club has 25 members. a) How many ways are there to choose four members of the club to
serve on an executive committee? b) How many ways are there to choose a president, vice
president, secretary, and treasurer of the club, where no person can hold more than one office?

6. An urn contain 15 balls, 8 of which are red and 7 are black. In how many ways can 5 balls be
selected so that

i.) all are black

ii.) all are red
iii.) 2 are red and 3 are black

7. A committee of 3 persons is to be constituted from a group of 2 men and 3 women. In how

many ways can this be done? How many of these committees would consist of 1 man and 2
women?

8. Determine the number of 5 card combinations out of a deck of 52 cards, if there is exactly one
ace in each combination.

9. In a hand of poker, 5 cards are dealt from a regular pack of 52 cards

i.) What is the total possible number of hands if there are no restrictions?
ii.) In how many of these hands are there
a) 4 kings?
b) 2 clubs and 3 hearts?
c) all hearts?
d) all the same colour?

10. A group consists of 4 girls and 7 boys. In how many ways can a team of 5 members be selected
if the team has

i.) no girls
ii.) at least one boy and one girl
iii.) at least three girls

11. A basketball coach must select two attackers and two defenders from among three attackers
and five defenders. How many different combinations of attackers and defenders can he select?

12. In how many ways can 2 letters be selected from the set {a, b, c, d} when repetition of the letters
is allowed, if

a) the order of the letters matters

b) the order does not matter?

13. There are 3 piles of identical red, blue and green balls, where each pile contains at least 10
balls. In how many ways can 10 balls be selected:

5
 a) if there is no restriction?
b) if at least one red ball must be selected?
c) if at least one red ball, at least 2 blue balls and at least 3 green balls must be selected?
d) if exactly one red ball must be selected?
e) if exactly one red ball and at least one blue ball must be selected?
f) if at most one red ball is selected?
g) if twice as many red balls as green balls must be selected?

14. 5 balls are to be placed in 3 boxes. Each can hold all the 5 balls. In how many different ways
can we place the balls so that no box is left empty, if

a) balls and boxes are different?

b) balls are identical and boxes are different?
c) balls are different and boxes are identical?
d) balls as well as boxes are identical?

6
 Discrete Mathematics and Graph Theory - Module 3

Recurrence Relation Problems

1. What is the solution of the recurrence relation

an = an−1 + 2an−2 with a0 = 2 and a1 = 7?

2. What is the solution of the recurrence relation

an = 6an−1 − 9an−2

with initial conditions a0 = 1 and a1 = 6?

3. Find the solution to the recurrence relation

an = 6an−1 − 11an−2 + 6an−3

with initial conditions a0 = 2, a1 = 5 and a2 = 15.

4. Find the solution to the recurrence relation

an = −3an−1 − 3an−2 − an−3

with initial conditions a0 = 1, a1 = −2 and a2 = −1.

5. Find the explicit formula for the Fibonacci numbers.

6. Solve the recurrence relation

an = 5an−1 − 6an−2 , n ≥ 2

given a0 = 1, a1 = 4.

7. Solve the recurrence relation

an = 4an−1 − 4an−2 , n ≥ 2

with initial conditions a0 = 1, a1 = 4.

8. Solve the recurrence relation

an − 8an−1 + 21an−2 − 18an−3 = 0

9. Solve

an = an−1 + 2an−2 , n ≥ 2

with the initial conditions a0 = 0, a1 = 1.

10. Solve the recurrence relation

an = 2(an−1 − an−2 ); n ≥ 2

and a0 = 1, a1 = 2.

1
11. Solve the recurrence relation

an − 2an−1 = 2n , a0 = 2

12. Solve an − 3an−1 = 2n, a1 = 3.

13. Solve the recurrence relation

an − 5an−1 + 6an−2 = 8n2 , a0 = 4, a1 = 7.

14. Solve the recurrence relation

an+2 − 6an+1 + 9an = 3.2n + 7.3n

where n ≥ 0 and a0 = 1, a1 = 4.

15. Solve the recurrence relation

an = 6an−1 − 9an−2 + 4(n + 1).3n , where a0 = 2, a1 = 3.

16. Find all solutions of the recurrence relation

an = 3an−1 + 2n.

What is the solution with a1 = 3?

17. Find all solutions of the recurrence relation

an = 5an−1 − 6an−2 + 7n .

18. Solve the recurrence equation

ar − 7ar−1 + 10ar−2 = 2r

with initial condition a0 = 0 and a1 = 6.

19. Solve

an+2 − 5an+1 + 6an = 2

with initial conditions a0 = 1, a1 = −1.

2
 Discrete Mathematics and Graph Theory
Module 3
Recurrence Relation and Generating Functions

1. Solve the recurrence relation an+1 − an = 3n2 − n; n ≥ 0, a0 = 3 using characteristic root

method. [Soln.: an = 3 + n(n − 1)2 ]

2. A particle is moving in the horizontal direction. The distance it travels in each second is equal
to two times the distance it travelled in the previous second. If ar denotes the position of the
particle in the rth second, determine ar , given that a0 = 3 and a3 = 10. [Soln.: ar = 2r + 2]

Solve the recurrence relation an = 4an−1# − 4an − 2 + (n + 1)2n using characteristic root method.
3. "
 
n3
2
Soln.: an = c1 + c2 n + n + 6 2n

4. Use the method of hgenerating function i the recurrence relation an = 3an−1 + 1; n ≥ 1,

 to solve
1 n+1
given that a0 = 1. Soln.: an = 2 3 −1
h i
n
5. Solve an+1 − 2an = 5; n ≥ 0 with a0 = 1. Soln.: an = 6(2 ) − 5
h i
n 2
6. Solve an − 2an−1 = 5; n ≥ 1 with a1 = 4. Soln.: an = 13(2 ) − 2(n + 4n + 6)
h i
1
7. Solve an+2 − 7an+1 − 8an = n(n − 1)2n Soln.: an = c1 8n + c2 (−1)n − 54
(3n2 − 5n + 1)2n

8. "
Use the method of generating function to solve the recurrence
# relation an+2 − 4an = 9n2 ; n ≥ 0.
 
Soln.: an = c1 2n + c2 (−1)n 2n − 3 n2 + 34 n + 20
9

method of generating function #to solve the recurrence relation un+1 − 3un = 7(2)n with
9. Use the "

u0 = 1. Soln.: un = −7(2)n + 8(3)n

10. Use the method of generating

" function to solve# the recurrence relation yn+2 − 6yn+1 + 5yn = 0

with y0 = 2 and y1 = 6. Soln.: yn = 1 + 5n

1
 Discrete Mathematics and Graph Theory
Module 4 - Problem Sheet 7
Lattices and Boolean Algebra

1. A relation R on Z is given by aRb iff a ≡ b(mod4). Verify that R is an equivalence relation.

2. Define a relation R on the set S of symmetric matrices as (A, B) ∈ R if and only if A = B T .

Show that R is an equivalence relation.

3. Show that a relation R defined on the set of real numbers R as (a, b) ∈ R if and only if |a| = |b|
is an equivalence relation.

4. Let R be the relation on the set of people such that xRy if x and y are people and x is older
than y. Check whether R is a partial ordering.

5. Which elements of the poset ({2, 4, 5, 10, 12, 20, 25}, |) are maximal, and which are minimal?

6. Show that the POSET (Z+ , ≤) where ≤ denotes divisibility, i.e a ≤ b if a | b is a Lattice.

7. Consider D200 and let the relation D be divisor on D200 . Find

a.) Draw the Hasse diagram for D200 with D.

b.) all lower bounds of 20 & 25
c.) Infimum of 20 & 25
d.) Supremum of 40 & 50
e.) Test whether it is a Lattice or not. If it is a lattice, check whether it is bounded or not.

8. Consider the POSET (P, ≤) given by the Hasse diagram. Test whether it is a Lattice.

9. Give an example of a POSET which is not a lattice.

10. Let R be a relation defined on a set S of people such that R = {(a, b) : a, b ∈ S and a is older than b}.
Is (S, R) a POSET? Also, check whether it is a lattice or not.

1
11. Test whether the Hasse diagram represents a Lattice.

12. Let D60 denote the set of divisors of 60 and the relation ≤ is defined as a ≤ b if a|b. Draw the
Hasse diagram of the POSET (P, ≤) an check whether it is a lattice.

13. In a Boolean algebra B, for all a, b, c ∈ B, prove that

i) b + a = c + a and b + a′ = c + a′ =⇒ b = c
ii) b.a = c.a and b.a′ = c.a′ =⇒ b = c

14. In a Boolean algebra, for any a, b ∈ B, prove that a + b′ = 1 if and only if a + b = a.

15. Prove that a.b′ = 0 iff a.b = a.

16. Simplify the Boolean expression a′ .b′ .c + a.b′ .c + a′ .b′ .c′ , using Boolean algebra identities.

17. Simplify the following Boolean expression using Boolean algebra: (x + y + xy)(x + z).

18. Find the Disjunctive normal forms of the following Boolean expression by f (x, y, z) = y ′ + [z ′ +
x + (yz)′ ](z + x′ y).

2
 Discrete Mathematics and Graph Theory
Module 5 - Tutorial sheet 8
Basics concepts of Graphs Till Graph Isomorphism

1. Construct two different 3-regular graphs on 6 vertices.

2. Find the number of vertices, the number of edges and the degree of each vertex in the following
undirected graphs. Verify also the handshaking theorem in each case.

3. For each of the following degree sequences, find if there exists a graph. In each case, either
draw a graph or explain why no graphs exists.
a.) 5, 4, 3, 2, 1, 1
b.) 3, 3, 3, 3, 2
c.) 1, 2, 3, 4, 4
d.) 3, 4, 3, 4, 3
4. Draw complete graphs on 6 vertices and compute the total number of edges in it.
5. Prove or disprove: All complete graphs are regular. Justify.
6. Represent the following graphs by adjacency matrices

1
 7. Draw the graphs represented by the following adjacency matrices.

8. Draw the graphs represented by the following incidence matrices.

9. Verify the handshaking theorem for each of the following graphs.

10. Examine whether the following pairs of graphs are isomorphic. If isomorphic, label the vertices
of the two graphs to show that their adjacency matrices are the same.

11. Examine whether the following pairs of graphs are isomorphic.

2
12. Find the complement of the graphs given in problem 11.

13. Examine whether the following pairs of graphs are isomorphic.

14. Give the adjacency matrices for the graphs in question number 13.

15. Examine whether the following pairs of graphs are isomorphic.

16. Give the incident matrices for the graphs in question number 15.

17. Find the incidence and adjacency matrices of the following graph. How do you interpret the
degree of the vertices from them?

3
18. Check whether the given graph below is planar or not. If yes, give the planar representation.

19. Check whether the given graph below G, H and W are planar or not. If yes, give the planar
representation.

20. Determine whether the given graph is planar. If so, draw it so that no edges cross.

4
 Discrete Mathematics and Graph Theory
Module 5 - Tutorial sheet 10
Connectivity, Eulerian, Hamiltonian and Dijkstra’s
Algorithm

∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗

1. Find all the cut vertices and cut edges of the given graph.

2. For each of these graphs, find κ(G), λ(G).

1
3. Determine whether the given graph has an Euler circuit. Construct such a circuit when one
exists. If no Euler circuit exists, determine whether the graph has an Euler path and construct
such a path if one exists.

4. Determine whether the given graph has a Hamilton circuit. If it does, find such a circuit. If it
does not, give an argument to show why no such circuit exists.

2
5. Determine whether the given graph has a Hamilton circuit. If it does, find such a circuit. If it
does not, give an argument to show why no such circuit exists.

6. Find an Euler path or an Euler circuit, if it exists in each of the three graphs. If it does not
exist, explain why?

7. Find a Hamiltonian path or a Hamiltonian circuit, if it exists in each of the three graphs. If it
does not exist, explain why?

8. Give an example of a graph which contains

(a) an Eulerian circuit that is also a Hamiltonian circuit

(b) an Eulerian circuit, but not a Hamiltonian circuit
(c) a Hamiltonian circuit, but not an Eulerian circuit
(d) neither an Eulerian circuit nor a Hamiltonian circuit.

9. Find an Euler path or an Euler circuit, if it exists in each of the three graphs. If it does not
exist, explain why?

3
10. Find an Euler path or an Euler circuit, if it exists in each of the three graphs. If it does not
exist, explain why?

11. Find a Hamiltonian path or a Hamiltonian circuit, if it exists, in each of the three graphs. If
it does not exist, explain why?

12. Find a Hamiltonian path or a Hamiltonian circuit, if it exists, in each of the three graphs. If
it does not exist, explain why?

4
 13. Use Dijkstra’s algorithm to find the shortest path between the indicated vertices in the weighted
graphs given below:

(a) From A to G

(b) From A to H

(c) From A to H

∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗∗

5
 Discrete Mathematics and Graph Theory
Module 5 - Tutorial sheet 11
Graph Colouring, Matching and Covering

∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗

1. Find the Chromatic number χ, Matching number M (G) and Vertex

′
Covering β and Edge Covering β numbers for the following graphs:

1
2
3
 2. Find the Chromatic Polynomial and Chromatic Number χ for the following
graphs:

∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗∗

4
 Discrete Mathematics and Graph Theory
Module 6 - Tutorial sheet 12
Trees, Spanning Trees, Binary Trees, Fundamental
circuits, Cut sets

∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗
1. Sketch the 11-vertex binary trees with minimum and maximum heights. Find
also the path length of both the trees.
2. Sketch the 9-vertex binary trees with minimum and maximum heights. Find
also the path lengths of both tress.
3. Sketch the 13-vertex binary trees with minimum and maximum heights. Find
also the path lengths of both trees.
4. Draw all the spanning trees of the graph given below:

5. Draw all the spanning trees of the graphs given below:

1
6. Use Prim’s and Kruskal’s algorithm to find a minimum spanning tree for the
weighted graph given here

7. Use Prim’s and Kruskal’s algorithm to find a minimum spanning tree for the
weighted graph given here

2
8. Use Prim’s and Kruskal’s algorithm to find a minimum spanning tree for the
weighted graph given here

9. Use Prim’s and Kruskal’s algorithm to find a minimum spanning tree for the
weighted graph given here

3
10. Find the Diameter, Radius and Central vertices for the following graphs:

11. List the order in which the nodes of the tree given are processed using preorder,
inorder and postorder traversal. Also, find the Diameter, Radius and Central
vertices.

4
12. List the order in which the nodes of the tree given are processed using preorder,
inorder and postorder traversal. Also, find the Diameter, Radius and Central
vertices.

13. List the order in which the nodes of the tree given are processed using preorder,
inorder and postorder traversal. Also, find the Diameter, Radius and Central
vertices.

Kindly refer Module 6 notes for tutorial questions on fundamental

cycles and fundamental cut sets.
∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗