Discrete Mathematics
CSE · Final · Spring 26
Batch 68
Read the questions as text
Read off the PDF by AI, so it may have mistakes. The PDF is the original.
Daffodil International University
Faculty of Science & Information Technology
Department of Computer Science & Engineering
Final Examination, Spring 2026
Course Code: CSE212, Course Title: Discrete Mathematics
Level: 2, Term: 1
Batch: 68
Time: 02:00 Hrs
Marks: 40
Answer ALL Questions
[The figures in the right margin indicate the full marks and corresponding course outcomes. All portions of each question must be answered sequentially.]
1. a) Consider the following relation on the set A={1,2,3,4,5,6}:
R={(1,1), (1,5), (2,2), (2,3), (2,6), (3,2), (3,3), (3,6), (4,4), (5,1), (5,5), (6,2), (6,3), (6,6)}
Determine whether or not the relation R on A is: (a) reflexive (b) symmetric (c) antisymmetric (d) transitive. Justify your answers. [4] [CO2]
b) Use mathematical induction to prove that the following equation holds for all nonnegative integers n.
1^2 + 3^2 + 5^2 + ... + (2n - 1)^2 = ((n + 1)(2n + 1)(2n + 3)) / 3 [6]
2. a) Prove whether the following graphs G and H are Isomorphic or not. [6]
[Figure: Graph G and Graph H]
b) Find out if the graph below is Eulerian. If so, write the sequence of vertices of an Eulerian circuit. If not, explain why it isn't Eulerian. [4] [CO3]
[Figure: A connected graph with vertices a, b, c, d, e, f, g, h]
3. a) Apply Kruskal's algorithm to construct a spanning tree for the given weighted graph [7]
[Figure: A weighted undirected graph with nodes a, b, c, d, e, f, g and weighted edges]
b) In the road network of Bangladesh, vertices represent major intersections in cities such as Dhaka, Chattogram, Rajshahi and edges represent roads connecting them. Some roads are one-way (certain roads in Dhaka city) while others are two-way highways (Dhaka-Chattogram highway). Assume that there is at most one road connecting any two intersections.
What type of graph is used to model this road network? Justify your answer. [3]
4. a) Consider a group of 7 students where each student writes letters to exactly 3 other students and, at the same time, receives letters from exactly 3 students. Is it possible to model this situation using a graph? If possible to model, then draw the graph. If you think it's not possible then explain with proof why it is not possible. [3]
b) "The Bengal Express" is a logistics company based in Dhaka. They need to map out the most efficient delivery route to different regional hubs across Bangladesh. You have been provided with the highway network map, where the cities represent nodes and the two-way highways represent undirected edges. The driving distances between the connected cities are given in kilometers. [7] [CO3]
The Highway Network Data:
Node | Regional Hub | Connecting Highways & Distances (km)
A | Dhaka | B (120), C (150), D (80)
B | Mymensingh | A (120), E (110)
C | Sylhet | A (150), E (190), F (210)
D | Comilla | A (80), G (100), H (140)
E | Bogura | B (110), C (190), F (105)
F | Rangpur | E (105), C (210)
G | Chittagong | D (100), H (90)
H | Cox's Bazar | D (140), G (90)
Now, apply the shortest path algorithm to find the shortest path from Dhaka to the Rangpur regional hub along with the distance in km.