Predicate Calculus

Learning objectives
•
Module 01, MAT2002//Discrete Mathematics and Graph Theory
Mathematics Division//School of Advanced Sciences and Languages// VIT Bhopal University

1
1 Introduction

2
Solved Examples from Past Examinations

1. (a) Check whether the compound proposition is tautology, contradiction, or

contingency.
(p ∨ q) → (q ∧ r) ↔ (p ∧ ¬r)
Solution: To determine if the compound proposition (p∨q) → (q∧r) ↔ (p∧¬r)
is a tautology, contradiction, or contingency, we need to construct a truth
table. Since there are three variables (p, q, and r), the table will have 23 = 8
rows.
p q r p ∨ q q ∧ r (p ∨ q) → (q ∧ r) ¬r p ∧ ¬r ↔
T T T T T T F F F
T T F T F F T T F
T F T T F F F F T
T F F T F F T T F
F T T T T T F F F
F T F T F F T F T
F F T F F T F F F
F F F F F T T F F
The final column contains both T and F values. Therefore, the proposition
is a contingency.
(b) Show that
(p ∧ q) ∧ (p → r) ∧ (q → r) → r
is a tautology without using truth tables.
Solution: To show that the proposition (p ∧ q) ∧ (p → r) ∧ (q → r) → r is a
tautology, we can use the laws of propositional logic to simplify the expres-
sion until it reduces to T (True).

((p ∧ q) ∧ (p → r) ∧ (q → r)) → r

≡ ((p ∧ q) ∧ (¬p ∨ r) ∧ (¬q ∨ r)) → r (Implication law a → b ≡ ¬a ∨ b)

≡ ¬ (p ∧ q) ∧ (¬p ∨ r) ∧ (¬q ∨ r) ∨ r (Implication law)

≡ ¬(p ∧ q) ∨ ¬(¬p ∨ r) ∨ ¬(¬q ∨ r) ∨ r (De Morgan’s law)

≡ (¬p ∨ ¬q) ∨ (p ∧ ¬r) ∨ (q ∧ ¬r) ∨ r (De Morgan’s law & Involution law ¬(¬a) ≡ a)

≡ (¬p ∨ ¬q) ∨ ((p ∨ q) ∧ ¬r) ∨ r (Distributive law)

≡ (¬p ∨ ¬q) ∨ ((p ∨ q ∨ r) ∧ (¬r ∨ r)) (Distributive law)

≡ (¬p ∨ ¬q) ∨ ((p ∨ q ∨ r) ∧ T ) (Tautology law ¬a ∨ a ≡ T )

≡ (¬p ∨ ¬q) ∨ (p ∨ q ∨ r) (Identity law)

≡ (¬p ∨ p) ∨ (¬q ∨ q) ∨ r (Associative & Commutative laws)

≡T ∨T ∨r (Tautology law)

≡T (Dominance law a ∨ T ≡ T )
Hence, ((p ∧ q) ∧ (p → r) ∧ (q → r)) → r is a tautology.

3
2. (a) Given the following two conditional statements:
1. “If a student studies hard, then they will pass the exam.”
2. “If a shape is a square, then it has four equal sides.”
For each statement, write the:
(i) Converse
(ii) Inverse
(iii) Contrapositive
Solution: 1. “If a student studies hard, then they will pass the exam."
Let, p: student studies hard, q: student passes exam. Then the given condi-
tional statement is written as p → q. Therefore,
(i) Converse q → p: If a student passes the exam, then they studied hard.
(ii) Inverse ¬p → ¬q: If a student does not study hard, then they will not
pass the exam.
(iii) Contrapositive ¬q → ¬p: If a student does not pass the exam, then they
did not study hard.
2. “If a shape is a square, then it has four equal sides."
Let, r: shape is square, s: shape has four equal sides. Then the given
conditional statement is written as r → s. Therefore,
(i) Converse s → r: If a shape has four equal sides, then it is a square.
(ii) Inverse ¬r → ¬s: If a shape is not a square, then it does not have four
equal sides.
(iii) Contrapositive ¬s → ¬r: If a shape does not have four equal sides, then
it is not a square.
(b) Use De Morgan’s law to find the negative of the following statement.
‘If it does not rain or if there is no traffic dislocation, then the sports day will
be held and the cultural program will go on.’
Solution: Let,
p : It rains
q : There is traffic dislocation
r : Sports day is held
s : Cultural program goes on

Given statement: (¬p ∨ ¬q) → (r ∧ s)

Negation: ¬[(¬p ∨ ¬q) → (r ∧ s)]
Using Implication law A → B ≡ ¬A ∨ B:

¬[(¬p ∨ ¬q) → (r ∧ s)] ≡ ¬[¬(¬p ∨ ¬q) ∨ (r ∧ s)]

Applying De Morgan’s law:

¬[¬(¬p ∨ ¬q) ∨ (r ∧ s)] ≡ (¬p ∨ ¬q) ∧ (¬r ∨ ¬s)

∴ Negation (¬p ∨ ¬q) ∧ (¬r ∨ ¬s): Either it does not rain or there is traffic
dislocation, and either the sports day is not held or the cultural program
does not go on.

4
3. (a) Prove that
(p → r) ∨ (q → r) ≡ (p ∧ q) → r.
(i) With truth table
(ii) Without truth table
Solution:
(i) Proof with truth table:

p q r p → r q → r LHS: (p → r) ∨ (q → r) p ∧ q RHS: (p ∧ q) → r
T T T T T T T T
T T F F F F T F
T F T T T T F T
T F F F T T F T
F T T T T T F T
F T F T F T F T
F F T T T T F T
F F F T T T F T

Since the truth values of LHS and RHS are same in all rows, the propo-
sitions are logically equivalent, i.e.,

(p → r) ∨ (q → r) ≡ (p ∧ q) → r

(ii) Proof without truth table:

To prove the equivalence, we apply the laws of propositional logic to the
Left-Hand Side (LHS):

LHS = (p → r) ∨ (q → r)
≡ (¬p ∨ r) ∨ (¬q ∨ r) (Implication law)
≡ (¬p ∨ ¬q) ∨ (r ∨ r) (Associative & Commutative laws)
≡ (¬p ∨ ¬q) ∨ r (Idempotent law)
≡ ¬(p ∧ q) ∨ r (De Morgan’s law)
≡ (p ∧ q) → r (Implication law)
= RHS

(b) Express the following propositions X, Y symbolically, and hence determine

whether X and Y are logically equivalent or not by using truth table.
X: If Alice is both smart and honest, then she is not intelligent.
Y : If Alice either smart or not intelligent, then she is not honest.
Solution: Let, p : Alice is smart
q : Alice is honest
r : Alice is intelligent

Symbolic Representation:
Proposition X: “If Alice is both smart and honest, then she is not intelligent.”

X : (p ∧ q) → ¬r

5
 Proposition Y : “If Alice either smart or not intelligent, then she is not hon-
est.”
Y : (p ∨ ¬r) → ¬q
Truth table comparison for propositions X and Y :

p q r p ∧ q ¬r X : (p ∧ q) → ¬r p ∨ ¬r ¬q Y : (p ∨ ¬r) → ¬q
T T T T F F T F F
T T F T T T T F F
T F T F F T T T T
T F F F T T T T T
F T T F F T F F T
F T F F T T T F F
F F T F F T F T T
F F F F T T T T T

Since the truth values of X and Y are not the same in all rows, the proposi-
tions are not logically equivalent, i.e.,

(p ∧ q) → ¬r 6≡ (p ∨ ¬r) → ¬q

4. (a) Discuss the consistency of the following statements:

• If RCB lose many matches, then they will not reach the final.
• If RCB do not reach the final, then they will not be champions.
• If RCB reach the final, then they will be champions.
• If Kohli scores a lot of runs, then RCB will be champions.
• RCB lose many matches and Kohli scores a lot of runs.
Solution: Let,
L : RCB lose many matches
F : RCB reach the final
C : RCB are champions
K : Kohli scores a lot of runs

Then the given statements are written as:

1. L → ¬F
2. ¬F → ¬C
3. F → C
4. K → C
5. L ∧ K

Now if we derive a contradiction by using the given statements, then they

are inconsistent.

6
 6. L Using 5 and Simplification
7. ¬F Modus Ponens using 1 and 6
8. ¬C Modus Ponens using 2 and 7
9. K Using 5 and Simplification
10. C Modus Ponens using 4 and 9
11. C ∧ ¬C Conjunction using 8 and 10
12. F Using 11 and Contradiction
∴ The statements are inconsistent.
(b) Prove that the premises
p → q, q → r, s →∼ r, and q ∧ s
are inconsistent.
Solution: To prove that the given premises are inconsistent, we derive a
contradiction.
1. q ∧ s Premise (Given)
2. q Using 1 and Simplification
3. s Using 1 and Simplification
4. q → r Premise (Given)
5. r Modus Ponens using 2 and 4
6. s →∼ r Premise (Given)
7. ∼ r Modus Ponens using 3 and 6
8. r∧ ∼ r Conjunction using 5 and 7
9. F 8 and Contradiction
∴ The premises are inconsistent.

5. (a) Show that t is a valid conclusion from the premises:

p → q, q → r, r → s, ∼ s, and p ∨ t.
Solution: The valid argument for deducing t from the given premises is
given as a sequence.
1. p −→ q Premise (Given)
2. q −→ r Premise (Given)
3. r −→ s Premise (Given)
4. ∼ s Premise (Given)
5. p ∨ t Premise (Given)
6. p −→ r Hypothetical Syllogism using 1 and 2
7. p −→ s Hypothetical Syllogism using 6 and 3
8. ∼ p Modus Tollens using 7 and 4
9. t Disjunctive Syllogism using 5 and 8
∴ The conclusion t is valid.

7
 (b) Prove that the following arguments are valid without using truth tables:
(i) p →∼ q, r → q, r ∴ ∼ p
(ii) p ∨ (q → p), ∼ p ∧ r ∴ ∼ q
Solution:
(i) The valid argument for deducing ∼ p from the given premises is given as
a sequence.
1. p −→∼ q Premise (Given)
2. r −→ q Premise (Given)
3. r Premise (Given)
4. q Modus Ponens using 2 and 3
5. ∼∼ q Using 4 and Involution law
6. ∼ p Modus Tollens using 1 and 5
∴ The conclusion ∼ p is valid.
(ii) The valid argument for deducing ∼ q from the given premises is given as
a sequence.
1. p ∨ (q −→ p) Premise (Given)
2. ∼ p ∧ r Premise (Given)
3. ∼ p Using 2 and Simplification
4. q −→ p Disjunctive Syllogism using 1 and 3
5. ∼ q Modus Tollens using 4 and 3
∴ The conclusion ∼ q is valid.

6. (a) Examine the validity of the following argument: “If the market is free then
there is no inflation. If there is no inflation then there are price controls.
Since there are price controls, therefore market is free."
Solution: Let,
p : The market is free
q : There is inflation
r : There are price controls
Symbolic Representation:
Given premises: p −→∼ q, ∼ q −→ r, r
Conclusion: p
From the given premises, the following can be deduced.
1. p −→∼ q Premise (Given)
2. ∼ q −→ r Premise (Given)
3. r Premise (Given)
4. p −→ r Hypothetical Syllogism using 1 and 2
But from r and p −→ r, we cannot conclude p. This is the fallacy of Affirming
the Conclusion.
Therefore, the argument is invalid.

8
 p r Premise 1: p −→ r Premise 2: r Conclusion: p
T T T T T
T F F F T
F T T T F (FAIL)
F F T F F

Table 1: Truth Table for Affirming the Conclusion

(b) You are about to leave for school in the morning and discover that you do
not have your glasses. You know the following statements are true:
a. If I was reading the newspaper in the kitchen, then my glasses are on
the kitchen table.
b. If my glasses are on the kitchen table, then I saw them at breakfast.
c. I did not see my glasses at breakfast.
d. I was reading the newspaper in the living room or I was reading the
newspaper in the kitchen.
e. If I was reading the newspaper in the living room, then my glasses are
on the coffee table.
Use the rules of inference to find where the glasses are.
Solution: Let,

K : I was reading the newspaper in the kitchen

L : I was reading the newspaper in the living room
T : My glasses are on the kitchen table
B : I saw my glasses at breakfast
C : My glasses are on the coffee table

Symbolic Representation:
Given statements: K −→ T , T −→ B, ∼ B, L ∨ K, L −→ C
Now apply rules of inference.

1. K → T Premise (Given)
2. T → B Premise (Given)
3. ∼ B Premise (Given)
4. L ∨ K Premise (Given)
5. L → C Premise (Given)
6. ∼ T Modus Tollens using 2 and 3
7. ∼ K Modus Tollens using 1 and 6
8. L Disjunctive Syllogism using 4 and 7
9. C Modus Ponens using 5 and 8

Therefore, the glasses are on the coffee table.

9
7. Show the validity of the following argument using the rule of conditional proof.
“If my program runs successfully then I will submit my project. I can appear
in the examination if I submit my project. Either my program runs successfully
or the computer crashes. Therefore, if the computer does not crash then I can
appear at the examination."
Solution: Let,
P : My program runs successfully
S : I submit my project
E : I can appear in the examination
C : The computer crashes

Symbolic Representation:
Given premises: P → S, S → E, (P ∧ ¬C) ∨ (¬P ∧ C)
Conclusion: ¬C → E
In conditional proof, we assume ¬C as an additional premise and try to derive
conclusion E.
Now apply rules of inference.

1. P → S Premise (Given)
2. S → E Premise (Given)
3. (P ∧ ¬C) ∨ (¬P ∧ C) Premise (Given)
4. ¬C Additional premise for conditional proof
5. P → E Hypothetical Syllogism using 1 and 2
6. ¬C ∨ P Using 4 and Addition
7. ¬(C ∧ ¬P ) Using 6, Involution law and De Morgan’s law
8. P ∧ ¬C Disjunctive Syllogism using 3 and 7
9. P Using 8 and Simplification
10. E Modus Ponens using 5 and 9

Hence, the argument is valid.

8. Write the following statements using nested quantifiers:

(i) Every street in the city has a house in which we can find a person who is
either rich or highly educated.
(ii) There is a room in Academic Building I where all the students of VIT Bhopal
can sing and dance.
(iii) Given any student in the campus, the student has a friend who has a job in
Pune.

Solution:

(i) Every street in the city has a house in which we can find a person who is
either rich or highly educated.

10
 Let,
S(x) : x is a street in the city
H(y, x) : y is a house on street x
P (z, y) : z is a person in house y
R(z) : z is rich
E(z) : z is highly educated


Symbolic form: ∀x S(x) → ∃y (H(y, x) ∧ ∃z (P (z, y) ∧ (R(z) ∨ E(z))))
(ii) There is a room in Academic Building I where all the students of VIT Bhopal
can sing and dance.
Let,
R(x) : x is a room in Academic Building I
S(y) : y is a student of VIT Bhopal
C(y, x) : student y can sing and dance in room x


Symbolic form: ∃x R(x) ∧ ∀y (S(y) → C(y, x))
(iii) Given any student in the campus, the student has a friend who has a job in
Pune.
Let,
S(x) : x is a street in the campus
F (x, y) : y is a friend of x
J(y) : y has a job in Pune


Symbolic form: ∀x S(x) → ∃y (F (x, y) ∧ J(y))

9. Translate each of these nested quantifications into an English statement that

expresses a mathematical fact. The domain in each case consists of all real
numbers.

(i) ∃x ∀y (x + y = y)


(ii) ∀x ∀y ((x ≥ 0) ∧ (y < 0)) → (x − y > 0)


(iii) ∃x ∃y ((x ≤ 0) ∧ (y ≤ 0)) ∧ (x − y > 0)


(iv) ∀x ∀y ((x 6= 0) ∧ (y 6= 0)) ↔ (xy 6= 0)

Solution:

