Gujarat Technological UniversitySummer 2026 examination

GTU BE04000261 Discrete Mathematics and Graph Theory Summer 2026 Question Paper & PDF

B.E. · Common Engineering · Semester 4 · Subject code BE04000261
Download official PDFView PDF here
Share with your class
Total
70 marks
To pass
23 marks (33%)
Duration
2.5 Hours 10:30 AM – 1:00 PM
Questions
5 with internal choice
No solutions on this paper yetNeed them for your exam? Ask once. Papers that students ask for are solved first, and we aim to add them within 24 hours.

Q.1

14 Marks
(a)
3 marks
Define surjective function. Check whether the function f: N→NN \to N defined by f(x)=2x−1f(x)=2x-1 is one-one and onto.
(b)
4 marks
Determine the relation perpendicular on the set L of lines in the plane are reflexive, symmetric, transitive, irreflexive.
(c)
7 marks
Define (1) Complete graph (2) Path (3) Null graph. Find the number of edges in a r-regular graph with n- vertices.

Q.2

14 Marks
(a)
3 marks
The chairs of an auditorium are to be labeled with an uppercase English letter followed by a positive integer not exceeding 100. What is the largest number of chairs that can be labeled differently?
(b)
4 marks
Identify the statement (¬q∧(p→q))→¬p(\neg q \wedge (p \to q)) \to \neg p is tautology or contradiction.
(c)
7 marks
Use a truth table to determine whether the following argument form is valid.
p→qp \to q
q→rq \to r
∴p→r\therefore p \to r
(c)
7 marks

Express the following using predicate, quantifier and logical connectives. Also verify the validity of the consequence.

1All parrots like fruit. My pet bird is not a parrot. Therefore, my pet bird does not like fruit.
2Every computer science major takes discrete mathematics. Natasha is taking discrete mathematics. Therefore, Natasha is a computer science major.

Q.3

14 Marks
(a)
3 marks

Find the number of mathematics students at a college taking at least one of the languages French, German, and Russian, given the following data: 65 study French, 45 study German, 42 study Russian, 20 study French and German, 25 study French and Russian, 15 study German and Russian, 8 study all three languages.

(b)
4 marks
Define Semigroup. Consider the set of positive integers N. Check (N,+)(N, +) is a semigroup. Is it monoid?
(c)
7 marks
Show that (R,+,×)(R, +, \times) is an integral domain, where R={a+b5/a, b∈Z}R = \{a + b\sqrt{5} / a,\ b \in \mathbb{Z}\}.
(a)
3 marks
If A,B,C are sets then prove that A∪(B∩C)=(A∪B)∩(A∪C)A \cup (B \cap C) = (A \cup B) \cap (A \cup C).
(b)
4 marks
Let g be a homomorphism from a group (G, *) to a group (H, Δ\Delta). Show that g(eG)=eHg(e_G) = e_H and for any a∈Ga \in G, g(a−1)=(g(a))−1g(a^{-1}) = (g(a))^{-1}.
(c)
7 marks
Define Group. Let Z5Z_5 denotes the integers modulo 5. Check whether Z5Z_5 is a group under addition.

Q.4

14 Marks
(a)
3 marks
Solve an−6 an−1+9 an−2=0a_n - 6\,a_{n-1} + 9\,a_{n-2} = 0.
(b)
4 marks
Let A be a given finite set and ρ(A)\rho(A) its power set. Let ⊆\subseteq be the set inclusion relation on the elements of ρ(A)\rho(A). Draw the Hasse diagram of (ρ(A),⊆)(\rho(A), \subseteq) for A={a,b,c}A=\{a,b,c\}.
(c)
7 marks
1Let
R={(1,1),(1,2),(2,1),(2,2),(3,3),(4,4),(5,5)}R = \{(1,1),(1,2),(2,1),(2,2),(3,3),(4,4),(5,5)\}
be the relation on A={1,2,3,4,5}A = \{1,2,3,4,5\}. Check whether the relation is an equivalence relation?
2Find out maximal compatibility blocks of following simplified graph of digraph.
GTU Discrete Mathematics and Graph Theory (BE04000261) Summer 2026 Question 4(c) Diagram
(a)
3 marks
Solve an+5 an−1+6 an−2=0a_n + 5\,a_{n-1} + 6\,a_{n-2} = 0.
(b)
4 marks
Let the relation R={(a,a),(a,b),(b,c),(c,c)}R = \{(a,a),(a,b),(b,c),(c,c)\} on A={a,b,c}A = \{a,b,c\}. Find the transitive closure of R.
(c)
7 marks

Let (L,≤)(L, \le) be a lattice. Show that for a,b,c∈La,b,c \in L, following inequalities holds.

ia⊕(b∗c)≤(a⊕b)∗(a⊕c)a \oplus (b * c) \le (a \oplus b) * (a \oplus c) and
iia∗(b⊕c)≥(a∗b)⊕(a∗c)a * (b \oplus c) \ge (a * b) \oplus (a * c).

Q.5

14 Marks
(a)
3 marks
Find the in-degree and out-degree of each vertex of the following graph. Also find d(v1,v3)d(v_1,v_3).
GTU Discrete Mathematics and Graph Theory (BE04000261) Summer 2026 Question 5(a) Diagram
(b)
4 marks
Find the reachable sets of all nodes for the given digraph
GTU Discrete Mathematics and Graph Theory (BE04000261) Summer 2026 Question 5(b) Diagram
(c)
7 marks
Define binary tree. In which order does a pre-order, in-order and post-order traversal visit the vertices of the ordered rooted tree T shown in figure?
GTU Discrete Mathematics and Graph Theory (BE04000261) Summer 2026 Question 5(c) Diagram
(a)
3 marks
A tree T has 3 vertices of degree 4, 5 vertices of degree 5. Find the number of pendant vertices in tree T.
(b)
4 marks
Check whether the following graphs are isomorphic?
GTU Discrete Mathematics and Graph Theory (BE04000261) Summer 2026 Question 5 OR (b) Diagram
(c)
7 marks
Define adjacency matrix. Warshall's algorithm to obtain path matrix from the adjacency matrix of following graph
GTU Discrete Mathematics and Graph Theory (BE04000261) Summer 2026 Question 5 OR (c) Diagram

Other Semester 4 subjects

BE Common

2140001
Mathematics-4
2140003
Engineering Economics and Management
BE04000101
Environmental Science, Sustainability and Renewable Energy
BE04000221
Operating System

Preparing with friends?

Send this paper to your class group. Every question has its own link.

About this paper

Official Gujarat Technological University (GTU) examination paper for Discrete Mathematics and Graph Theory (Summer 2026, B.E. · Common 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 official PDF All Discrete Mathematics and Graph Theory Papers (1) →Report a typo or correction
ViewDownload PDF