N2113112 · 60 marks · 3 hrs
Discrete Structures & Graph Theory
Exam: 19 Nov 2026 · 14:30-16:30 · Mumbai University, B.E. AI & DS Sem III (NEP-2020).
Units & topics
| Unit | Title & topics |
|---|---|
| Unit 1 | Crisp Set Theory and Logic Mathematical induction, Logical equivalence, Truth table / access expression |
| Unit 2 | Mathematical Relations Transitive closure / Warshall, Hasse diagram / lattice, Equivalence relation |
| Unit 3 | Functions Function composition, Mapping: function / one-one / onto / many-one |
| Unit 4 | Counting Inclusion–exclusion, Recurrence relation, Pigeonhole principle |
| Unit 5 | Algebraic Structures Group under × mod 7, Ring |
| Unit 6 | Graph Theory Graph isomorphism, Euler / Hamiltonian paths & circuits |
Question papers
Scanned originals as printed. Open a paper for preview, or download the PDF.
Dec 2025 · QP 99814
60 marks · 3 hrs · verified — scanned original
May 2026 · QP 14827
60 marks · 3 hrs · verified — scanned original
Most-asked topics
How many questions each topic got in Dec 2025 and May 2026. History, not a prediction — nothing here is guaranteed to appear next.
| Topic | Dec 2025 | May 2026 | Total | Marks |
|---|---|---|---|---|
| Mathematical induction | 1 | 1 | 2 | 14 |
| Logical equivalence | 1 | 1 | 2 | 10 |
| Transitive closure / Warshall | 1 | 1 | 2 | 16 |
| Hasse diagram / lattice | 1 | 1 | 2 | 14 |
| Equivalence relation | 1 | 1 | 2 | 10 |
| Function composition | 1 | 1 | 2 | 14 |
| Inclusion–exclusion | 1 | 1 | 2 | 16 |
| Recurrence relation | 1 | 1 | 2 | 14 |
Question sets
Topic-wise question sets from the two papers — questions only.
DSGT — Topic-wise Question Sets (Dec 2025 + May 2026)
9 pages · Scanned university question papers, grouped by topic · Questions only — no answers
All questions — Dec 2025 + May 2026
28 questions, quoted as printed. No answers are published on this site.
| Q | Topic | Question | Marks | Paper |
|---|---|---|---|---|
| Q1a | Equivalence relation | A student-feedback system groups teacher responses using the rule: Two responses x and y are "similar" if they fall in the same satisfaction band (e.g., 1–2 = Low, 3 = Medium, 4–5 = High). i. Using definitions of reflexive, symmetric, transitive, determine whether "similarity" is an equivalence relation. ii. Explain the classroom-level meaning of each property. iii. Discuss how violating any property affects AI-based feedback analytics and dashboard reports. | 5 | dsgt-dec2025 |
| Q1b | Logical equivalence | A college bus attendance system gives "Boarded = True" when: P: The student taps RFID card; Q: Bus mentor manually verifies student; R: The system logs boarding record. The transport officer rewrites: (P ∨ Q) → R ≡ (P → R) ∧ (Q → R). i. Prove the above using logical equivalence laws step-by-step. ii. Explain how this version ensures no boarding method is ignored, improves data consistency, and reduces false "absent" cases. | 5 | dsgt-dec2025 |
| Q1c | Pigeonhole principle | A programming contest has 240 participants and 12 judging terminals. i. Using Pigeonhole Principle, find the minimum number of contestants who must end up using the same terminal. ii. Explain how this insight helps in contest scheduling, load balancing, and avoiding terminal bottlenecks. | 5 | dsgt-dec2025 |
| Q1d | Truth table / access expression | A Cybersecurity lab access is granted if: P: Student has lab clearance; Q: Student has signed NDA; R: Student completed safety briefing. Access expression: A = (P ∧ Q) ∨ (P ∧ R). i. Construct truth table for A. ii. Identify combinations where access is wrongly granted. iii. Explain consequences for security, safety compliance, and audit records. | 5 | dsgt-dec2025 |
| Q1e | Mapping: function / one-one / onto / many-one | Students are assigned to specialization tracks based on the following rule: Score in Coding ≥ 80 → Software Track; Score in Networks ≥ 75 → Network Security; Score in Math ≥ 85 → Data Science. (Priority: Data Science > Software > Network Security). Given sample data (Coding, Networks, Math): S1: (85, 60, 70); S2: (65, 80, 90); S3: (82, 78, 88); S4: (78, 76, 60). i. Map each student to a track. ii. Check if the mapping is function / one-one / onto / many-one. iii. Explain how these properties impact batch size planning, mentor allocation, and fairness. | 5 | dsgt-dec2025 |
| Q2a | Inclusion–exclusion | A campus event app records students who use three app sections: E: Event Announcements; C: Clubs & Communities; R: Reels / Short videos. Survey data table: E 140; C 110; R 120; E∩C 65; E∩R 70; C∩R 55; Total Students 200. i. Using inclusion–exclusion, compute how many students use all three sections. ii. Find students who use only one section. iii. Explain how this analysis helps app developers and event committees design targeted notifications and UI improvements. | 8 | dsgt-dec2025 |
| Q2b | Function composition | A university assigns raw marks to final grades using: Moderation function M(x) = x + 5; Weight conversion W(x) = 0.4x. Compute the compositions: i. W ∘ M; ii. M ∘ W; iii. M ∘ M; iv. W ∘ W. Interpret each composition in the grading context, and discuss which are academically meaningful and which may distort scores. | 7 | dsgt-dec2025 |
| Q3a | Transitive closure / Warshall | A Data Science program has a prerequisite network among modules: M1: Python Basics; M2: DS Foundation; M3: Machine Learning; M4: Deep Learning; M5: Deployment. Given relation R = {(1,2), (2,3), (3,4), (4,5), (1,1), (3,3), (5,5)}. i. Apply Warshall's Algorithm to compute transitive closure. ii. For each Mi, list all modules it can unlock. iii. Identify root modules and terminal modules. iv. Explain how this helps curriculum planners maintain valid learning paths. | 8 | dsgt-dec2025 |
| Q3b | Hasse diagram / lattice | Data storage providers offer plans of sizes: S = {1 TB, 2 TB, 4 TB, 8 TB, 16 TB}. Relation a | b (a divides b). i. Draw the Hasse diagram. ii. List all (a,b) where a divides b. iii. Check whether S forms a lattice (meet & join for every pair). iv. Explain impact on designing upgrade/downgrade recommendations and plan combinations in the storage app. | 7 | dsgt-dec2025 |
| Q4a | Group under × mod 7 | A QR-based token system transforms token number a into: T(a) = (a × k) mod 7, with a ∈ {1…6}. i. Construct multiplication table (×_7). ii. Find modular inverses of 2, 3, 5 under mod 7. iii. Determine if ({1…6}, ×_7) forms a group. iv. Comment on whether this token transformation ensures reversibility, forgery prevention, and predictable validation. | 8 | dsgt-dec2025 |
| Q4b | Mathematical induction | A student deposits savings in a fund according to: Daily saving: S_n = 4n − 1. They want to verify if S_n is always odd for all natural numbers n. i. Prove the statement using mathematical induction. ii. Explain the meaning for planning weekly budgets and long-term savings. | 7 | dsgt-dec2025 |
| Q5a | Graph isomorphism | Two lab surveillance networks are modeled as undirected graphs: Graph G_1 (Cameras A,B,C,D): A: B, C; B: A, D; C: A, D; D: B, C. Graph G_2 (Cameras P,Q,R,S): P: Q, R; Q: P, S; R: P, S; S: Q, R. i. Determine whether G_1 and G_2 are isomorphic. ii. If yes, provide the mapping. iii. Explain how detecting isomorphic patterns helps in reusing surveillance layouts and minimizing storage of duplicate designs. | 8 | dsgt-dec2025 |
| Q5b | Recurrence relation | A student club records followers using recurrence: F_n = 4F_n−1 − 4F_n−2. With, F_0 = 10 (core team); F_1 = 30 (after first promotion). i. Solve the recurrence relation. ii. Describe growth pattern (linear/exponential). iii. Comment whether such growth is realistic for a campus club in long term. | 7 | dsgt-dec2025 |
| Q6a | Ring | The college uses modulo-6 operations to rotate lab batches: Addition: a ⊕ b = (a + b) mod 6; Multiplication: a ⊗ b = (a × b) mod 6. i. Check if (Z_6, ⊕) is an abelian group. ii. Check closure, associativity of (Z_6, ⊗). iii. Verify distributive property of ⊗ over ⊕. iv. Conclude whether (Z_6, ⊕, ⊗) forms a ring, and discuss why this matters in designing timetable rotation logic. | 8 | dsgt-dec2025 |
| Q6b | Euler / Hamiltonian paths & circuits | A research conference venue is modeled as graph V = {A,B,C,D,E,F} with edges: E = {AB, AC, BC, BD, CE, DE, DF, EF}. i. Determine existence of Euler Path, Euler Circuit, Hamiltonian Path, Hamiltonian Circuit. ii. Construct them if they exist. iii. Explain what this means for planning visitor flow, inspection rounds, and avoiding repeated walking paths. | 7 | dsgt-dec2025 |
| Q1a | Equivalence relation | A digital geometry learning platform groups polygons based on the number of sides for automatic classification and retrieval. Let A be the set of all polygons. A relation R is defined on A as: R = {(P_1, P_2): P_1 and P_2 have the same number of sides}. Based on this classification system: 1. Analyze whether the relation R is an equivalence relation on A. 2. Verify the properties of reflexivity, symmetry, and transitivity. 3. Construct suitable equivalence classes for triangles, quadrilaterals, and pentagons. 4. Interpret how equivalence relations help organize geometric data in digital systems. | 5 | dsgt-may2026 |
| Q1b | Logical equivalence | A software security system uses logical rules to decide whether access should be granted, denied, or forwarded for further verification. Consider the following logical expressions: ((p → q) → r) and (p ∧ ¬q) ∨ r. Using a series of logical equivalences, prove that the two expressions are logically equivalent. Also interpret how logical equivalence helps simplify decision rules in software systems. | 5 | dsgt-may2026 |
| Q1c | Pigeonhole principle | A quality control department stores 10 pairs of socks of different colors in a drawer for packaging verification. Using the Pigeonhole Principle, analyze the minimum number of socks that must be selected randomly to guarantee that at least one matching pair of the same color is obtained. Justify your answer with suitable reasoning. | 5 | dsgt-may2026 |
| Q2a | Inclusion–exclusion | A pharmaceutical company conducts a drug trial on 1000 people to analyze the side effects of a newly developed medicine. The following observations are recorded: 122 people develop symptom A; 88 people develop symptom B; 112 people develop symptom C; 27 people develop both symptoms A and C; 29 people develop both symptoms A and C; 32 people develop both symptoms B and C; 10 people develop all three symptoms A, B, and C. Using the Principle of Inclusion and Exclusion: 1. Analyze how many people develop at least one symptom. 2. Determine the number of people who show exactly one symptom. 3. Construct a Venn diagram and fill all regions appropriately. | 8 | dsgt-may2026 |
| Q2b | Function composition | A retail store offers seasonal discounts on clothing items. A customer wants to purchase a shirt priced at Rs.1000. The store first provides a 15% discount, after which an 8% sales tax is applied to the discounted price. Based on this shopping scenario: 1. Develop suitable mathematical functions representing the discount process and the tax calculation process. 2. Construct the composite function representing the final cost of the shirt. 3. Determine the final amount to be paid by the customer. 4. Analyze how composite functions help automate billing systems in retail applications. | 7 | dsgt-may2026 |
| Q3a | Transitive closure / Warshall | A domestic airline company maintains a directed flight network among four cities: V = {a, b, c, d}. The direct flight connections are represented by the relation: R = {(a,b), (b,d), (d,c), (d,a)}. The company wants to analyze all possible direct and indirect travel routes, including circular journeys. Based on the given flight network: 1. Identify and explain the concept of reachability / transitive closure used in the graph. 2. Determine all possible ordered pairs of cities connected through: direct routes, routes with layovers, and circular routes. 3. Analyze how graph connectivity helps optimize airline route planning. 4. Represent the final connectivity relation for the graph. | 8 | dsgt-may2026 |
| Q3b | Hasse diagram / lattice | A cloud access-control system organizes permission levels using divisibility-based hierarchy. The permission levels are: A = {1,2,3,6,12,24,36,72}. A relation R is defined on A as: (x,y) ∈ R if x | y. Based on this hierarchy: 1. Write all ordered pairs of relation R. 2. Construct the Hasse Diagram of the poset. 3. Analyze whether the given poset forms a lattice. 4. Justify your answer using suitable meet and join examples. | 7 | dsgt-may2026 |
| Q4a | Group under × mod 7 | A cryptographic system uses non-zero residue classes modulo 7 for secure key generation. Consider the set: G = {1,2,3,4,5,6} under multiplication modulo 7. Based on this system: 1. Construct the multiplication table of G under multiplication modulo 7. 2. Determine the multiplicative inverses of 2,3,5, and 6. 3. Analyze whether G forms a cyclic group. 4. If it is cyclic, identify at least one generator and justify your answer. | 8 | dsgt-may2026 |
| Q4b | Mathematical induction | A data analyst observes that the cumulative computational cost of a repeated process is modeled by the series: Σ_r=1^n r(r + 3). The analyst claims that for every positive integer n, Σ_r=1^n r(r + 3) = (1/3)n(n + 1)(n + 5), n ≥ 1, n ∈ N. Using the principle of mathematical induction: 1. Verify the result for the base case. 2. Prove the inductive step. 3. Conclude that the formula is valid for all n ≥ 1. 4. Interpret how induction helps validate formulas in algorithm analysis. | 7 | dsgt-may2026 |
| Q5a | Graph isomorphism | A computer networking company proposes two communication network layouts represented by graphs G_1 and G_2. The organization wants to verify whether both network structures provide the same connectivity pattern even though the device labels are different. The graphs are represented as: V(G_1) = {A,B,C,X,Y,Z}; E(G_1) = {(A,X), (A,Y), (B,X), (B,Y), (C,Y)}; V(G_2) = {1,2,3,4,5,6}; E(G_2) = {(1,4), (1,5), (2,4), (2,5), (3,5)}. Based on the above network structures: 1. Define isomorphism of graphs. 2. Analyze whether graphs G_1 and G_2 are isomorphic. 3. If they are isomorphic, determine a valid one-to-one correspondence between the vertices. 4. Justify your answer by comparing degree sequence and adjacency preservation. | 8 | dsgt-may2026 |
| Q5b | Recurrence relation | A financial analytics company models the quarterly growth of a digital investment portfolio using a recurrence relation. Let F_n represent the portfolio value during the n^th quarter. The growth pattern is governed by: F_n = 3F_n−1 + 10F_n−2 + 7·5^n, with initial conditions: F_0 = 4, F_1 = −3. Based on this predictive model: 1. Solve the given recurrence relation using an appropriate method. 2. Determine the general expression for F_n. 3. Analyze the effect of the exponential forcing term 7·5^n on the sequence growth. 4. Interpret how recurrence relations are useful in financial forecasting and computational modeling. | 7 | dsgt-may2026 |
| Q6a | Ring | A cryptographic system uses arithmetic operations on residue classes modulo 4 for encoding and verification. Consider the set: Z_4 = {0,1,2,3} with addition and multiplication defined modulo 4. Based on this algebraic structure: 1. Construct the addition and multiplication tables for Z_4. 2. Verify whether Z_4 satisfies the required ring properties. 3. Analyze the role of additive identity, additive inverse, multiplicative associativity, and distributive laws. 4. Conclude whether Z_4 forms a ring under addition and multiplication modulo 4. | 8 | dsgt-may2026 |
| Q6b | Euler / Hamiltonian paths & circuits | A city transport authority is analyzing a road network connecting six important locations A, B, C, D, E, and F. The network is represented by the following graph: [graph figure not printed in the paper — no figure appears under this line in the scan]. Based on the given road network: 1. Determine whether the graph has an Euler Path. 2. Determine whether the graph has an Euler Circuit. 3. Determine whether the graph has a Hamiltonian Path. 4. Determine whether the graph has a Hamiltonian Circuit. 5. Justify your answer using degree of vertices and graph traversal conditions. | 7 | dsgt-may2026 |