(i) ∃x ∀y (x + y = y)
Translation: There exists a real number x such that for every real number
y, the sum of x and y equals y.
(Equivalently: There is a real number that is an additive identity in the set
of real numbers.)


(ii) ∀x ∀y ((x ≥ 0) ∧ (y < 0)) → (x − y > 0)
Translation: For every pair of real numbers x and y, if x is non-negative and
y is negative, then the difference x − y is positive.

11


(iii) ∃x ∃y ((x ≤ 0) ∧ (y ≤ 0)) ∧ (x − y > 0)
Translation: There exist non-positive real numbers x and y such that their
difference x − y is positive.


(iv) ∀x ∀y ((x 6= 0) ∧ (y 6= 0)) ↔ (xy 6= 0)
Translation: For all real numbers x and y, both x and y are non-zero if and
only if their product xy is non-zero.

10. Determine the truth value and negation of the following statements, where the
universal set is U = {1, 2, 3}:

(i) ∃a ∀b, a2 − 1 < b

(ii) ∀a ∃b, a2 + b2 < 17
(iii) ∀a ∀b, a2 + b2 < 15

Solution:

(i) Statement: ∃a ∀b, a2 − 1 < b

This statement asserts there exists at least one element a ∈ U such that for
every element b ∈ U , the inequality a2 − 1 < b holds.
• Let a = 1. Then a2 − 1 = 12 − 1 = 0.
• For b = 1: 0 < 1 (True)
• For b = 2: 0 < 2 (True)
• For b = 3: 0 < 3 (True)
Since the condition holds for a = 1, the statement is satisfied.
Truth Value: True
Negation: ¬(∃a ∀b, a2 − 1 < b) ≡ ∀a ∃b, a2 − 1 ≥ b
(ii) Statement: ∀a ∃b, a2 + b2 < 17
This statement asserts that for every a ∈ U , there is at least one b ∈ U such
that a2 + b2 < 17.
• If a = 1: Choose b = 1 =⇒ 12 + 12 = 2 < 17 (True)
• If a = 2: Choose b = 1 =⇒ 22 + 12 = 5 < 17 (True)
• If a = 3: Choose b = 1 =⇒ 32 + 12 = 10 < 17 (True)
The condition holds for every a.
Truth Value: True
Negation: ¬(∀a ∃b, a2 + b2 < 17) ≡ ∃a ∀b, a2 + b2 ≥ 17
(iii) Statement: ∀a ∀b, a2 + b2 < 15
This statement asserts that the sum of squares is less than 15 for every
possible pair (a, b).
• Counterexample: Let a = 3 and b = 3.
• a2 + b2 = 32 + 32 = 9 + 9 = 18.
• 18 < 15 is False.
Since at least one pair fails, the universal statement is false.
Truth Value: False
Negation: ¬(∀a ∀b, a2 + b2 < 15) ≡ ∃a ∃b, a2 + b2 ≥ 15

12
11. A doctor is analyzing a patient’s symptoms. Given the following premises:

• If a person has a fever, then they have a disease.

• If a person has chills, then they have a fever.
• Alice has chills.
• If a person has a disease, then they need medication.
• If a person needs medication, then they are not healthy.

Using predicate logic, prove that Alice is not healthy.

Solution: Let,
C(x) : x has chills
F (x) : x has fever
D(x) : x has a disease
M (x) : x needs medication
H(x) : x is healthy

Symbolic Representation:
Given premises : ∀x (F (x) → D(x)), ∀x (C(x) → F (x)), C(Alice), ∀x (D(x) → M (x)),
∀x (M (x) → ¬H(x))

Conclusion: ¬H(Alice)
Now apply rules of inference.

1. ∀x (F (x) → D(x)) Premise (Given)

2. ∀x (C(x) → F (x)) Premise (Given)
3. C(Alice) Premise (Given)
4. ∀x (D(x) → M (x)) Premise (Given)
5. ∀x (M (x) → ¬H(x)) Premise (Given)
6. C(Alice) → F (Alice) Universal Instantiation from 2
7. F (Alice) Modus Ponens using 3 and 6
8. F (Alice) → D(Alice) Universal Instantiation from 1
9. D(Alice) Modus Ponens using 7 and 8
10. D(Alice) → M (Alice) Universal Instantiation from 4
11. M (Alice) Modus Ponens using 9 and 10
12. M (Alice) → ¬H(Alice) Universal Instantiation from 5
13. ¬H(Alice) Modus Ponens using 11 and 12

Therefore, Alice is not healthy is a valid conclusion.

12. Verify the validity of the inference.

If one person is more successful than another, then he has worked harder to
deserve success. John has not worked harder than Peter. Therefore, John is not
successful than Peter.

13
Solution: Let,

S(x, y) : x is more successful than y

W (x, y) : x has worked harder than y to deserve success
j : John
p : Peter

Symbolic Representation:
Given premises: ∀x ∀y [S(x, y) → W (x, y)], ¬W (j, p)
Conclusion: ¬S(j, p)
Now apply rules of inference.

1. ¬W (j, p) Premise (Given)

2. ∀x ∀y [S(x, y) → W (x, y)] Premise (Given)
3. ∀y [S(j, y) → W (j, y)] Universal instantiation and 2
4. S(j, p) → W (j, p) Universal instantiation and 3
5. ¬S(j, p) Modus Tollens using 1 and 4

Hence, the argument is valid.

14
Exercises

1. Determine whether (p ∨ q) ∧ (¬p ∨ r) → (q ∨ r) is a tautology or contradiction using

laws of statement calculus. Mention all the laws properly in each steps.

2. Test the validity of the following argument. If I will select in IAS examination,
then I will not be able to go to London. Since, I am going to London, I will not
select in IAS examination.

3. Prove the validity of the following argument "If I get the job and work hard, then
I will get promoted. If I get promoted, then I will be happy. I will not be happy.
Therefore, I will not get the job or I will not work hard".

4. Show that ∼ p is a valid conclusion from the premises (p → q), (r → s), (q →

t), (s → u), ∼ (t ∧ u), and (p → r).

5. State the converse, inverse, and contrapositive of the following statement. ’A

positive integer is a prime only if it has no divisors other than 1 and itself.’

6. Write the contrapositive of the statement “(a, b) is related to (c, d) if a is related to

c or if a is equal to c, then b is related to d".

7. (a) "If a number is divisible by 10 , then the number ends in zero". Write
the given statement into symbolic form and then write contrapositive of the
statement.
(b) Prove or Disprove: (p ∧ q) ∧ (∼ (p ∨ q)) is a tautology.

8. Verify the validity of the following argument using inference rules: "If I take the
day off, it either rains or snows." "I took Tuesday off or I took Thursday off." "It
was sunny on Tuesday." "It did not snow on Thursday." Therefore, "It rained on
Thursday."

9. (a) Using truth table find whether the following expression is a tautology, con-
tradiction, or contingency:

(p ∨ q) → (p ∧ ¬q) ↔ (¬p ∨ q)

(b) Prove the following equivalence without using truth table:

(p → q) → (q → r) ≡ ¬q ∨ r

10. Show that (t ∧ s) can be derived from the premises p → q, q →∼ r, r, p ∨ (t ∧ s).

11. (a) Check whether the given compound proposition

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

is a tautology, contingency or contradiction. Justify your answer.

(b) State the converse, contrapositive and inverse of the following conditional
statement. "I will go to the beach whenever it is a sunny summer day."

15
12. (a) A university database has a table Students (Name, Course, Grade), where
Name represents the student’s name, Course represents the course the stu-
dent is enrolled in, and Grade represents the student’s grade in that course.
The university has the following policies:
(A) Every student must pass at least one course.
(B) If a student passes a course, they are eligible for the next level of that
course.
(C) A student is placed on academic probation if they pass fewer than two
courses.
Answer the following:
(i) Express all policies in symbolic form.
(ii) Negate all policy statements and provide their symbolic notation.
(b) Given the following premises:
(i) If a student studies consistently, they will understand the material.
(ii) If a student understands the material, they will pass the exam.
(iii) If a student does not pass the exam, they must retake the course.
(iv) Sofia studied consistently.
Can we logically conclude that Sofia does not have to retake the course? Is
the conclusion valid? Justify your answer.

13. (a) Check whether p ∨ (q ∧ r) and (p ∨ q) ∧ (p ∨ r) are logically equivalent?

(b) Prove without using truth table: ¬(p ↔ q) ≡ ¬p ↔ q.

14. Show that the premises “It is not sunny this afternoon and it is colder than
yesterday," “We will go swimming only if it is sunny," “If we do not go swimming,
then we will take a canoe trip," and “If we take a canoe trip, then we will be home
by sunset" lead to the conclusion “We will be home by sunset."

15. (a) Show that ¬r is a valid conclusion from the premises p → ¬q, r → p, q
(i) with truth table
(ii) without truth table.
(b) Write the English sentence using the logical expression.
“You cannot ride the roller coaster if you are under 4 feet tall unless you are
older than 16 years old."

16. (a) Without using the truth table show that

∼ (p ∨ q) ↔ (p ∧ q) ≡ (p ∨ q) ∧ (∼ p∨ ∼ q)

(b) Translate the statement ∀x (C(x) ∨ ∃y (C(y) ∧ F (x, y))) into English, where
C(x) : x has a computer and F (x, y) : x and y are friends, and the domain for
both x and y consists of all students in your school.

17. Determine the truth value of each of these statements, if the universe of dis-
course consists of all integers. In case of false value give a counter example.

16
 (i) ∃n n = −n2

(ii) ∀n n3 ≥ n

(iii) ∃n (n + 3 = 3n)

18. (a) Using the vocabulary Q(x) : x is a rational number, R(x) : x is a real number,
and L(x) : x is less than 2 , translate the following into English sentences:
(i) ∀x (Q(x) → R(x))
(ii) ∃x (¬Q(x) ∧ R(x))
(iii) ∀x (Q(x) ∧ L(x) → R(x) ∧ L(x))
(iv) ∀x (Q(x) ∧ L(x)) → ∀x (R(x) ∧ L(x)).
(b) Translate into logical expressions:
(i) Each person in this room is either a BTech student or an MSc student.
(ii) There is a student in this class room who speaks Hindi or English.

19. (a) Give the symbolic form of the following statements.

(i) Some men are genius.
(ii) For every x, there exists a y such that x2 + y 2 ≥ 200.
(iii) Given any positive integer, there is a greater positive integer.
(b) Test the validity of the following argument:
If two sides of a triangle are equal, then the opposite angles are equal. Two
sides of a triangle are not equal. Therefore, the opposite angles are not
equal.

20. Write the following statements using predicates and quantifiers also find their
negations

(i) Some of the hardworking students do not get passed.

(ii) No student completes homework but all get passed.

21. Let A = {1, 2, 3, 4, 5, 6}. Determine the truth value of each of the following:

(i) (∃x ∈ A) (x2 > 25)

(ii) (∃x ∈ A) (x + 6 > 12)
(iii) (∀x ∈ A) (x2 − x < 30)

22. Let the universe of discourse be the set of real numbers and define
x
P (x, y) : = 1.
y
What is the truth value of the following statements? Justify your answers.

(i) ∀x ∀y P (x, y)
(ii) ∀x ∃y P (x, y)
(iii) ∃x ∀y P (x, y)
(iv) ∃x ∃y P (x, y)

17
23. Let C(x, y) be the statement “x and y have chatted over the Internet,” where the
domain for the variables x and y consists of all students in your class. Use
quantifiers to express each of these statements.

(i) There are two students in your class who have not chatted with each other
over the Internet.
(ii) There is a student in your class who has chatted with everyone in your class
over the Internet.
(iii) There are at least two students in your class who have not chatted with the
same person in your class.
(iv) There are two students in the class who between them have chatted with
everyone else in the class.

24. Let C(x) be the statement “x has a cat,” let D(x) be the statement “x has a dog,”
and let F (x) be the statement “x has a ferret.” Express each of the following
statements in terms of C(x), D(x), F (x), quantifiers, and logical connectives.
Moreover, write the negative of each of the statements. Let the domain consist of
all students in your class.

(i) A student in your class has a cat, a dog, and a ferret.

(ii) All students in your class have a cat, a dog, or a ferret.
(iii) Some student in your class has a cat and a ferret, but not a dog.
(iv) No student in your class has a cat, a dog, and a ferret.

25. Let P (x) be the statement “x can speak Russian” and let Q(x) be the statement
“x knows the computer language C++.” Express each of these sentences in terms
of P (x), Q(x), quantifiers, and logical connectives. The domain for quantifiers
consists of all students at your school.

(i) There is a student at your school who can speak Russian and who knows
C++.
(ii) There is a student at your school who can speak Russian but who doesn’t
know C++.
(iii) Every student at your school either can speak Russian or knows C++.
(iv) No student at your school can speak Russian or knows C++.

26. Use predicate calculus to prove the following agreement. "Students who pass the
course do the homework or attend lectures. Bob did not attend every lecture.
Bob passed the course. Therefore, Bob must have done the homework."

27. Verify the validity of the following argument. “Every living thing is a plant or an
animal. John’s goldfish is alive and it is not a plant. All animals have hearts.
Therefore, John’s goldfish has a heart."

28. Show that the following argument is valid “One student in the class knows JAVA."
“Everyone who knows JAVA can get a high-paying job." Therefore “Someone in
this class can get a high-paying job."

18
 Module 2: Sets and Relations

Sets and Relations

• Sets

• Relations

• Types of Relations

• Partial Order Relations

• Equivalence Relations

• POSET

• Hasse Diagram

Hasse Diagram
A Hasse diagram is a mathematical diagram used to represent a partially ordered set (poset).
It simplifies a directed graph by removing redundant information like reflexive loops and
transitive edges.

Rules for Drawing

1. Bottom-to-Top: If a < b, then the element b is placed higher than a.

2. Covering Relation: An edge is drawn between a and b only if b covers a, meaning

there is no element c such that
a<c<b

3. No Loops: Reflexive relations (where an element relates to itself) are not shown.

1
Example: Factors of 12
Consider the set
A = {1, 2, 3, 4, 6, 12}
ordered by the divisibility relation (a | b).

• 1 is at the bottom because it divides all other numbers.

• 2 and 3 are placed above 1.

• 4 is placed above 2.

• 6 is placed above both 2 and 3.

• 12 is placed at the top, connected to 4 and 6.

There is no line from 1 to 4 because the relation is transitive:

1 | 2 and 2 | 4

imply
1|4

Examples of Hasse Diagrams

I. Divisibility Relations (a | b)
1. Factors of 6:
D6 = {1, 2, 3, 6}

2. Factors of 8:
D8 = {1, 2, 4, 8}

3. Factors of 12:
D12 = {1, 2, 3, 4, 6, 12}

4. Factors of 30:
D30 = {1, 2, 3, 5, 6, 10, 15, 30}

5. Factors of 60:
D60 = {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60}

6.
{2, 4, 8, 16, 32}

7.
{2, 3, 6, 12, 18, 36}

2
 8.
{2, 4, 5, 10, 12, 20, 25}

9. Factors of 24:
D24 = {1, 2, 3, 4, 6, 8, 12, 24}

10. Set of primes:

{2, 3, 5, 7}

II. Subset Inclusion Relations

These diagrams represent the power set of a set S, ordered by inclusion.

1. Power set of {1}:

{∅, {1}}

2. Power set of {a, b}:

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

3. Power set of {1, 2, 3}

4. Power set of {w, x, y, z}

III. Standard Numerical Order (≤)

1.
{1, 2, 3, 4, 5}

2.
{0, 2, 5, 10, 11, 15}

3.
{−3, −1, 0, 4}

IV. Product and Lexicographical Orders

1. Product order on
{1, 2} × {1, 2}
where
(a, b) ≤ (c, d)
if
a ≤ c and b ≤ d

3
 2. Lexicographical order on
{1, 2} × {1, 2}
where
(a, b) ≤ (c, d)
if
a<c
or
a = c and b ≤ d

