Discrete Mathematics 2018 Question Paper — Government College of Engi…

Instructions

• Attempt five questions in all selecting at least two questions from each Section.
• Each question carries 20 marks.
• Assume missing data suitably.

Questions

Section - A

Attempt at least two questions from this Section.

• Q1. (a) Show that the set $M_2 (Z)$ of all $2 \times 2$ matrices over integers is an abelian group under addition of matrices. (b) Prove that a non-empty subset $H$ of a group $G$ is a subgroup of $G$ if and only if (i) $ab \in H \quad \forall a, b \in H$ (ii) $a^{-1} \in H \quad \forall a \in H$ (c) Prove that $(2n + 7) < (n + 3)^2$ by using the principle of mathematical induction for all $n \in \mathbb{N}$. [20 marks]
• Q2. (a) Show that the set of all positive rational no.'s is a countably infinite set. (b) Show that the function $f: \mathbb{R} \to \mathbb{R}$ define by $f(x) = 2x^3 + 1$, $\forall x \in \mathbb{R}$ is a bijection. (c) Determine the no. of integers between 1 and 250 which are divisible by any of the integers 2, 3, 5, 7. [20 marks]
• Q3. (a) If 'x' is a finite set containing 'n' elements, then prove that its power set contains $2^n$ elements. (b) For $a/b, c/d \in \mathbb{Q}$, define a relation 'R' by $a/b \text{ R } c/d$ iff $ad = bc$. Show that R is an equivalence relation on $\mathbb{Q}$. (c) Prove that a field is an integral domain. [20 marks]
• Q4. (a) Prove that the cancellation laws hold in a ring R iff R has no left zero divisors. (b) Let $G$ and $G'$ be two groups and $f: G \to G'$ be a group homomorphism, then show that $f$ is an isomorphism iff $\text{Ker } f = \{e\}$. (c) Prove that any two left (right) cosets of a subgroup in a group are either identical or disjoint. [20 marks]

Section - B

Attempt at least two questions from this Section.

• Q5. (a) Prove that every cut-set in a connected graph G must contain at least one branch of every spanning tree of G. (b) Define the following terms: (i) Graphs (ii) Walk (iii) Path (iv) Circuits (v) Eular Graph (vi) Hamiltonian Circuit (vii) Trees (c) Find the shortest path in the given below weighted graph using Djikstra's Algorithm. (Use A as starting Point). [20 marks]
• Q6. (a) Prove that every circuit has an even number of edges in common with every cutset. (b) Prove that a given connected graph G is an Eular graph iff all vertices of G are of even degree. (c) State and prove Euler's formula. [20 marks]
• Q7. (a) Write in detail about Konigsberg bridge problem. (b) Prove that a tree with n vertices has $n - 1$ edges. (c) Given an example of a graph that has (i) Both a Hamiltonian Circuit and Eular Circuit. (ii) Eular Circuit but not Hamiltonian Circuit. [20 marks]
• Q8. (a) What is Traveling - Salesman Problem? (b) Prove that every connected graph has at least one spanning tree. (c) Prove that any connected graph with n vertices and $n - 1$ edges is a tree. [20 marks]

Related pages

• Discrete Mathematics syllabus
• All Discrete Mathematics papers from 2018

Other years

• Discrete Mathematics 2022 question paper — end-term
• Discrete Mathematics 2018 question paper — end-term