Discrete Mathematics 2022 Question Paper — Government College of Engi…
The 2022 Discrete Mathematics previous year question paper (Government College of Engineering and Technology, Jammu), with every question and its marks.
- University: Government College of Engineering and Technology, Jammu
- Subject: Discrete Mathematics
- Course: Discrete Mathematics
- Branch: COMPUTER ENGINEERING
- Year: 2022
- Paper: end-term
- Duration: 180 minutes
- Total marks: 100
Instructions
- Attempt five questions in all selecting at least two questions from each Section.
- Each question carries 20 marks.
Questions
Section A
- Q1. (a) State and prove De Morgan's laws of sets and Distributive Laws of sets. (b) In a group of 120 people, 50 speak English, 70 speak Hindi, 20 speak French, 5 speak English and French, 20 speak English and Hindi, 10 speak Hindi and French and 3 speak all three languages. Then how many speak (i) Hindi alone (ii) French alone (iii) English but not Hindi (iv) Hindi but not French [20 marks]
- Q2. (a) Prove that the set of rational numbers is countable. (b) Find the number of integers between 1 and 500, both inclusive (i) which are divisible, either by 10, 15 or 25. (ii) which are divisible neither by 10, 15 nor 25. [20 marks]
- Q3. (a) Prove that in a group G, (i) identity element is unique. (ii) inverse of each element of G is unique. (b) Prove that a non-empty subset H of a group G is a subgroup of G if and only if the following two conditions hold: (i) $ab \in H, \forall a, b \in H$ (ii) $a^{-1} \in H, \forall a \in H$. [20 marks]
- Q4. (a) Define Centre of Group. Show that Centre of a group G is a normal subgroup of G. (b) Prove that a commutative ring with unity is an integral domain iff cancellation laws hold in R. [20 marks]
Section B
- Q5. (a) Define degree of a vertex. Prove that the number of odd degree vertices in a graph is always even. (b) Is it possible to construct a graph with 22 edges such that four of its vertices are of degree 5, two vertices of degree 7 and remaining vertices with degree 3? Justify your answer. [20 marks]
- Q6. (a) Prove that if G is a simple graph with n ($n \ge 3$) vertices and if $d(v) \ge \frac{n}{2}$ for each vertex v, then G is Hamiltonian. (b) Determine the shortest path from a to h of the following directed graph using Dijkstra's algorithm: [20 marks]
- Q7. (a) State and prove Euler's formula for connected graphs. (b) Explain Chinese Postman Problem by giving a suitable example. [20 marks]
- Q8. (a) Prove that a graph with n vertices, n-1 edges and no cycles is connected. (b) Define cut set. Prove that every cycle in a connected graph G has even no. of edges in common with any cut set of G. [20 marks]
Related pages
Other years
- Discrete Mathematics 2018 question paper — end-term
- Discrete Mathematics 2018 question paper — end-term