3. Partitions of
{a, b, c}

4. Boolean Algebra B2

Key Definitions
• Maximal Element: An element x such that no element y exists with

x<y

• Minimal Element: An element x such that no element y exists with

y<x

• Greatest Element (Maximum): An element larger than every other element.

• Least Element (Minimum): An element smaller than every other element.

Examples with Extremal Elements

No. Set & Relation Elements Minimal(s) Maximal(s)

1 D6 {1, 2, 3, 6} 1 6
2 D8 {1, 2, 4, 8} 1 8
3 D12 {1, 2, 3, 4, 6, 12} 1 12
4 D30 {1, 2, 3, 5, 6, 10, 15, 30} 1 30
5 Power set of {a, b} {∅, {a}, {b}, {a, b}} ∅ {a, b}
6 Power set of {1, 2, 3} 8 subsets ∅ {1, 2, 3}
7 {2, 3, 5, 7} Disconnected dots 2, 3, 5, 7 2, 3, 5, 7
8 {2, 4, 8, 16} Chain 2 16
9 {3, 6, 9, 12} Tree-like 3 9, 12
10 {2, 4, 6, 8, 10} Branching 2 6, 8, 10

4
Exercise Questions
1. Let
A = {1, 2, 3}, B = {a, b}
Write the Cartesian product
A×B

2. Let
A = {1, 2, 3}
and
R = {(1, 1), (1, 2), (2, 2), (3, 3)}
Determine whether R is:

• Reflexive
• Symmetric
• Transitive

3. Find the inverse relation of

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

4. If
A = {1, 2, 3, 4}
and
aRb ⇐⇒ a < b
write all ordered pairs of R.

5. On integers Z,
aRb ⇐⇒ a − b is divisible by 3
Show whether the relation is:

• Reflexive
• Symmetric
• Transitive

6. On
A = {1, 2, 3, 4}
define
R = {(1, 1), (2, 2), (3, 3), (4, 4), (1, 3), (3, 1)}
Determine whether R is an equivalence relation.

5
 7. Let
aRb ⇐⇒ a − b is divisible by 4
Find:
[0], [1], [2], [3]

8. On
A = {1, 2, 3, 6}
define
aRb ⇐⇒ a | b
Check:

• Reflexive
• Antisymmetric
• Transitive

9. On
A = {1, 2, 3}
define
R = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)}
Is R a partial order relation?

10. Show that subset inclusion

⊆
on power set P (A) is a partial order relation.

11. Draw the Hasse diagram for

A = {1, 2, 3, 6, 12}
under divisibility.

12. Draw the Hasse diagram of

P ({a, b})
under inclusion relation.

13. Draw the Hasse diagram for

A = {1, 2, 4, 8, 16}
under divisibility.

6
 Lattices and Boolean algebra

• Lattice as POSET: Definition and Examples

• Distributive Lattice

• Boolean Algebra as Lattice

• Laws of Boolean Algebra

• Boolean Functions- Normal Forms

• Application of Boolean Algebra to Switching Circuits

Learning objectives
• Lattice as POSET & Core Structures Identify POSETs:

– Differentiate between partially ordered sets and totally ordered sets using
formal relational definitions.
– Construct Hasse Diagrams: Draw clear Hasse diagrams from a given partial
order relation without redundant transitive edges.
– Calculate Bounds: Find the maximal, minimal, greatest, least, upper, and
lower bounds of a subset within a POSET.

• Construct Truth Tables: Build accurate truth tables for any given Boolean func-
tion to evaluate all possible input combinations.

• Convert to Normal Forms: Transform standard Boolean functions into Disjunc-

tive Normal Form (DNF/SOP) and Conjunctive Normal Form (CNF/POS).

• Design Logic Gate Networks: Draw functional logic circuit diagrams using stan-
dard gates (AND, OR, NOT) directly from simplified Boolean functions.

Module 02, MAT3002//Applied Linear Algebra

Mathematics Division//School of Advanced Sciences and Languages// VIT Bhopal University

1
1 Introduction

Lattices and Boolean algebra are mathematical frameworks used to analyze order,
logic, and relationships between sets.

• Lattices deal with how elements are ranked, ordered, or bounded relative to one
another.

• Boolean Algebra uses binary logic (True/False, 1/0) to calculate and simplify
logical reasoning and electronic systems.

1.1 From POSET to Lattice

A POSET upgrades to a Lattice if, and only if, every pair of elements {a, b} has two
unique bounds:

• Meet (∧): The greatest lower bound (Infimum / Floor).

• Join (∨): The least upper bound (Supremum / Ceiling).

[Top Element] (Join / Supremum)

[A] [B]

[Bottom Element] (Meet / Infimum)

2 Upgrading to Boolean Algebra

Boolean algebra is a specialized, highly structured type of lattice. For a lattice to

qualify as a Boolean algebra, it must possess two additional properties:

• Distributive: The operations distribute over each other:

a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c) (1)

• Complemented: The lattice has a distinct top element (1) and bottom element
(0). Every element a must have a unique opposite element a0 such that:

a ∧ a0 = 0 and a ∨ a0 = 1 (2)

3 Real-World Applications

3.1 Set Theory

In any universal set, subset relationships (⊆) form a lattice. The Meet operation
behaves exactly like a set Intersection (∩), while the Join operation behaves exactly
like a set Union (∪).

2
3.2 Digital Electronics & Computing
Computer hardware processes data using switches that are either ON (1) or OFF (0).
Boolean algebra provides the mathematical language required to design, analyze, and
minimize these electronic circuits:

• A AND B =⇒ A ∧ b =⇒ AND Gate

• A OR B =⇒ A ∨ b =⇒ OR Gate

• NOT A =⇒ A0 =⇒ NOT Gate (Inverter)

4 Core Mathematical Axioms

Every Boolean algebra complies with the following foundational dual laws:

Table 1: Fundamental Laws of Boolean Algebra

Law Name Meet Form (∧) Join Form (∨)
Identity a∧1=a a∨0=a
Idempotent a∧a=a a∨a=a
Commutative a ∧ b = b ∧ a a∨b=b∨a
Associative (a ∧ b) ∧ c = a ∧ (b ∧ c) (a ∨ b) ∨ c = a ∨ (b ∨ c)
Domination a∧0=0 a∨1=1

3
 We considered some examples related to above these topics

Example 1. Find the complement of each element of (D42 , /). Also, prove that, in any
distributive lattice (S, ≤), the joint cancellation law holds, i.e., if a ∨ b = a ∨ c and
a ∧ b = a ∧ c then b = c. (VIT-2025-2026 MTE)
Solution: Complements in (D42 , /) and Cancellation Law
For complements of elements in D42 :
The set of divisors of 42 is D42 = {1, 2, 3, 6, 7, 14, 21, 42}. In the lattice (D42 , /), the meet
(∧) is defined as gcd(a, b) and the join (∨) is defined as lcm(a, b). An element b is a
complement of a if a ∧ b = 1 and a ∨ b = 42.

Element (a) Complement (a0 ) Reasoning

1 42 gcd(1, 42) = 1, lcm(1, 42) = 42
2 21 gcd(2, 21) = 1, lcm(2, 21) = 42
3 14 gcd(3, 14) = 1, lcm(3, 14) = 42
6 7 gcd(6, 7) = 1, lcm(6, 7) = 42
7 6 gcd(7, 6) = 1, lcm(7, 6) = 42
14 3 gcd(14, 3) = 1, lcm(14, 3) = 42
21 2 gcd(21, 2) = 1, lcm(21, 2) = 42
42 1 gcd(42, 1) = 1, lcm(42, 1) = 42

For Joint Cancellation Law

We have given a ∨ b = a ∨ c and a ∧ b = a ∧ c in a distributive lattice (S, ≤).
To prove that b = c.

b = b ∨ (b ∧ a) (By Absorption Law)

= b ∨ (a ∧ b)
= b ∨ (a ∧ c) (Given a ∧ b = a ∧ c)
= (b ∨ a) ∧ (b ∨ c) (By Distributive Law)
= (a ∨ c) ∧ (b ∨ c) (Given a ∨ b = a ∨ c)
= (a ∧ b) ∨ c (By Distributive Law)
= (a ∧ c) ∨ c (Given a ∧ b = a ∧ c)
=c (By Absorption Law)

Thus, b = c.

Example 2. Express the following function into its Sum of Product (SOP) / pdnf with-
out using truth table. (VIT-2024-2025 TEE)

(a) ((xy)0 z)0 ((x0 + z)(y 0 + z 0 ))0

(b) x + yz + xyz

4
 (c) xz 0 + y 0
Solution: Sum of Products (SOP) / PDNF

(a) Let F = ((xy)0 z)0 ((x0 + z)(y 0 + z 0 ))0

= [(xy)00 + z 0 ] · [(x0 + z)0 + (y 0 + z 0 )0 ] (De Morgan’s Law)
0 0
= (xy + z ) · (xz + yz)
= xyxz 0 + xyyz + z 0 xz 0 + z 0 yz
= xyz 0 + xyz + xz 0 + 0 (Since z 0 z = 0)
= xyz 0 + xyz + xz 0 (y + y 0 )
= xyz 0 + xyz + xyz 0 + xy 0 z 0
= xyz + xyz 0 + xy 0 z 0 (By Idempotent Law)
P
PDNF: m7 + m6 + m4 = (4, 6, 7)

(b) Let F = x + yz + xyz

= x(y + y 0 )(z + z 0 ) + (x + x0 )yz + xyz
= (xyz + xyz 0 + xy 0 z + xy 0 z 0 ) + (xyz + x0 yz) + xyz
= xyz + xyz 0 + xy 0 z + xy 0 z 0 + x0 yz
P
PDNF: m7 + m6 + m5 + m4 + m3 = (3, 4, 5, 6, 7)

(c) Let F = xz 0 + y 0
= xz 0 (y + y 0 ) + y 0 (x + x0 )(z + z 0 )
= (xyz 0 + xy 0 z 0 ) + (xy 0 z + xy 0 z 0 + x0 y 0 z + x0 y 0 z 0 )
= xyz 0 + xy 0 z 0 + xy 0 z + x0 y 0 z + x0 y 0 z 0
P
PDNF: m6 + m4 + m5 + m1 + m0 = (0, 1, 4, 5, 6)

Example 3. Construct the tables for ∧ and ∨ for the set of all divisors of 36 under the
relation of divisibility. Also show that it forms a lattice. (VIT-2024-2025 TEE)
Solution: Let D36 = {1, 2, 3, 4, 6, 9, 12, 18, 36}. Here, a ∧ b = gcd(a, b) and a ∨ b = lcm(a, b).
Meet Table (∧ or gcd)
∧ 1 2 3 4 6 9 12 18 36
1 1 1 1 1 1 1 1 1 1
2 1 2 1 2 2 1 2 2 2
3 1 1 3 1 3 3 3 3 3
4 1 2 1 4 2 1 4 2 4
6 1 2 3 2 6 3 6 6 6
9 1 1 3 1 3 9 3 9 9
12 1 2 3 4 6 3 12 6 12
18 1 2 3 2 6 9 6 18 18
36 1 2 3 4 6 9 12 18 36

5
Join Table (∨ or lcm)

∨ 1 2 3 4 6 9 12 18 36
1 1 2 3 4 6 9 12 18 36
2 2 2 6 4 6 18 12 18 36
3 3 6 3 12 6 9 12 18 36
4 4 4 12 4 12 36 12 36 36
6 6 6 6 12 6 18 12 18 36
9 9 18 9 36 18 9 36 18 36
12 12 12 12 12 12 36 12 36 36
18 18 18 18 36 18 18 36 18 36
36 36 36 36 36 36 36 36 36 36

It forms a Lattice, since a set forms a lattice if every pair of elements has a unique
greatest lower bound (meet) and a unique least upper bound (join). Since for any
a, b ∈ D36 , the operations gcd(a, b) and lcm(a, b) yield distinct elements that are also
members of D36 , it satisfies the definition and forms a lattice.

Example 4. Determine which of the following posets are lattice. (VIT-2024-2025

TEE)

Figure 1:

Solution: To determine which posets are lattices, we evaluate if every pair of elements
has a Least Upper Bound (LUB / Join) and a Greatest Lower Bound (GLB / Meet).

• I: Lattice. This is a distributive lattice (specifically, a product of two chains).

Every pair of elements has a unique supremum (LUB) and infimum (GLB).

• II: Lattice. This is a chain (1 < 2 < 3 < 4). All finite chains are lattices because
for any two elements, the larger element is the LUB and the smaller element is
the GLB.

• III: Not a Lattice. Look at elements a and b. They have two upper bounds, d and
e, but neither d nor e is strictly "least" (they are incomparable). Thus, LUB(a, b)
does not exist.

• IV: Not a Lattice. Look at elements d and c. They have no common upper bound
(there is no element located "above" both). Thus, LUB(d, c) does not exist.

6
Example 5. (a) Find the complements in the Lattice of c and d from Figure 2. (VIT-
2024-2025 MTE )

Figure 2:

(b) Cheek it is lattice or not which is shown in Figure 3. (VIT-2024-2025 MTE )

Figure 3:

Solution 5 (a): In a lattice with a total top element (e) and a bottom element (a), an
element x is a complement of y if:

LUB(x, y) = e and GLB(x, y) = a

• Complement of c: Notice that LUB(c, b) = e and GLB(c, b) = a. Therefore, b is the

complement of c.

• Complement of d: Notice that LUB(d, b) = e and GLB(d, b) = a. Therefore, b is

also the complement of d.

Solution 5 (b): This is the standard Hasse diagram for the diamond lattice.

• The bottom element is a.

• The top element is e.

• Every pair from the incomparable middle elements {b, c, d} has e as their LUB
and a as their GLB. Since every possible pair has a unique LUB and GLB, it
satisfies the definition of a lattice.

7
 The Hasse diagram represents the lattice L = D30 , which is the set of divisors of
30:
D30 = {1, 2, 3, 5, 6, 10, 15, 30}
under the partial order of divisibility (a | b).
For a subset S ⊆ L to be a sub-lattice, it must be closed under the meet and join
operations of the original lattice. In D30 , the operations are:

• Meet (∧): gcd(a, b)

• Join (∨): lcm(a, b)

Example 6. If L = D3 0 having the Hasse diagram which shown in figure 4.

(a) Check L1 = {1, 2, 3, 6} is sub-lattice or not.
(b) Check L2 = {1, 2, 5} is sub-lattice or not. (VIT-2024-2025 TEE)

Figure 4:

Solution 6 (a): Let us check the closure for all pairs in L1 :

• gcd(2, 3) = 1 ∈ L1

• lcm(2, 3) = 6 ∈ L1

• All other operations (e.g., between 1 or 6 and other elements) naturally yield
elements within the set.

Since L1 is closed under both meet and join, L1 is a sub-lattice.

Solution 6 (b): Let us check the join of 2 and 5:

2 ∨ 5 = lcm(2, 5) = 10

8
Since 10 ∈
/ L2 , the subset is not closed under the join operation.
Conclusion: L2 is not a sub-lattice.

Example 7. If L = D3 0 having the Hasse diagram which shown in figure

(a) Check L1 = {3, 6, 15, 30} is sub-lattice or not.
(b) Check L2 = {6, 15, 30} is sub-lattice or not. (VIT-2025-2026 TEE)

Figure 5:

Solution 7 (a): Let us check the operations for the non-comparable elements 6 and
15:

• Meet: 6 ∧ 15 = gcd(6, 15) = 3 ∈ L1

• Join: 6 ∨ 15 = lcm(6, 15) = 30 ∈ L1

All other operations between comparable elements yield elements already in the set
(e.g., gcd(3, 6) = 3, lcm(6, 30) = 30).
Since L1 is closed under both operations, L1 is a sub-lattice.

Solution 7 (b): Let us check the meet of 6 and 15:

