UnFoldPrep
Browse Archive
Gujarat Technological UniversityWinter 2025 Examination

GTU 3140708 Discrete Mathematics (DM) Winter 2025 Paper Solution & PDF

B.E. · Computer Engineering · Semester 4 · Subject Code: 3140708
Download Official GTU PDF
Share:
Total Marks70 MarksExternal theory exam
Passing Marks23 Marks33% minimum cutoff
Exam Duration2.5 Hours2:30 PM – 5:00 PM
Paper Structure5 QuestionsWith internal OR choices
Jump toQ1Q2Q3Q4Q5

Question 1

14 MarksMedium
(a)
Draw the graph with 4 nodes and 7 edges.
3 Marks
(b)

Define simple graph, degree of a vertex, finite and infinite graphs and complete graph.

4 Marks
(c)
(
i)If A = B = {1, 2, 3, 5, 6, 10, 15, 30} and relation R defined as a/b, where a∈A and b∈B. Find the relation matrix.
ii)Solve the recurrence relation an - 3an-1 = 2, n ≥ 1, a0 = 1.
7 Marks

Question 2

14 MarksMedium
(a)

Let A, B and C be the sets such that (A∩B∩C) = ∅, (A∩B) ≠ ∅, (A∩C) ≠ ∅, (B∩C) ≠ ∅. Draw the corresponding venn diagram.

3 Marks
(b)

Define subgroup of a group. Also, show that the subset H of a group of integers I is a subgroup under addition, where H = {...., -2m, -m, 0, m, 2m, .....}.

4 Marks
(c)
How many integers between 1 to 2000 are divisible by 2, 3, 5 or 7.
7 Marks
OR OPTION
(c)
Using venn diagram, prove the following
i)A∪(B∩C) = (A∪B)∩(A∪C)
ii)A⊕(B⊕C) = (A⊕B)⊕C
7 Marks

Question 3

14 MarksMedium
(a)
Check whether the proposition ((pνq)Λ∼p)→q is contradiction, tautology or
contingency.
3 Marks
(b)
Show that the proposition (p→(q→r))→((p→q)→(p→r)) is a tautology.
4 Marks
(c)

Let A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 18, 24} be ordered by the relation x divides y. Show that the relation is partial ordering and draw the Hasse diagram.

7 Marks
OR OPTION
(a)
Show that the propositions p→q and ∼pvq are logically equivalent.
3 Marks
(b)
Negate (opposite) each of the following statements
i)∀ x, |x| = x
ii)∃ x, x2 = x
iii)If there is a riot, then someone killed.
iv)It is day light and all the people are arisen.
4 Marks
(c)
Solve the following recurrence relation
i)an - 7an-1 + 10an-2 = 0 given that a0 = 0, a1 = 3.
ii)an - 4an-1 + 4an-2 = 0 given that a0 = 1, a1 = 6.
7 Marks

Question 4

14 MarksMedium
(a)
Explain Partially order relation, Poset and Hasse diagram with example(s)
3 Marks
(b)
Explain the regular graph and complete bipartite graph with example(s).
4 Marks
(c)

Define tree and root. Also draw a tree with 10 vertices which has vertices either of degree 1 or of degree 3. Is it possible to draw a same type of tree with 11 vertices?

7 Marks
OR OPTION
(a)

Let n be a positive integer, Sn be the set of all divisors of n. Let D denote the relation of division. Draw the lattices for

i)n = 24,
ii)n = 30
3 Marks
(b)
Draw the following grapghs
i)K3,4 Marks
ii)K4,4 Marks
iii)K5,4 Marks
iv)K5
12 Marks
(c)
Find minimum spanning tree for the weighted graph given below
7 Marks

Question 5

14 MarksMedium
(a)
Define abelian group for any non empty set.
3 Marks
(b)

If G = {0, 1, 2, 3, 4, 5, 6, 7} and operation +8 is an addition modulo 8, then show that (G, +8) is an abelian group.

4 Marks
(c)

Consider the set (C, +, . ), where C is the set of complex numbers and + and . are ordinary addition and multiplication operation. Show that (C, +, . ) is a field.

7 Marks
OR OPTION
(a)

Let Q+ be the set of all positive rational numbers and ∗ be a binary operation on Q+ defined by a∗b = ab/3 , then show that (Q+, ∗) is an abelian group.

3 Marks
(b)
Define cyclic group and show that the following groups are cyclic groups
i)Third roots of unity i.e. G = {1, ω, ω 2}, ω3 =1 Marks
ii)G = {1, -1, i, -i}, where i2 = -1
1 Marks
(c)

Show that R = {a+b√2; a, b ∈ I} is an integral domain but not a field under the binary operations + (usual addition) and . (usual multiplication).

7 Marks
College Exam Groups

Studying for Discrete Mathematics?

Circulate this solved paper with KaTeX formulas and 1-click AI step solvers to your batchmates on WhatsApp or Telegram.

Related papers

About this Examination Paper & Attribution

Official Gujarat Technological University (GTU) examination paper and step-by-step solutions for Discrete Mathematics (DM) (Winter 2025, B.E. · Computer Engineering, Sem 4). Features complete 70-mark regular & remedial examination pattern, official marking distribution across all 5 questions, and direct 1-click official PDF download.

Transcribed for student exam preparation from Gujarat Technological University official examination archives. Questions, syllabus guidelines, and curriculum marking schemes remain the intellectual property of Gujarat Technological University.

Download PDF