6 ∧ 15 = gcd(6, 15) = 3

Since 3 ∈
/ L2 , the subset is not closed under the meet operation.
Conclusion: L2 is not a sub-lattice.

Example 8. Construct an input/output table for the following Boolean function: f (A, B, C) =
(A + B)C̄, also find the disjunctive normal form of the Boolean function. Hence to rep-
resent the logical expressions with min term. (VIT-2024-2025 TEE)
Solution: Step 1:

9
 A B C C̄ A+B f (A, B, C) = (A + B)C̄
0 0 0 1 0 0
0 0 1 0 0 0
0 1 0 1 1 1
0 1 1 0 1 0
1 0 0 1 1 1
1 0 1 0 1 0
1 1 0 1 1 1
1 1 1 0 1 0

Step 2: Disjunctive Normal Form (DNF): The Disjunctive Normal Form is the sum
of the minterms for which the output of the function is 1. From the truth table, the
function yields 1 for the following rows:

1. A = 0, B = 1, C = 0 =⇒ ĀB C̄

2. A = 1, B = 0, C = 0 =⇒ AB̄ C̄

3. A = 1, B = 1, C = 0 =⇒ AB C̄

Thus, the DNF is:

f (A, B, C) = ĀB C̄ + AB̄ C̄ + AB C̄
Step 3: Representation with Min terms Mapping the binary inputs to their decimal
equivalents (0102 = 2, 1002 = 4, and 1102 = 6), the expression can be written in min
term notation as: X
f (A, B, C) = m(2, 4, 6)

Example 9. (a) Determine the complement of the elements a and c from the given
below Figure 6.

Figure 6:

(b) Find the Boolean function of the following circuit and find its equivalent sim-
plified circuit of the given below figure 7. Also draw the simplified circuit. (VIT-
2025-2026 MTE)

10
 Figure 7:

Solution 9 (a):
In a bounded lattice, an element x is a complement of an element y if:

x∧y =0 (the least element) and x ∨ y = 1 (the greatest element)

From the provided Hasse diagram:

• The least element (0) is e.

• The greatest element (1) is f .

For element a: We look for an element x such that a ∧ x = e and a ∨ x = f .

• a∧b=e

• a∨b=f

Thus, the complement of a is b.

For element c: We look for an element x such that c ∧ x = e and c ∨ x = f .

• c ∧ e = e, but c ∨ e = c 6= f .

• c ∧ b = e, but c ∨ b = f holds. However, this is not a distributive lattice and

b is already a complement of a. Looking closely at the connections, there is
no single element that satisfies both the greatest lower bound and least upper
bound properties strictly as a unique complement for c.

Thus, the element c does not have a complement in this lattice.

Solution 9 (b): The given switching network consists of two main branches connected
in parallel between nodes B and L. We can represent parallel connections with addi-
tion (+) and series connections with multiplication (·).

• Top Branch: Two sub-circuits are connected in series.

– The first sub-circuit has switches p and q in parallel: (p + q)

– The second sub-circuit has switches p and t in parallel: (p + t)
– Combined expression for top branch: (p + q) · (p + t)

• Bottom Branch: Switch t is in series with a sub-circuit containing switches p, q,

and t all in parallel.

11
 – The sub-circuit expression: (p + q + t)
– Combined expression for bottom branch: t · (p + q + t)

Since the top and bottom branches are in parallel, we add their expressions. Thus,
the Boolean function representing the circuit is:

F (p, q, t) = [(p + q) · (p + t)] + [t · (p + q + t)] (3)

Simplifying the Boolean Function

We can simplify the function using the standard laws of Boolean algebra:

F = (p + q)(p + t) + t(p + q + t)

Apply the distributive law to the first term (p + y)(p + z) = p + yz, and distribute t in
the second term:

= (p + qt) + (tp + tq + t · t)

Since t · t = t:

= p + qt + pt + qt + t

Using the idempotent law, qt + qt = qt:

= p + pt + qt + t

Factor out t from the last three terms:

= p + t(p + q + 1)

Since 1 + anything = 1 in Boolean algebra, the entire term in the parentheses becomes
1:

= p + t(1)
=p+t

The equivalent simplified Boolean function is:

F =p+t (4)

Drawing the Simplified Circuit

The simplified function F = p+t indicates that the original complex network is logically
equivalent to a simple circuit with only two switches, p and t, connected in **parallel**.

+--- [ p ] ---+
B ----| |---- L
+--- [ t ] ---+

12
Example 10. Find the simpler network corresponding to the Boolean expression F (a, b, c) =
0 0 0 0
a.b.c + a.b .c + a .b .c (VIT-2022-2023 TEE)
Solution: The following steps are used

1. Observe that the first two terms (a · b · c and a · b0 · c) have common factors a and c.

F = (a · c)(b + b0 ) + a0 · b0 · c0

2. Apply the Complement Law:

F = (a · c)(1) + a0 · b0 · c0

3. Apply the Identity Law:

F = a · c + a0 · b0 · c0

The simplified Boolean expression is:

F (a, b, c) = ac + a0 b0 c0 (5)

+--- [ a ] ------[ c ]------------+

---B ---| |--- L
+--- [ a’ ] ---[ b’ ]---[ c’ ]---+

13
Exercises: Lattices and Boolean Algebra

Lattice as POSET
1. Let S = {1, 2, 3, 6, 12} be a set ordered by the divisibility relation (a ≤ b if a divides
b). Draw the Hasse diagram for the partially ordered set (S, ≤) and determine
whether it forms a lattice.

2. Let X = {a, b, c} and consider its power set P(X) ordered by subset inclusion (⊆).
Find the infimum (meet) and supremum (join) for the elements {a} and {b, c}.

Distributive Lattice
3. Prove that every chain (a totally ordered set) is a distributive lattice.

4. Show that the diamond lattice M3 (the five-element lattice containing a top el-
ement, a bottom element, and three mutually incomparable elements between
them) is not distributive.

Boolean Algebra as Lattice

5. Prove that in any Boolean algebra, the complement of every element is unique.

6. Let D30 = {1, 2, 3, 5, 6, 10, 15, 30} be the lattice of divisors of 30 under the divisibility
relation. Verify whether D30 constitutes a Boolean algebra.

Laws of Boolean Algebra

7. Using the algebraic laws of Boolean algebra (such as De Morgan’s laws and ab-
sorption laws), simplify the following expression:

A · (Ā + B) + B · (B + C)

8. Prove the Consensus Theorem algebraically:

X · Y + X̄ · Z + Y · Z = X · Y + X̄ · Z

Boolean Functions & Normal Forms

9. Find the Principal Disjunctive Normal Form (PDNF), also known as the Sum-of-
Minterms, for the Boolean function:

f (X, Y, Z) = (X + Y ) · (X̄ + Z)

Application to Switching Circuits

10. Design a switching circuit for a hallway light controlled by two separate switches
(one at the entrance and one at the exit) such that flipping either switch toggles
the state of the light. State its Boolean expression.

14
Problem 1:
Find the complement of each element of (D42 , /). Also, prove that, in any
distributive lattice (S, ≤), the joint cancellation law holds, i.e., if a ∨ b = a ∨ c
and a ∧ b = a ∧ c then b = c. (VIT-2025-2026 MTE)
Solution : Complements in (D42 , /) and Cancellation Law
For complements of elements in D42 :
The set of divisors of 42 is D42 = {1, 2, 3, 6, 7, 14, 21, 42}. In the lattice (D42 , /),
the meet (∧) is defined as gcd(a, b) and the join (∨) is defined as lcm(a, b). An
element b is a complement of a if a ∧ b = 1 and a ∨ b = 42.

Element (a) Complement (a0 ) Reasoning

1 42 gcd(1, 42) = 1, lcm(1, 42) = 42
2 21 gcd(2, 21) = 1, lcm(2, 21) = 42
3 14 gcd(3, 14) = 1, lcm(3, 14) = 42
6 7 gcd(6, 7) = 1, lcm(6, 7) = 42
7 6 gcd(7, 6) = 1, lcm(7, 6) = 42
14 3 gcd(14, 3) = 1, lcm(14, 3) = 42
21 2 gcd(21, 2) = 1, lcm(21, 2) = 42
42 1 gcd(42, 1) = 1, lcm(42, 1) = 42

For Joint Cancellation Law

We have given a ∨ b = a ∨ c and a ∧ b = a ∧ c in a distributive lattice (S, ≤).
To prove that b = c.

b = b ∨ (b ∧ a) (By Absorption Law)

= b ∨ (a ∧ b)
= b ∨ (a ∧ c) (Given a ∧ b = a ∧ c)
= (b ∨ a) ∧ (b ∨ c) (By Distributive Law)
= (a ∨ c) ∧ (b ∨ c) (Given a ∨ b = a ∨ c)
= (a ∧ b) ∨ c (By Distributive Law)
= (a ∧ c) ∨ c (Given a ∧ b = a ∧ c)
=c (By Absorption Law)

Thus, b = c.

1
Problem 2:
Express the following function into its Sum of Product (SOP) / pdnf without
using truth table. (VIT-2024-2025 TEE)
(a) ((xy)0 z)0 ((x0 + z)(y 0 + z 0 ))0
(b) x + yz + xyz

(c) xz 0 + y 0
Solution: Sum of Products (SOP) / PDNF

(a) Let F = ((xy)0 z)0 ((x0 + z)(y 0 + z 0 ))0

= [(xy)00 + z 0 ] · [(x0 + z)0 + (y 0 + z 0 )0 ] (De Morgan’s Law)
0 0
= (xy + z ) · (xz + yz)
= xyxz 0 + xyyz + z 0 xz 0 + z 0 yz
= xyz 0 + xyz + xz 0 + 0 (Since z 0 z = 0)
= xyz 0 + xyz + xz 0 (y + y 0 )
= xyz 0 + xyz + xyz 0 + xy 0 z 0
= xyz + xyz 0 + xy 0 z 0 (By Idempotent Law)
P
PDNF: m7 + m6 + m4 = (4, 6, 7)

(b) Let F = x + yz + xyz

= x(y + y 0 )(z + z 0 ) + (x + x0 )yz + xyz
= (xyz + xyz 0 + xy 0 z + xy 0 z 0 ) + (xyz + x0 yz) + xyz
= xyz + xyz 0 + xy 0 z + xy 0 z 0 + x0 yz
P
PDNF: m7 + m6 + m5 + m4 + m3 = (3, 4, 5, 6, 7)

(c) Let F = xz 0 + y 0
= xz 0 (y + y 0 ) + y 0 (x + x0 )(z + z 0 )
= (xyz 0 + xy 0 z 0 ) + (xy 0 z + xy 0 z 0 + x0 y 0 z + x0 y 0 z 0 )
= xyz 0 + xy 0 z 0 + xy 0 z + x0 y 0 z + x0 y 0 z 0
P
PDNF: m6 + m4 + m5 + m1 + m0 = (0, 1, 4, 5, 6)

2
Problem 3:
Construct the tables for ∧ and ∨ for the set of all divisors of 36 under the
relation of divisibility. Also show that it forms a lattice. (VIT-2024-2025
TEE)
Solution: Let D36 = {1, 2, 3, 4, 6, 9, 12, 18, 36}. Here, a ∧ b = gcd(a, b) and
a ∨ b = lcm(a, b).
Meet Table (∧ or gcd)

∧ 1 2 3 4 6 9 12 18 36
1 1 1 1 1 1 1 1 1 1
2 1 2 1 2 2 1 2 2 2
3 1 1 3 1 3 3 3 3 3
4 1 2 1 4 2 1 4 2 4
6 1 2 3 2 6 3 6 6 6
9 1 1 3 1 3 9 3 9 9
12 1 2 3 4 6 3 12 6 12
18 1 2 3 2 6 9 6 18 18
36 1 2 3 4 6 9 12 18 36

Join Table (∨ or lcm)

∨ 1 2 3 4 6 9 12 18 36
1 1 2 3 4 6 9 12 18 36
2 2 2 6 4 6 18 12 18 36
3 3 6 3 12 6 9 12 18 36
4 4 4 12 4 12 36 12 36 36
6 6 6 6 12 6 18 12 18 36
9 9 18 9 36 18 9 36 18 36
12 12 12 12 12 12 36 12 36 36
18 18 18 18 36 18 18 36 18 36
36 36 36 36 36 36 36 36 36 36
It forms a Lattice, since a set forms a lattice if every pair of elements has
a unique greatest lower bound (meet) and a unique least upper bound (join).
Since for any a, b ∈ D36 , the operations gcd(a, b) and lcm(a, b) yield distinct
elements that are also members of D36 , it satisfies the definition and forms a
lattice.

3
Problem 4:
Determine which of the following posets are lattice. (VIT-2024-2025 TEE)

Figure 1:

Solution: To determine which posets are lattices, we evaluate if every pair

of elements has a Least Upper Bound (LUB / Join) and a Greatest Lower
Bound (GLB / Meet).

• I: Lattice. This is a distributive lattice (specifically, a product of two

chains). Every pair of elements has a unique supremum (LUB) and infi-
mum (GLB).
• II: Lattice. This is a chain (1 < 2 < 3 < 4). All finite chains are
lattices because for any two elements, the larger element is the LUB and
the smaller element is the GLB.
• III: Not a Lattice. Look at elements a and b. They have two upper
bounds, d and e, but neither d nor e is strictly ”least” (they are incompa-
rable). Thus, LUB(a, b) does not exist.
• IV: Not a Lattice. Look at elements d and c. They have no common
upper bound (there is no element located ”above” both). Thus, LUB(d, c)
does not exist.

Problem 5:
(a) Find the complements in the Lattice of c and d from Figure 2. (VIT-
2024-2025 MTE )
Solution: In a lattice with a total top element (e) and a bottom element
(a), an element x is a complement of y if:

LUB(x, y) = e and GLB(x, y) = a

• Complement of c: Notice that LUB(c, b) = e and GLB(c, b) = a. There-

fore, b is the complement of c.
• Complement of d: Notice that LUB(d, b) = e and GLB(d, b) = a. There-
fore, b is also the complement of d.

4
 Figure 2:

Problem 5:
(b) Cheek it is lattice or not which is shown in Figure 3. (VIT-2024-2025
MTE )

Figure 3:

Solution: This is the standard Hasse diagram for the diamond lattice.

• The bottom element is a.

• The top element is e.
• Every pair from the incomparable middle elements {b, c, d} has e as their
LUB and a as their GLB. Since every possible pair has a unique LUB and
GLB, it satisfies the definition of a lattice.

The Hasse diagram represents the lattice L = D30 , which is the set of divisors
of 30:
D30 = {1, 2, 3, 5, 6, 10, 15, 30}
under the partial order of divisibility (a | b).
For a subset S ⊆ L to be a sub-lattice, it must be closed under the meet
and join operations of the original lattice. In D30 , the operations are:
• Meet (∧): gcd(a, b)

• Join (∨): lcm(a, b)

5
Problem 6:
If L = D3 0 having the Hasse diagram which shown in figure 4.
(a) Check L1 = {1, 2, 3, 6} is sub-lattice or not.
(b) Check L2 = {1, 2, 5} is sub-lattice or not. (VIT-2024-2025 TEE)

Figure 4:

Solution: (a) Let us check the closure for all pairs in L1 :

• gcd(2, 3) = 1 ∈ L1
• lcm(2, 3) = 6 ∈ L1
• All other operations (e.g., between 1 or 6 and other elements) naturally
yield elements within the set.
Since L1 is closed under both meet and join, L1 is a sub-lattice.
(b) Let us check the join of 2 and 5:

2 ∨ 5 = lcm(2, 5) = 10

Since 10 ∈
/ L2 , the subset is not closed under the join operation.
Conclusion: L2 is not a sub-lattice.

Problem 7:
If L = D3 0 having the Hasse diagram which shown in figure
(a) Check L1 = {3, 6, 15, 30} is sub-lattice or not.
(b) Check L2 = {6, 15, 30} is sub-lattice or not. (VIT-2025-2026 TEE)
Solution: (a) Let us check the operations for the non-comparable elements
6 and 15:
• Meet: 6 ∧ 15 = gcd(6, 15) = 3 ∈ L1
• Join: 6 ∨ 15 = lcm(6, 15) = 30 ∈ L1

6
 Figure 5:

All other operations between comparable elements yield elements already in the
set (e.g., gcd(3, 6) = 3, lcm(6, 30) = 30).
Since L1 is closed under both operations, L1 is a sub-lattice.
(b) Let us check the meet of 6 and 15:

6 ∧ 15 = gcd(6, 15) = 3

Since 3 ∈
/ L2 , the subset is not closed under the meet operation.
Conclusion: L2 is not a sub-lattice.

Problem 8:
Problem: Construct an input/output table for the following Boolean function:
f (A, B, C) = (A + B)C̄, also find the disjunctive normal form of the Boolean
function. Hence to represent the logical expressions with min term. (VIT-
2024-2025 TEE)
Solution: Step 1:
A B C C̄ A+B f (A, B, C) = (A + B)C̄
0 0 0 1 0 0
0 0 1 0 0 0
0 1 0 1 1 1
0 1 1 0 1 0
1 0 0 1 1 1
1 0 1 0 1 0
1 1 0 1 1 1
1 1 1 0 1 0

Step 2: Disjunctive Normal Form (DNF): The Disjunctive Normal Form is

the sum of the minterms for which the output of the function is 1. From the
truth table, the function yields 1 for the following rows:

7
 1. A = 0, B = 1, C = 0 =⇒ ĀB C̄
2. A = 1, B = 0, C = 0 =⇒ AB̄ C̄
3. A = 1, B = 1, C = 0 =⇒ AB C̄

Thus, the DNF is:

f (A, B, C) = ĀB C̄ + AB̄ C̄ + AB C̄

Step 3: Representation with Min terms Mapping the binary inputs to their
decimal equivalents (0102 = 2, 1002 = 4, and 1102 = 6), the expression can be
written in min term notation as:
X
f (A, B, C) = m(2, 4, 6)

Problem 9:
Determine the complement of the elements a and c from the given below Figure
6.

Figure 6:

(b) Find the Boolean function of the following circuit and find its equivalent
simplified circuit of the given below figure 7. Also draw the simplified circuit.
(VIT-2025-2026 MTE)

Figure 7:

8
 Solution: (a) In a bounded lattice, an element x is a complement of an
element y if:

x ∧ y = 0 (the least element) and x ∨ y = 1 (the greatest element)

From the provided Hasse diagram:

• The least element (0) is e.

• The greatest element (1) is f .
For element a: We look for an element x such that a ∧ x = e and a ∨ x = f .

• a∧b=e
• a∨b=f
Thus, the complement of a is b.
For element c: We look for an element x such that c ∧ x = e and c ∨ x = f .

• c ∧ e = e, but c ∨ e = c 6= f .
• c ∧ b = e, but c ∨ b = f holds. However, this is not a distributive lattice
and b is already a complement of a. Looking closely at the connections,
there is no single element that satisfies both the greatest lower bound and
least upper bound properties strictly as a unique complement for c.

Thus, the element c does not have a complement in this lattice.

(b) The given switching network consists of two main branches connected
in parallel between nodes B and L. We can represent parallel connections with
addition (+) and series connections with multiplication (·).

• Top Branch: Two sub-circuits are connected in series.

– The first sub-circuit has switches p and q in parallel: (p + q)
– The second sub-circuit has switches p and t in parallel: (p + t)
– Combined expression for top branch: (p + q) · (p + t)
• Bottom Branch: Switch t is in series with a sub-circuit containing switches
p, q, and t all in parallel.

– The sub-circuit expression: (p + q + t)

– Combined expression for bottom branch: t · (p + q + t)

Since the top and bottom branches are in parallel, we add their expressions.
Thus, the Boolean function representing the circuit is:

F (p, q, t) = [(p + q) · (p + t)] + [t · (p + q + t)] (1)

9
 Simplifying the Boolean Function
We can simplify the function using the standard laws of Boolean algebra:

F = (p + q)(p + t) + t(p + q + t)

Apply the distributive law to the first term (p+y)(p+z) = p+yz, and distribute
t in the second term:

= (p + qt) + (tp + tq + t · t)

Since t · t = t:

= p + qt + pt + qt + t

Using the idempotent law, qt + qt = qt:

= p + pt + qt + t

Factor out t from the last three terms:

= p + t(p + q + 1)

Since 1 + anything = 1 in Boolean algebra, the entire term in the parentheses

becomes 1:

= p + t(1)
=p+t

The equivalent simplified Boolean function is:

F =p+t (2)

Drawing the Simplified Circuit

The simplified function F = p + t indicates that the original complex network is
logically equivalent to a simple circuit with only two switches, p and t, connected
in **parallel**.

+--- [ p ] ---+
B ----| |---- L
+--- [ t ] ---+

Problem 10:
Find the simpler network corresponding to the Boolean expression F (a, b, c) =
0 0 0 0
a.b.c + a.b .c + a .b .c (VIT-2022-2023 TEE)

Solution:

10
 1. Observe that the first two terms (a · b · c and a · b0 · c) have common factors
a and c.
F = (a · c)(b + b0 ) + a0 · b0 · c0

2. Apply the Complement Law:

F = (a · c)(1) + a0 · b0 · c0

3. Apply the Identity Law:

F = a · c + a0 · b0 · c0

The simplified Boolean expression is:

F (a, b, c) = ac + a0 b0 c0 (3)

+--- [ a ] ------[ c ]------------+

---B ---| |--- L
+--- [ a’ ] ---[ b’ ]---[ c’ ]---+

11
 Graphs and its Matrix
Representation
• Problem set and solutions

• Excercise

Learning objectives
• We will apply the concepts of graph theory to real-life problems.
Module 04, MAT2002//Discrete Mathematics and Graph Theory
Mathematics Division//School of Advanced Sciences and Languages// VIT Bhopal University

1
1 Problem set and solutions

Question-1

How many edges are there in an undirected graph with 10 vertices each of degree 6?

Solution: Let us consider that e be the number edges in the graph G = (V, E), where V
is the set of all vertices of the graph G and E be the set of all edges of the same graph
G.
Then, by using the Handshaking Theorem, we can write
X
2e = deg(v)
v∈V

⇒ 2e = sum of the degrees of all the vertices

⇒ 2e = 10 × 6
⇒ 2e = 60
⇒ e = 30
Hence, there are 30 edges in the graph G.

Question-2

Determine whether the following graph is a bipartite graph.

a b

f c

e d

Solution: Yes, the graph is bipartite.

A graph is bipartite if its vertices can be divided into two separate sets (let’s call
them Set 1 and Set 2) such that every edge in the graph connects a vertex in Set 1 to
a vertex in Set 2. Importantly, there can be no edges connecting vertices within the
same set.
We can test if a graph is bipartite by trying to assign each vertex to one of the two
sets:

1. Start with vertex f : Place f into Set 1.

2
 2. Assign f ’s neighbors: Look at all the vertices connected to f . The graph shows
edges connecting f to a, b, e, and d. Because they share an edge with f , they
cannot be in the same set as f . Therefore, we place a, b, e, and d into Set 2.

3. Assign the remaining vertex: The only vertex left to assign is c.

4. Check c’s neighbors: Look at the edges connected to c. It is connected to a, b,

e, and d. Because all of its neighbors are currently in Set 2, vertex c must be
placed in Set 1.

• Set 1: {f, c}

• Set 2: {a, b, e, d}

Because every single edge in the graph runs only between a vertex in Set 1 and a
vertex in Set 2, we have successfully partitioned the graph. Therefore, the graph is
bipartite.

(Note: Because every vertex in Set 1 is connected to every single vertex in Set 2, this is
specifically known as a complete bipartite graph, denoted as K2,4 .)

Question-3

Determine whether the given pair of graphs is isomorphic. Exhibit an isomorphism

or provide a rigorous argument that none exists.

u2 v2

v1 v3
u9 v8
u1 u10 u8 u3
v10
u7
u6 v7 v9
v6 v4

u5 u4
v5
Solution: Based on a detailed structural analysis, the two graphs are isomorphic.
Before constructing a mapping, we first confirm that both graphs share identical
fundamental properties. Let the left graph be G1 and the right graph be G2 .

• Vertices: Both G1 and G2 have exactly 10 vertices (|V | = 10).

• Edges: Both graphs have exactly 15 edges (|E| = 15).

3
 • Degrees: Every vertex in G1 has a degree of 3. By counting the connections
in G2 (including outer edges, straight spokes, curved edges, and inner central
connections), every vertex in G2 also has a degree of 3. Both are therefore 3-
regular (cubic) graphs.

To prove isomorphism, we define a bijective function f : V (G1 ) → V (G2 ) that per-

fectly preserves adjacency.
Let the mapping f be defined as follows:

f (u1 ) = v9 f (u6 ) = v5
f (u2 ) = v1 f (u7 ) = v7
f (u3 ) = v2 f (u8 ) = v8
f (u4 ) = v3 f (u9 ) = v6
f (u5 ) = v4 f (u10 ) = v10

To rigorously prove this mapping is an isomorphism, we apply the function f to all

15 edges of G1 and verify that the corresponding mapped edge exists in G2 .
Outer Pentagon Edges of G1 :

• (u1 , u2 ) → (v9 , v1 ) : Exists in G2 (Curved edge)

• (u2 , u3 ) → (v1 , v2 ) : Exists in G2 (Outer hexagon)

• (u3 , u4 ) → (v2 , v3 ) : Exists in G2 (Outer hexagon)

• (u4 , u5 ) → (v3 , v4 ) : Exists in G2 (Outer hexagon)

• (u5 , u1 ) → (v4 , v9 ) : Exists in G2 (Straight spoke)

Inner Star Edges of G1 :

• (u6 , u8 ) → (v5 , v8 ) : Exists in G2 (Curved edge)

• (u8 , u10 ) → (v8 , v10 ) : Exists in G2 (Inner central edge)

• (u10 , u7 ) → (v10 , v7 ) : Exists in G2 (Inner central edge)

• (u7 , u9 ) → (v7 , v6 ) : Exists in G2 (Straight spoke)

• (u9 , u6 ) → (v6 , v5 ) : Exists in G2 (Outer hexagon)

Connecting Spoke Edges of G1 :

• (u1 , u10 ) → (v9 , v10 ) : Exists in G2 (Inner central edge)

• (u2 , u9 ) → (v1 , v6 ) : Exists in G2 (Outer hexagon)

• (u3 , u8 ) → (v2 , v8 ) : Exists in G2 (Straight spoke)

• (u4 , u7 ) → (v3 , v7 ) : Exists in G2 (Curved edge)

• (u5 , u6 ) → (v4 , v5 ) : Exists in G2 (Outer hexagon)

Since every edge in G1 corresponds directly to a valid edge in G2 under the bijective
mapping f , the function is a valid isomorphism. Therefore, G1 ∼= G2 .

4
Question-4

Determine whether the given pair of graphs is isomorphic. Exhibit an isomorphism

or provide a rigorous argument that none exists.

u1 v1 v2

u6 u2
v5

v6
u5 u3

u4 v4 v3

Solution: Based on a detailed analysis of the two graphs, we can determine that the
given pair of graphs is indeed isomorphic.
Here is the rigorous step-by-step mathematical solution and the explicit isomor-
phism.
Let the left graph be G1 and the right graph be G2 .

• Number of Vertices: |V (G1 )| = 6 and |V (G2 )| = 6.

• Vertex Degrees: By counting the connections, every vertex in G1 has a degree of

3 (it is a 3-regular graph). Similarly, every vertex in G2 also has a degree of 3.

• Number of Edges: Using the handshaking lemma ( 21 degrees), both graphs

P

have 6×32 = 9 edges.

Since the basic invariants match, we can proceed to look at the internal structure.
To find an isomorphism mapping, we need to identify unique structural features,
such as specific cycles (loops). Let’s look for triangles (3-cycles) in both graphs.

• Cycles in G1 : There are exactly two separate 3-cycles: the top triangle formed
by {u1 , u2 , u6 } and the bottom triangle formed by {u4 , u3 , u5 }.

• Cycles in G2 : Looking closely at G2 , there are also exactly two 3-cycles: the
top inner triangle formed by {v1 , v2 , v5 } and the bottom inner triangle formed by
{v4 , v3 , v6 }.

Furthermore, in both graphs, the two triangles are connected to each other by
exactly three independent edges (a perfect matching).

• In G1 , the connecting edges are (u1 , u4 ), (u2 , u3 ), and (u6 , u5 ).

• In G2 , the connecting edges are (v1 , v4 ), (v2 , v3 ), and (v5 , v6 ).

5
 Because the structural anatomy of both graphs is identical (they are both repre-
sentations of the triangular prism graph), we can construct a one-to-one mapping
between them.
We will define a bijective function f : V (G1 ) → V (G2 ) by mapping the vertices of the
first triangle in G1 to the first triangle in G2 , and then following the connecting edges
to map the second triangle.
Let’s establish the following mapping:

• f (u1 ) = v1

• f (u2 ) = v2

• f (u3 ) = v3

• f (u4 ) = v4

• f (u5 ) = v6

• f (u6 ) = v5

To prove that f is a valid isomorphism, we must verify that for every edge (x, y) in
G1 , there is a corresponding edge (f (x), f (y)) in G2 .
Let’s test all 9 edges of G1 under our mapping function f :
Edges of the first triangle:

• (u1 , u2 ) → (f (u1 ), f (u2 )) = (v1 , v2 ) : Valid edge in G2

• (u2 , u6 ) → (f (u2 ), f (u6 )) = (v2 , v5 ) : Valid edge in G2

• (u6 , u1 ) → (f (u6 ), f (u1 )) = (v5 , v1 ) : Valid edge in G2

Edges of the second triangle:

• (u4 , u3 ) → (f (u4 ), f (u3 )) = (v4 , v3 ) : Valid edge in G2

• (u3 , u5 ) → (f (u3 ), f (u5 )) = (v3 , v6 ) : Valid edge in G2

• (u5 , u4 ) → (f (u5 ), f (u4 )) = (v6 , v4 ) : Valid edge in G2

Edges connecting the triangles:

• (u1 , u4 ) → (f (u1 ), f (u4 )) = (v1 , v4 ) : Valid edge in G2

• (u2 , u3 ) → (f (u2 ), f (u3 )) = (v2 , v3 ) : Valid edge in G2

• (u6 , u5 ) → (f (u6 ), f (u5 )) = (v5 , v6 ) : Valid edge in G2

Since f is a bijection from the vertex set of G1 to the vertex set of G2 that preserves
all adjacency relationships perfectly, the function f is a valid isomorphism. Therefore,
the two graphs are mathematically identical.

6
Question-5

Determine whether the given pair of directed graphs are isomorphic.

u1 u2 v1 v2

u3 u4 v3 v4

Solution: To determine if the directed graphs G1 = (V1 , E1 ) and G2 = (V2 , E2 ) are

isomorphic, we compare their structural properties and invariants.
An isomorphism must preserve the out-degree (dout ) and in-degree (din ) for corre-
sponding vertices. Let us list the degree pairs (dout , din ) for each vertex:
Graph G1 (vertices ui ):
• u1 : (1, 2)

• u2 : (3, 2) (includes self-loop)

• u3 : (3, 1)

• u4 : (0, 2)
Graph G2 (vertices vi ):
• v1 : (1, 1)

• v2 : (3, 1)

• v3 : (1, 2)

• v4 : (2, 3) (includes self-loop)

We observe the following discrepancies between the two graphs:

1. Existence of a Sink: In graph G1 , vertex u4 is a sink node with an out-degree of

0. In graph G2 , there is no vertex with an out-degree of 0.

2. In-degree Maximum: The maximum in-degree in G1 is ∆in (G1 ) = 2. However, in

G2 , vertex v4 has an in-degree of 3.

3. Self-loop Properties: In G1 , the vertex with a self-loop (u2 ) has degrees (3, 2).
In G2 , the vertex with a self-loop (v4 ) has degrees (2, 3). For the graphs to be
isomorphic, these degree pairs must match.

Because the graphs do not share the same degree sequences and structural prop-
erties (such as sink nodes and maximum in-degrees), there is no bijection f : V1 → V2
that preserves adjacency.
Therefore, the two directed graphs are not isomorphic.

7
Question-6

Determine whether the given pair of directed graphs are isomorphic.

u1 v1

u4 v4

u2 u3 v2 v3

Solution: To determine whether the two directed graphs are isomorphic, we can eval-
uate their graph invariants. Specifically, we will look at the out-degrees (the number
of directed edges originating from a vertex) for each node. For two directed graphs to
be isomorphic, their vertices must share the exact same out-degree sequence.
Let us calculate the out-degree, denoted as deg+ (x), for each vertex in the first
graph:

• Vertex u1 : 1 outgoing edge (to u4 ) =⇒ deg+ (u1 ) = 1

• Vertex u2 : 3 outgoing edges (to u1 , u3 , u4 ) =⇒ deg+ (u2 ) = 3

• Vertex u3 : 1 outgoing edge (to u1 ) =⇒ deg+ (u3 ) = 1

• Vertex u4 : 1 outgoing edge (to u3 ) =⇒ deg+ (u4 ) = 1

The out-degree sequence for G1 is (3, 1, 1, 1).

Now, we calculate the out-degrees for the vertices in the second graph. Pay close
attention to the direction of the bottom edge, which points from v3 to v2 :

• Vertex v1 : 1 outgoing edge (to v4 ) =⇒ deg+ (v1 ) = 1

• Vertex v2 : 2 outgoing edges (to v1 , v4 ) =⇒ deg+ (v2 ) = 2

• Vertex v3 : 2 outgoing edges (to v1 , v2 ) =⇒ deg+ (v3 ) = 2

• Vertex v4 : 1 outgoing edge (to v3 ) =⇒ deg+ (v4 ) = 1

The out-degree sequence for G2 is (2, 2, 1, 1).

The first graph contains a vertex (u2 ) with an out-degree of 3. The second graph
lacks any vertex with an out-degree of 3. Because a graph isomorphism must preserve
degree sequences, it is impossible to map the vertices of G1 to G2 . Therefore, the two
directed graphs are not isomorphic.

8
Question-7

Represent the following pseudograph using an incidence matrix.

e2
v1 v2 e4
v3
e1
e3

e7
e6 e5

v4
v5
e8

Solution: An incidence matrix of an undirected graph is a matrix M where the rows

represent the vertices and the columns represent the edges. The entries mij are
defined as:

• mij = 1 if edge ej is incident to vertex vi .

• mij = 0 otherwise.

Note: For loops, the edge is incident to only one vertex, resulting in a single 1 in that
edge’s column.

Based on the provided graph, we have:

• Vertices (n = 5): v1 , v2 , v3 , v4 , v5

• Edges (m = 8): e1 , e2 , e3 , e4 , e5 , e6 , e7 , e8

This means our incidence matrix M will be a 5 × 8 matrix.

We determine the non-zero entries for each column (edge):

• e1 : Loop at v1 =⇒ Incident to v1

• e2 : Connects v1 and v2 =⇒ Incident to v1 , v2

• e3 : Connects v1 and v2 =⇒ Incident to v1 , v2

• e4 : Connects v2 and v3 =⇒ Incident to v2 , v3

• e5 : Connects v3 and v5 =⇒ Incident to v3 , v5

• e6 : Connects v2 and v5 =⇒ Incident to v2 , v5

9
 • e7 : Connects v2 and v4 =⇒ Incident to v2 , v4

• e8 : Loop at v4 =⇒ Incident to v4

Putting it all together, we label the rows v1 . . . v5 and the columns e1 . . . e8 to yield
the final incidence matrix:

e1 e2 e3 e4 e5 e6 e7 e8
 
v1 1 1 1 0 0 0 0 0
v2 
 0 1 1 1 0 1 1 0 

M = v3  0 0 0 1 1 0 0 0
 

 
v4  0 0 0 0 0 0 1 1 
v5 0 0 0 0 1 1 0 0

Question-8

Find the adjacency matrix of the given directed multigraph with respect to the vertices
listed in alphabetic order.

a b

c d

Solution: An adjacency matrix A for a directed graph with n vertices is an n × n matrix

where the entry Aij = 1 if there is an edge pointing from vertex i to vertex j, and Aij = 0
otherwise.
Let us construct the matrix by observing the outgoing edges from each vertex. We
will order the rows and columns as a, b, c, d:

• Vertex a: There are outgoing edges to a (loop), b (straight edge), c (curved edge),
and d (curved edge).
Therefore, the first row is 1, 1, 1, 1.

• Vertex b: There are outgoing edges to b (loop) and d (curved edge). There are no
arrows pointing from b to a or c.
Therefore, the second row is 0, 1, 0, 1.

10
 • Vertex c: There are outgoing edges to a (curved edge) and c (loop). There are no
arrows pointing from c to b or d.
Therefore, the third row is 1, 0, 1, 0.

• Vertex d: There are outgoing edges to a (curved edge), b (curved edge), c (straight
edge), and d (loop).
Therefore, the fourth row is 1, 1, 1, 1.

Combining these rows, the resulting adjacency matrix A is:

 
1 1 1 1
0 1 0 1
A=
 

1 0 1 0
1 1 1 1

Question-9

Find Hamilton circuit or path for the following graph, if exists.

a j

e i
f
b h

d g

c k
Solution: To determine if a Hamiltonian circuit exists, we examine the degrees of the
vertices. A fundamental rule for finding Hamiltonian circuits is that if a vertex has a
degree of exactly 2, both of its incident edges must be included in any Hamiltonian
circuit.
Observe the outer vertices a, c, j, and k. They all have a degree of 2.

• deg(a) = 2 =⇒ edges {a, e} and {a, b} must be in the circuit.

• deg(c) = 2 =⇒ edges {c, b} and {c, d} must be in the circuit.

• deg(j) = 2 =⇒ edges {j, i} and {j, h} must be in the circuit.

• deg(k) = 2 =⇒ edges {k, g} and {k, h} must be in the circuit.

A vertex in a Hamiltonian circuit can only have exactly 2 incident edges used.

• Look at vertex b. In our circuit, we must use edges {a, b} and {c, b}. Since b’s
quota of 2 edges is full, the other edges connected to b (which are {b, e} and
{b, d}) cannot be part of the circuit.

11
 • Similarly, look at vertex h. We must use edges {j, h} and {k, h}. Therefore, the
other edges connected to h ({h, i} and {h, g}) cannot be part of the circuit.

By forcing these edges, we have formed two required strings of vertices:

• Path 1: e → a → b → c → d

• Path 2: i → j → h → k → g

To form a full Hamiltonian circuit, we must connect these two paths along with
the only remaining unvisited vertex, f . The available open endpoints of our paths are
e, d and i, g.

• If we connect e → f → i, we successfully include vertex f and merge the top parts

of our paths.

• Now we must close the circuit by connecting the bottom endpoints d and g. The
edge {d, g} exists in the graph (it is the long bottom arc).

Tracing this complete route yields:

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

Checking this sequence, it visits all 11 vertices (a, b, c, d, e, f, g, h, i, j, k) exactly once and
returns to the starting vertex. All traversed edges exist in the original graph.
Yes, the graph contains a Hamiltonian Circuit (and consequently, it also contains
multiple Hamiltonian Paths).

Question-10

Draw an undirected graph represented by the given adjacency matrix.

 
0 1 3 0 4
1 2 1 3 0
 
3 1 1 0 1
 
 
0 3 0 0 2
4 0 1 2 3
Solution: We are asked to draw the undirected graph it represents. We’ll identify this
as an adjacency matrix for a weighted, undirected multigraph with self-loops. Let’s
list the vertices as V = {v1 , v2 , v3 , v4 , v5 }.
The matrix entries correspond to the edge weights between vertices:

• Vertices: Since it is a 5 × 5 matrix, there are 5 vertices.

• Undirected: The matrix is symmetric (M = M T ), so the graph is undirected.

• Weighted Edges: Entry Mij (where i ̸= j) represents the weight of the single edge
between vi and vj . A non-zero entry Mii indicates a single self-loop with that
weight on vertex vi .

Here is the full list of vertices and edges with their weights, derived from the matrix:

12
 • Vertex Set: V = {v1 , v2 , v3 , v4 , v5 }

• Edge Set with Weights:

– (v1 , v2 ) with weight 1

– (v1 , v3 ) with weight 3
– (v1 , v5 ) with weight 4
– (v2 , v3 ) with weight 1
– (v2 , v4 ) with weight 3
– (v3 , v5 ) with weight 1
– (v4 , v5 ) with weight 2
– Self-loop on v2 with weight 2
– Self-loop on v3 with weight 1
– Self-loop on v5 with weight 3

v2

1
1

3
1 1
v51 3 v3
3 4

v4

Question-11

Determine whether the following graph has an Euler circuit? If not, find an Euler
path. For the same graph, find for Hamilton path or circuit.

13
 a

f
e b

j g

i h

d c

Solution: The graph displays the classic Petersen graph. Let V be the set of vertices
and E be the set of edges. The graph has |V | = 10 vertices and |E| = 15 edges. By
observing the graph, we can see that every vertex is connected to exactly 3 edges.
Thus, it is a 3-regular (cubic) graph.
A connected graph contains an Euler circuit if and only if every vertex in the graph
has an even degree. In our graph, the degree of every vertex is 3 (an odd number).
Because there are vertices with an odd degree, the graph does not have an Euler
circuit.
A connected graph contains an Euler path if and only if it has exactly zero or
exactly two vertices of odd degree. As established, all 10 vertices in this graph have
a degree of 3. Since there are more than two vertices with an odd degree, the graph
does not have an Euler path.
A Hamilton circuit is a cycle that visits every vertex exactly once and returns to
the starting vertex. The Petersen graph is a famous example of a hypohamiltonian
graph, meaning it does not contain a Hamilton circuit. If you remove any single
vertex from it, the remaining graph becomes Hamiltonian, but the full 10-vertex graph
cannot form a complete cycle.
A Hamilton path is a path that visits every vertex in the graph exactly once without
needing to return to the origin. The Petersen graph does have a Hamilton path. To
find one, we can traverse the outer pentagon, cross over to the inner star, and trace
through the remaining vertices. A valid sequence of vertices for a Hamilton path is:

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

Question-12

Determine whether the following directed graph has an Euler circuit. Construct an
Euler circuit if one exists. If no Euler circuit exists, determine whether the directed
graph has an Euler path. Construct the Euler path if exists.

14
 a b c

d e

Solution: To determine whether the given directed graph has an Euler circuit or an
Euler path, we must evaluate the in-degrees (deg− ) and out-degrees (deg+ ) of every
vertex. Let V = {a, b, c, d, e}.
By counting the incoming and outgoing arrows for each node, we get:

• Vertex a:

– In-edges: from b ⇒ deg− (a) = 1

– Out-edges: to d, e ⇒ deg+ (a) = 2

• Vertex b:

– In-edges: from c, d, e ⇒ deg− (b) = 3

– Out-edges: to a, c, e ⇒ deg+ (b) = 3

• Vertex c:

– In-edges: from b, e ⇒ deg− (c) = 2

– Out-edges: to b, e ⇒ deg+ (c) = 2

• Vertex d:

– In-edges: from a, e ⇒ deg− (d) = 2

– Out-edges: to b, e ⇒ deg+ (d) = 2

• Vertex e:

– In-edges: from a, b, c, d ⇒ deg− (e) = 4

– Out-edges: to b, c, d ⇒ deg+ (e) = 3

A directed graph contains an Euler circuit if and only if it is weakly connected

and deg− (v) = deg+ (v) for every vertex v ∈ V . Since deg− (a) ̸= deg+ (a) and deg− (e) ̸=
deg+ (e), no Euler circuit exists.
A directed graph contains an Euler path (but no circuit) if and only if it is weakly
connected and:

1. Exactly one vertex has deg+ (v) − deg− (v) = 1 (Start vertex).

2. Exactly one vertex has deg− (v) − deg+ (v) = 1 (End vertex).

15
 3. All other vertices have equal in-degrees and out-degrees.

Based on our analysis:

• For vertex a: deg+ (a) − deg− (a) = 2 − 1 = 1.

• For vertex e: deg− (e) − deg+ (e) = 4 − 3 = 1.

• For vertices b, c, d: deg− (v) = deg+ (v).

Since these conditions are met perfectly, an Euler path exists. It must start at vertex
a and end at vertex e.
Starting at vertex a and ending at vertex e, we can traverse all 12 distinct edges of
the graph exactly once. One such valid Euler path is:

a→d→b→a→e→d→e→b→c→b→e→c→e

This traverses the edges in the following order: (a, d), (d, b), (b, a), (a, e), (e, d), (d, e),
(e, b), (b, c), (c, b), (b, e), (e, c), (c, e).

Question-13

Consider the following directed graph. Find the shortest path between the vertices S
and T of the graph by Dijkstra’s algorithm.

2
1 2
E G
C
1
A
1
3 4
4 3
7 D
S 3
3
4 5 T
3 B
5
F

Solution: Let d(v) be the shortest distance from the source node S to node v. Initially,
d(S) = 0 and d(v) = ∞ for all other vertices.
The table below tracks the shortest distance to each node at every step. In each
row, the unvisited node with the smallest tentative distance is selected and its neigh-
bors are updated.
The shortest distance from S to T is 10.
Tracing back the distance updates reveals that there are three valid shortest paths
that all result in a total weight of 10:

16
 Selected Node S A B C D E F G T
Initial 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
S (d = 0) – 4 3 ∞ 7 ∞ ∞ ∞ ∞
B (d = 3) – 4 – ∞ 7 ∞ ∞ ∞ ∞
A (d = 4) – – – 5 7 ∞ ∞ ∞ ∞
C (d = 5) – – – – 7 6 ∞ ∞ ∞
E (d = 6) – – – – 7 – ∞ 8 10
D (d = 7) – – – – – – 12 8 10
G (d = 8) – – – – – – 12 – 10
T (d = 10) – – – – – – 12 – –
F (d = 12) – – – – – – – – –

• Path 1: S → A → C → E → T (Weights: 4 + 1 + 1 + 4 = 10)

• Path 2: S → D → T (Weights: 7 + 3 = 10)

• Path 3: S → B → D → T (Weights: 3 + 4 + 3 = 10)

Question-14

Let G be the directed graph given below. Use Dijkstra’s algorithm to find the shortest
path between the vertices A and H.

4 4 6
A C E G I
6 2
3
1 5 7 1 9 2

2 0 7
B D F H J
Solution: To find the shortest path, we initialize the distance to the source node A as
d(A) = 0 and all other nodes as ∞. We then iteratively relax the edges.
The shortest path is determined by following the predecessors of the relaxed dis-
tances:

• Path: A → C → B → D → F → G → E → H

• Total Weight: 4 + 3 + 2 + 0 + 2 + 4 + 1 = 16

17
 Step Node Neighbors Relaxed Distance Vector (A, B, C, D, E, F, G, H)
0 — — (0, ∞, ∞, ∞, ∞, ∞, ∞, ∞)
1 A C :0+4=4 (0, ∞, 4, ∞, ∞, ∞, ∞, ∞)
2 C B : 4 + 3 = 7, F : 4 + 6 = 10 (0, 7, 4, ∞, ∞, 10, ∞, ∞)
3 B D :7+2=9 (0, 7, 4, 9, ∞, 10, ∞, ∞)
4 D F :9+0=9 (0, 7, 4, 9, ∞, 9, ∞, ∞)
5 F G : 9 + 2 = 11 (0, 7, 4, 9, ∞, 9, 11, ∞)
6 G E : 11 + 4 = 15, H : 11 + 9 = 20 (0, 7, 4, 9, 15, 9, 11, 20)
7 E H : 15 + 1 = 16 (0, 7, 4, 9, 15, 9, 11, 16)
8 H Goal Reached (0, 7, 4, 9, 15, 9, 11, 16)

Question-15

Find the strongly connected components of the given digraph.

a b c

f e d
Solution: A strongly connected component (SCC) of a directed graph is a maximal
subgraph in which for every pair of vertices u and v, there is a directed path from u to
v and a directed path from v to u.
To find the SCCs of the given digraph, we group the vertices into sets where all
vertices in a set are mutually reachable:

• Observe the vertices on the left. There is a two-way connection between a and b
(a → b and b → a), meaning they can reach each other.

• Similarly, there is a two-way connection between a and f (a → f and f → a).

• By transitivity, b can reach f (via a) and f can reach b (via a). Thus, a, b, and f
are all mutually reachable.

• We must check if this component can be expanded. The vertices b and f have
outgoing edges to the right side of the graph (b → c, b → e, f → e). However, there
are no returning edges from {c, d, e} back to {a, b, f }.

• Therefore, no other vertices can be part of this mutual-reachability group. The

set {a, b, f } is a maximal strongly connected component.

• Now look at the remaining vertices on the right. There is a two-way connection
between c and e (c → e and e → c).

18
 • We also have a path passing through d. There is an edge c → d and an edge
d → e.

• This creates a directed cycle: c → d → e → c. Because they form a continuous

loop, any vertex in {c, d, e} can reach any other vertex in that same set.

• Since there are no other vertices left in the graph to check, this forms our second
maximal strongly connected component.

The digraph has exactly two strongly connected components:

C1 = {a, b, f }

C2 = {c, d, e}

2 Excercise

1. Represent the following graph by an incidence matrix.

v1 v2 e6 v3

e3

e4
e1 e5
e2

v4 v5

Answer:  
1 1 0 0 0 0
0 0 1 1 0 1
 
0 0 0 0 1 1
 
 
1 0 1 0 0 0
0 1 0 1 1 0

2. Represent the following directed graph by an adjacency matrix.

19
 b

a c

e d

Answer:  
0 1 1 0 1 1
0 1 0 1 1 0
 
1 0 1 0 0 1
 
 
0 0 0 0 0 0
0 1 1 1 1 0

3. Use paths either to show the following pair of graphs are not isomorphic or find
an isomorphism between them.

u1 u2 v1

u6 u7 v6
v5
v4 v2
v7
u8 u3 v8

u5 u4 v3

Answer: Isomorphic.

4. Determine whether the following graph has an Euler circuit? If not, find an Euler
path. For the same graph, find for Hamilton path or circuit.

20
 a b c

j
i k

o p q
d h

n l
m

e f g

Answer: The graph has neither an Euler circuit nor an Euler path. This graph
has neither a Hamilton path nor a Hamilton circuit.

5. Using Dijkstra’s Algorithm, determine the shortest distance and the shortest
path between the vertices v1 to v16 .

21
 4 2 7
v1 v2 v3 v4

5 8 3 10 1
10

4
v5 v6 v7 v8
2 2
5

15
1
6 9 3 12

1 2
v9 v10 v11 v12
4
3
2

20
4 7 6 5

v13 v14 v15 v16

3 1 8

5 2 1
Answer: The shortest distane is 15 amd the shortest path is v1 →
− v5 →
− v6 →
−
2 5
v11 →
− v12 →
− v16 .

22
 Graphs and its Matrix
Representation
• Problem set and solutions

Learning objectives
• We will apply the concepts of graph theory to real-life problems.
Module 04, MAT2002//Discrete Mathematics and Graph Theory
Mathematics Division//School of Advanced Sciences and Languages// VIT Bhopal University

1
1 Problem set and solutions

Question-1

How many edges are there in an undirected graph with 10 vertices each of degree 6?

Solution: Let us consider that e be the number edges in the graph G = (V, E), where V
is the set of all vertices of the graph G and E be the set of all edges of the same graph
G.
Then, by using the Handshaking Theorem, we can write
X
2e = deg(v)
v∈V

⇒ 2e = sum of the degrees of all the vertices

⇒ 2e = 10 × 6
⇒ 2e = 60
⇒ e = 30
Hence, there are 30 edges in the graph G.

Question-2

Determine whether the following graph is a bipartite graph.

a b

f c

e d

Solution: Yes, the graph is bipartite.

A graph is bipartite if its vertices can be divided into two separate sets (let’s call
them Set 1 and Set 2) such that every edge in the graph connects a vertex in Set 1 to
a vertex in Set 2. Importantly, there can be no edges connecting vertices within the
same set.
We can test if a graph is bipartite by trying to assign each vertex to one of the two
sets:

1. Start with vertex f : Place f into Set 1.

2
 2. Assign f ’s neighbors: Look at all the vertices connected to f . The graph shows
edges connecting f to a, b, e, and d. Because they share an edge with f , they
cannot be in the same set as f . Therefore, we place a, b, e, and d into Set 2.

3. Assign the remaining vertex: The only vertex left to assign is c.

4. Check c’s neighbors: Look at the edges connected to c. It is connected to a, b,

e, and d. Because all of its neighbors are currently in Set 2, vertex c must be
placed in Set 1.

• Set 1: {f, c}

• Set 2: {a, b, e, d}

Because every single edge in the graph runs only between a vertex in Set 1 and a
vertex in Set 2, we have successfully partitioned the graph. Therefore, the graph is
bipartite.

(Note: Because every vertex in Set 1 is connected to every single vertex in Set 2, this is
specifically known as a complete bipartite graph, denoted as K2,4 .)

Question-3

Determine whether the given pair of graphs is isomorphic. Exhibit an isomorphism

or provide a rigorous argument that none exists.

u2 v2

v1 v3
u9 v8
u1 u10 u8 u3
v10
u7
u6 v7 v9
v6 v4

u5 u4
v5
Solution: Based on a detailed structural analysis, the two graphs are isomorphic.
Before constructing a mapping, we first confirm that both graphs share identical
fundamental properties. Let the left graph be G1 and the right graph be G2 .

• Vertices: Both G1 and G2 have exactly 10 vertices (|V | = 10).

• Edges: Both graphs have exactly 15 edges (|E| = 15).

3
 • Degrees: Every vertex in G1 has a degree of 3. By counting the connections
in G2 (including outer edges, straight spokes, curved edges, and inner central
connections), every vertex in G2 also has a degree of 3. Both are therefore 3-
regular (cubic) graphs.

To prove isomorphism, we define a bijective function f : V (G1 ) → V (G2 ) that per-

fectly preserves adjacency.
Let the mapping f be defined as follows:

f (u1 ) = v9 f (u6 ) = v5
f (u2 ) = v1 f (u7 ) = v7
f (u3 ) = v2 f (u8 ) = v8
f (u4 ) = v3 f (u9 ) = v6
f (u5 ) = v4 f (u10 ) = v10

To rigorously prove this mapping is an isomorphism, we apply the function f to all

15 edges of G1 and verify that the corresponding mapped edge exists in G2 .
Outer Pentagon Edges of G1 :

• (u1 , u2 ) → (v9 , v1 ) : Exists in G2 (Curved edge)

• (u2 , u3 ) → (v1 , v2 ) : Exists in G2 (Outer hexagon)

• (u3 , u4 ) → (v2 , v3 ) : Exists in G2 (Outer hexagon)

• (u4 , u5 ) → (v3 , v4 ) : Exists in G2 (Outer hexagon)

• (u5 , u1 ) → (v4 , v9 ) : Exists in G2 (Straight spoke)

Inner Star Edges of G1 :

• (u6 , u8 ) → (v5 , v8 ) : Exists in G2 (Curved edge)

• (u8 , u10 ) → (v8 , v10 ) : Exists in G2 (Inner central edge)

• (u10 , u7 ) → (v10 , v7 ) : Exists in G2 (Inner central edge)

• (u7 , u9 ) → (v7 , v6 ) : Exists in G2 (Straight spoke)

• (u9 , u6 ) → (v6 , v5 ) : Exists in G2 (Outer hexagon)

Connecting Spoke Edges of G1 :

• (u1 , u10 ) → (v9 , v10 ) : Exists in G2 (Inner central edge)

• (u2 , u9 ) → (v1 , v6 ) : Exists in G2 (Outer hexagon)

• (u3 , u8 ) → (v2 , v8 ) : Exists in G2 (Straight spoke)

• (u4 , u7 ) → (v3 , v7 ) : Exists in G2 (Curved edge)

• (u5 , u6 ) → (v4 , v5 ) : Exists in G2 (Outer hexagon)

Since every edge in G1 corresponds directly to a valid edge in G2 under the bijective
mapping f , the function is a valid isomorphism. Therefore, G1 ∼= G2 .

4
Question-4

Determine whether the given pair of graphs is isomorphic. Exhibit an isomorphism

or provide a rigorous argument that none exists.

u1 v1 v2

u6 u2
v5

v6
u5 u3

u4 v4 v3

Solution: Based on a detailed analysis of the two graphs, we can determine that the
given pair of graphs is indeed isomorphic.
Here is the rigorous step-by-step mathematical solution and the explicit isomor-
phism.
Let the left graph be G1 and the right graph be G2 .

• Number of Vertices: |V (G1 )| = 6 and |V (G2 )| = 6.

• Vertex Degrees: By counting the connections, every vertex in G1 has a degree of

3 (it is a 3-regular graph). Similarly, every vertex in G2 also has a degree of 3.

• Number of Edges: Using the handshaking lemma ( 21 degrees), both graphs

P

have 6×32 = 9 edges.

Since the basic invariants match, we can proceed to look at the internal structure.
To find an isomorphism mapping, we need to identify unique structural features,
such as specific cycles (loops). Let’s look for triangles (3-cycles) in both graphs.

• Cycles in G1 : There are exactly two separate 3-cycles: the top triangle formed
by {u1 , u2 , u6 } and the bottom triangle formed by {u4 , u3 , u5 }.

• Cycles in G2 : Looking closely at G2 , there are also exactly two 3-cycles: the
top inner triangle formed by {v1 , v2 , v5 } and the bottom inner triangle formed by
{v4 , v3 , v6 }.

Furthermore, in both graphs, the two triangles are connected to each other by
exactly three independent edges (a perfect matching).

• In G1 , the connecting edges are (u1 , u4 ), (u2 , u3 ), and (u6 , u5 ).

• In G2 , the connecting edges are (v1 , v4 ), (v2 , v3 ), and (v5 , v6 ).

5
 Because the structural anatomy of both graphs is identical (they are both repre-
sentations of the triangular prism graph), we can construct a one-to-one mapping
between them.
We will define a bijective function f : V (G1 ) → V (G2 ) by mapping the vertices of the
first triangle in G1 to the first triangle in G2 , and then following the connecting edges
to map the second triangle.
Let’s establish the following mapping:

• f (u1 ) = v1

• f (u2 ) = v2

• f (u3 ) = v3

• f (u4 ) = v4

• f (u5 ) = v6

• f (u6 ) = v5

To prove that f is a valid isomorphism, we must verify that for every edge (x, y) in
G1 , there is a corresponding edge (f (x), f (y)) in G2 .
Let’s test all 9 edges of G1 under our mapping function f :
Edges of the first triangle:

• (u1 , u2 ) → (f (u1 ), f (u2 )) = (v1 , v2 ) : Valid edge in G2

• (u2 , u6 ) → (f (u2 ), f (u6 )) = (v2 , v5 ) : Valid edge in G2

• (u6 , u1 ) → (f (u6 ), f (u1 )) = (v5 , v1 ) : Valid edge in G2

Edges of the second triangle:

• (u4 , u3 ) → (f (u4 ), f (u3 )) = (v4 , v3 ) : Valid edge in G2

• (u3 , u5 ) → (f (u3 ), f (u5 )) = (v3 , v6 ) : Valid edge in G2

• (u5 , u4 ) → (f (u5 ), f (u4 )) = (v6 , v4 ) : Valid edge in G2

Edges connecting the triangles:

• (u1 , u4 ) → (f (u1 ), f (u4 )) = (v1 , v4 ) : Valid edge in G2

• (u2 , u3 ) → (f (u2 ), f (u3 )) = (v2 , v3 ) : Valid edge in G2

• (u6 , u5 ) → (f (u6 ), f (u5 )) = (v5 , v6 ) : Valid edge in G2

Since f is a bijection from the vertex set of G1 to the vertex set of G2 that preserves
all adjacency relationships perfectly, the function f is a valid isomorphism. Therefore,
the two graphs are mathematically identical.

6
Question-5

Determine whether the given pair of directed graphs are isomorphic.

u1 u2 v1 v2

u3 u4 v3 v4

Solution: To determine if the directed graphs G1 = (V1 , E1 ) and G2 = (V2 , E2 ) are

isomorphic, we compare their structural properties and invariants.
An isomorphism must preserve the out-degree (dout ) and in-degree (din ) for corre-
sponding vertices. Let us list the degree pairs (dout , din ) for each vertex:
Graph G1 (vertices ui ):
• u1 : (1, 2)

• u2 : (3, 2) (includes self-loop)

• u3 : (3, 1)

• u4 : (0, 2)
Graph G2 (vertices vi ):
• v1 : (1, 1)

• v2 : (3, 1)

• v3 : (1, 2)

• v4 : (2, 3) (includes self-loop)

We observe the following discrepancies between the two graphs:

1. Existence of a Sink: In graph G1 , vertex u4 is a sink node with an out-degree of

0. In graph G2 , there is no vertex with an out-degree of 0.

2. In-degree Maximum: The maximum in-degree in G1 is ∆in (G1 ) = 2. However, in

G2 , vertex v4 has an in-degree of 3.

3. Self-loop Properties: In G1 , the vertex with a self-loop (u2 ) has degrees (3, 2).
In G2 , the vertex with a self-loop (v4 ) has degrees (2, 3). For the graphs to be
isomorphic, these degree pairs must match.

Because the graphs do not share the same degree sequences and structural prop-
erties (such as sink nodes and maximum in-degrees), there is no bijection f : V1 → V2
that preserves adjacency.
Therefore, the two directed graphs are not isomorphic.

7
Question-6

Determine whether the given pair of directed graphs are isomorphic.

u1 v1

u4 v4

u2 u3 v2 v3

Solution: To determine whether the two directed graphs are isomorphic, we can eval-
uate their graph invariants. Specifically, we will look at the out-degrees (the number
of directed edges originating from a vertex) for each node. For two directed graphs to
be isomorphic, their vertices must share the exact same out-degree sequence.
Let us calculate the out-degree, denoted as deg+ (x), for each vertex in the first
graph:

• Vertex u1 : 1 outgoing edge (to u4 ) =⇒ deg+ (u1 ) = 1

• Vertex u2 : 3 outgoing edges (to u1 , u3 , u4 ) =⇒ deg+ (u2 ) = 3

• Vertex u3 : 1 outgoing edge (to u1 ) =⇒ deg+ (u3 ) = 1

• Vertex u4 : 1 outgoing edge (to u3 ) =⇒ deg+ (u4 ) = 1

The out-degree sequence for G1 is (3, 1, 1, 1).

Now, we calculate the out-degrees for the vertices in the second graph. Pay close
attention to the direction of the bottom edge, which points from v3 to v2 :

• Vertex v1 : 1 outgoing edge (to v4 ) =⇒ deg+ (v1 ) = 1

• Vertex v2 : 2 outgoing edges (to v1 , v4 ) =⇒ deg+ (v2 ) = 2

• Vertex v3 : 2 outgoing edges (to v1 , v2 ) =⇒ deg+ (v3 ) = 2

• Vertex v4 : 1 outgoing edge (to v3 ) =⇒ deg+ (v4 ) = 1

The out-degree sequence for G2 is (2, 2, 1, 1).

The first graph contains a vertex (u2 ) with an out-degree of 3. The second graph
lacks any vertex with an out-degree of 3. Because a graph isomorphism must preserve
degree sequences, it is impossible to map the vertices of G1 to G2 . Therefore, the two
directed graphs are not isomorphic.

8
Question-7

Represent the following pseudograph using an incidence matrix.

e2
v1 v2 e4
v3
e1
e3

e7
e6 e5

v4
v5
e8

Solution: An incidence matrix of an undirected graph is a matrix M where the rows

represent the vertices and the columns represent the edges. The entries mij are
defined as:

• mij = 1 if edge ej is incident to vertex vi .

• mij = 0 otherwise.

Note: For loops, the edge is incident to only one vertex, resulting in a single 1 in that
edge’s column.

Based on the provided graph, we have:

• Vertices (n = 5): v1 , v2 , v3 , v4 , v5

• Edges (m = 8): e1 , e2 , e3 , e4 , e5 , e6 , e7 , e8

This means our incidence matrix M will be a 5 × 8 matrix.

We determine the non-zero entries for each column (edge):

• e1 : Loop at v1 =⇒ Incident to v1

• e2 : Connects v1 and v2 =⇒ Incident to v1 , v2

• e3 : Connects v1 and v2 =⇒ Incident to v1 , v2

• e4 : Connects v2 and v3 =⇒ Incident to v2 , v3

• e5 : Connects v3 and v5 =⇒ Incident to v3 , v5

• e6 : Connects v2 and v5 =⇒ Incident to v2 , v5

9
 • e7 : Connects v2 and v4 =⇒ Incident to v2 , v4

• e8 : Loop at v4 =⇒ Incident to v4

Putting it all together, we label the rows v1 . . . v5 and the columns e1 . . . e8 to yield
the final incidence matrix:

e1 e2 e3 e4 e5 e6 e7 e8
 
v1 1 1 1 0 0 0 0 0
v2 
 0 1 1 1 0 1 1 0 

M = v3  0 0 0 1 1 0 0 0
 

 
v4  0 0 0 0 0 0 1 1 
v5 0 0 0 0 1 1 0 0

Question-8

Find the adjacency matrix of the given directed multigraph with respect to the vertices
listed in alphabetic order.

a b

c d

Solution: An adjacency matrix A for a directed graph with n vertices is an n × n matrix

where the entry Aij = 1 if there is an edge pointing from vertex i to vertex j, and Aij = 0
otherwise.
Let us construct the matrix by observing the outgoing edges from each vertex. We
will order the rows and columns as a, b, c, d:

• Vertex a: There are outgoing edges to a (loop), b (straight edge), c (curved edge),
and d (curved edge).
Therefore, the first row is 1, 1, 1, 1.

• Vertex b: There are outgoing edges to b (loop) and d (curved edge). There are no
arrows pointing from b to a or c.
Therefore, the second row is 0, 1, 0, 1.

10
 • Vertex c: There are outgoing edges to a (curved edge) and c (loop). There are no
arrows pointing from c to b or d.
Therefore, the third row is 1, 0, 1, 0.

• Vertex d: There are outgoing edges to a (curved edge), b (curved edge), c (straight
edge), and d (loop).
Therefore, the fourth row is 1, 1, 1, 1.

Combining these rows, the resulting adjacency matrix A is:

 
1 1 1 1
0 1 0 1
A=
 

1 0 1 0
1 1 1 1

Question-9

Find Hamilton circuit or path for the following graph, if exists.

a j

e i
f
b h

d g

c k
Solution: To determine if a Hamiltonian circuit exists, we examine the degrees of the
vertices. A fundamental rule for finding Hamiltonian circuits is that if a vertex has a
degree of exactly 2, both of its incident edges must be included in any Hamiltonian
circuit.
Observe the outer vertices a, c, j, and k. They all have a degree of 2.

• deg(a) = 2 =⇒ edges {a, e} and {a, b} must be in the circuit.

• deg(c) = 2 =⇒ edges {c, b} and {c, d} must be in the circuit.

• deg(j) = 2 =⇒ edges {j, i} and {j, h} must be in the circuit.

• deg(k) = 2 =⇒ edges {k, g} and {k, h} must be in the circuit.

A vertex in a Hamiltonian circuit can only have exactly 2 incident edges used.

• Look at vertex b. In our circuit, we must use edges {a, b} and {c, b}. Since b’s
quota of 2 edges is full, the other edges connected to b (which are {b, e} and
{b, d}) cannot be part of the circuit.

11
 • Similarly, look at vertex h. We must use edges {j, h} and {k, h}. Therefore, the
other edges connected to h ({h, i} and {h, g}) cannot be part of the circuit.

By forcing these edges, we have formed two required strings of vertices:

• Path 1: e → a → b → c → d

• Path 2: i → j → h → k → g

To form a full Hamiltonian circuit, we must connect these two paths along with
the only remaining unvisited vertex, f . The available open endpoints of our paths are
e, d and i, g.

• If we connect e → f → i, we successfully include vertex f and merge the top parts

of our paths.

• Now we must close the circuit by connecting the bottom endpoints d and g. The
edge {d, g} exists in the graph (it is the long bottom arc).

Tracing this complete route yields:

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

Checking this sequence, it visits all 11 vertices (a, b, c, d, e, f, g, h, i, j, k) exactly once and
returns to the starting vertex. All traversed edges exist in the original graph.
Yes, the graph contains a Hamiltonian Circuit (and consequently, it also contains
multiple Hamiltonian Paths).

Question-10

Draw an undirected graph represented by the given adjacency matrix.

 
0 1 3 0 4
1 2 1 3 0
 
3 1 1 0 1
 
 
0 3 0 0 2
4 0 1 2 3
Solution: We are asked to draw the undirected graph it represents. We’ll identify this
as an adjacency matrix for a weighted, undirected multigraph with self-loops. Let’s
list the vertices as V = {v1 , v2 , v3 , v4 , v5 }.
The matrix entries correspond to the edge weights between vertices:

• Vertices: Since it is a 5 × 5 matrix, there are 5 vertices.

• Undirected: The matrix is symmetric (M = M T ), so the graph is undirected.

• Weighted Edges: Entry Mij (where i ̸= j) represents the weight of the single edge
between vi and vj . A non-zero entry Mii indicates a single self-loop with that
weight on vertex vi .

Here is the full list of vertices and edges with their weights, derived from the matrix:

12
 • Vertex Set: V = {v1 , v2 , v3 , v4 , v5 }

• Edge Set with Weights:

– (v1 , v2 ) with weight 1

– (v1 , v3 ) with weight 3
– (v1 , v5 ) with weight 4
– (v2 , v3 ) with weight 1
– (v2 , v4 ) with weight 3
– (v3 , v5 ) with weight 1
– (v4 , v5 ) with weight 2
– Self-loop on v2 with weight 2
– Self-loop on v3 with weight 1
– Self-loop on v5 with weight 3

v2

1
1

3
1 1
v51 3 v3
3 4

v4

Question-11

Determine whether the following graph has an Euler circuit? If not, find an Euler
path. For the same graph, find for Hamilton path or circuit.

13
 a

f
e b

j g

i h

d c

Solution: The graph displays the classic Petersen graph. Let V be the set of vertices
and E be the set of edges. The graph has |V | = 10 vertices and |E| = 15 edges. By
observing the graph, we can see that every vertex is connected to exactly 3 edges.
Thus, it is a 3-regular (cubic) graph.
A connected graph contains an Euler circuit if and only if every vertex in the graph
has an even degree. In our graph, the degree of every vertex is 3 (an odd number).
Because there are vertices with an odd degree, the graph does not have an Euler
circuit.
A connected graph contains an Euler path if and only if it has exactly zero or
exactly two vertices of odd degree. As established, all 10 vertices in this graph have
a degree of 3. Since there are more than two vertices with an odd degree, the graph
does not have an Euler path.
A Hamilton circuit is a cycle that visits every vertex exactly once and returns to
the starting vertex. The Petersen graph is a famous example of a hypohamiltonian
graph, meaning it does not contain a Hamilton circuit. If you remove any single
vertex from it, the remaining graph becomes Hamiltonian, but the full 10-vertex graph
cannot form a complete cycle.
A Hamilton path is a path that visits every vertex in the graph exactly once without
needing to return to the origin. The Petersen graph does have a Hamilton path. To
find one, we can traverse the outer pentagon, cross over to the inner star, and trace
through the remaining vertices. A valid sequence of vertices for a Hamilton path is:

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

Question-12

Determine whether the following directed graph has an Euler circuit. Construct an
Euler circuit if one exists. If no Euler circuit exists, determine whether the directed
graph has an Euler path. Construct the Euler path if exists.

14
 a b c

d e

Solution: To determine whether the given directed graph has an Euler circuit or an
Euler path, we must evaluate the in-degrees (deg− ) and out-degrees (deg+ ) of every
vertex. Let V = {a, b, c, d, e}.
By counting the incoming and outgoing arrows for each node, we get:

• Vertex a:

– In-edges: from b ⇒ deg− (a) = 1

– Out-edges: to d, e ⇒ deg+ (a) = 2

• Vertex b:

– In-edges: from c, d, e ⇒ deg− (b) = 3

– Out-edges: to a, c, e ⇒ deg+ (b) = 3

• Vertex c:

– In-edges: from b, e ⇒ deg− (c) = 2

– Out-edges: to b, e ⇒ deg+ (c) = 2

• Vertex d:

– In-edges: from a, e ⇒ deg− (d) = 2

– Out-edges: to b, e ⇒ deg+ (d) = 2

• Vertex e:

– In-edges: from a, b, c, d ⇒ deg− (e) = 4

– Out-edges: to b, c, d ⇒ deg+ (e) = 3

A directed graph contains an Euler circuit if and only if it is weakly connected

and deg− (v) = deg+ (v) for every vertex v ∈ V . Since deg− (a) ̸= deg+ (a) and deg− (e) ̸=
deg+ (e), no Euler circuit exists.
A directed graph contains an Euler path (but no circuit) if and only if it is weakly
connected and:

1. Exactly one vertex has deg+ (v) − deg− (v) = 1 (Start vertex).

2. Exactly one vertex has deg− (v) − deg+ (v) = 1 (End vertex).

15
 3. All other vertices have equal in-degrees and out-degrees.

Based on our analysis:

• For vertex a: deg+ (a) − deg− (a) = 2 − 1 = 1.

• For vertex e: deg− (e) − deg+ (e) = 4 − 3 = 1.

• For vertices b, c, d: deg− (v) = deg+ (v).

Since these conditions are met perfectly, an Euler path exists. It must start at vertex
a and end at vertex e.
Starting at vertex a and ending at vertex e, we can traverse all 12 distinct edges of
the graph exactly once. One such valid Euler path is:

a→d→b→a→e→d→e→b→c→b→e→c→e

This traverses the edges in the following order: (a, d), (d, b), (b, a), (a, e), (e, d), (d, e),
(e, b), (b, c), (c, b), (b, e), (e, c), (c, e).

Question-13

Consider the following directed graph. Find the shortest path between the vertices S
and T of the graph by Dijkstra’s algorithm.

2
1 2
E G
C
1
A
1
3 4
4 3
7 D
S 3
3
4 5 T
3 B
5
F

Solution: Let d(v) be the shortest distance from the source node S to node v. Initially,
d(S) = 0 and d(v) = ∞ for all other vertices.
The table below tracks the shortest distance to each node at every step. In each
row, the unvisited node with the smallest tentative distance is selected and its neigh-
bors are updated.
The shortest distance from S to T is 10.
Tracing back the distance updates reveals that there are three valid shortest paths
that all result in a total weight of 10:

16
 Selected Node S A B C D E F G T
Initial 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
S (d = 0) – 4 3 ∞ 7 ∞ ∞ ∞ ∞
B (d = 3) – 4 – ∞ 7 ∞ ∞ ∞ ∞
A (d = 4) – – – 5 7 ∞ ∞ ∞ ∞
C (d = 5) – – – – 7 6 ∞ ∞ ∞
E (d = 6) – – – – 7 – ∞ 8 10
D (d = 7) – – – – – – 12 8 10
G (d = 8) – – – – – – 12 – 10
T (d = 10) – – – – – – 12 – –
F (d = 12) – – – – – – – – –

• Path 1: S → A → C → E → T (Weights: 4 + 1 + 1 + 4 = 10)

• Path 2: S → D → T (Weights: 7 + 3 = 10)

• Path 3: S → B → D → T (Weights: 3 + 4 + 3 = 10)

Question-14

Let G be the directed graph given below. Use Dijkstra’s algorithm to find the shortest
path between the vertices A and H.

4 4 6
A C E G I
6 2
3
1 5 7 1 9 2

2 0 7
B D F H J
Solution: To find the shortest path, we initialize the distance to the source node A as
d(A) = 0 and all other nodes as ∞. We then iteratively relax the edges.
The shortest path is determined by following the predecessors of the relaxed dis-
tances:

• Path: A → C → B → D → F → G → E → H

• Total Weight: 4 + 3 + 2 + 0 + 2 + 4 + 1 = 16

17
 Step Node Neighbors Relaxed Distance Vector (A, B, C, D, E, F, G, H)
0 — — (0, ∞, ∞, ∞, ∞, ∞, ∞, ∞)
1 A C :0+4=4 (0, ∞, 4, ∞, ∞, ∞, ∞, ∞)
2 C B : 4 + 3 = 7, F : 4 + 6 = 10 (0, 7, 4, ∞, ∞, 10, ∞, ∞)
3 B D :7+2=9 (0, 7, 4, 9, ∞, 10, ∞, ∞)
4 D F :9+0=9 (0, 7, 4, 9, ∞, 9, ∞, ∞)
5 F G : 9 + 2 = 11 (0, 7, 4, 9, ∞, 9, 11, ∞)
6 G E : 11 + 4 = 15, H : 11 + 9 = 20 (0, 7, 4, 9, 15, 9, 11, 20)
7 E H : 15 + 1 = 16 (0, 7, 4, 9, 15, 9, 11, 16)
8 H Goal Reached (0, 7, 4, 9, 15, 9, 11, 16)

Question-15

Find the strongly connected components of the given digraph.

a b c

f e d
Solution: A strongly connected component (SCC) of a directed graph is a maximal
subgraph in which for every pair of vertices u and v, there is a directed path from u to
v and a directed path from v to u.
To find the SCCs of the given digraph, we group the vertices into sets where all
vertices in a set are mutually reachable:

• Observe the vertices on the left. There is a two-way connection between a and b
(a → b and b → a), meaning they can reach each other.

• Similarly, there is a two-way connection between a and f (a → f and f → a).

• By transitivity, b can reach f (via a) and f can reach b (via a). Thus, a, b, and f
are all mutually reachable.

• We must check if this component can be expanded. The vertices b and f have
outgoing edges to the right side of the graph (b → c, b → e, f → e). However, there
are no returning edges from {c, d, e} back to {a, b, f }.

• Therefore, no other vertices can be part of this mutual-reachability group. The

set {a, b, f } is a maximal strongly connected component.

• Now look at the remaining vertices on the right. There is a two-way connection
between c and e (c → e and e → c).

18
• We also have a path passing through d. There is an edge c → d and an edge
d → e.

• This creates a directed cycle: c → d → e → c. Because they form a continuous

loop, any vertex in {c, d, e} can reach any other vertex in that same set.

• Since there are no other vertices left in the graph to check, this forms our second
maximal strongly connected component.

The digraph has exactly two strongly connected components:

C1 = {a, b, f }

C2 = {c, d, e}

19