Code: 105304Computer Science & Eng.3rd Semester8 Examination Papers

Discrete Mathematics

Official Bihar Engineering University examination question papers, marks distribution, and questions transcript. Available exam sessions: 2025, 2024, 2023, 2022, 2019, 2018, 2016, 2015.

Exam Year:

Get Instant AI Answers on this Paper

Open BEU Connect Android app to solve any numerical or derive formulas step by step.

Ask AI in App
Official Exam Paper TranscriptB. Tech 3rd Semester Examination, 2025
Bihar Engineering University, Patna
B.Tech 3rd Semester Examination, 2025

Discrete Mathematics and Graph Theory

Time: 03 HoursCode: 105304Full Marks: 70

Instructions:

  1. The marks are indicated in the right-hand margin.
  2. There are NINE questions in this paper.
  3. Attempt FIVE questions in all.
  4. Question No. 1 is compulsory.
Q.1 Choose the correct option/answer the following (Any seven question only):[2×7=14]

  1. If A = {1,2,3}, how many subsets does A have?

    1. 3
    2. 8
    3. 6
    4. 9

  2. Principle of induction is used to prove statements about

    1. Real numbers
    2. Complex numbers
    3. Natural numbers
    4. Integers only

  3. The base step in induction verifies

    1. All cases
    2. Recursive step
    3. First case
    4. Final step

  4. p→q is false when

    1. p = T, q = T
    2. p = T, q = F
    3. p = F, q = T
    4. p = F, q = F

  5. Contrapositive of p→q is

    1. ¬p→¬q
    2. q→p
    3. ¬q→¬p
    4. p→¬q

  6. A group must satisfy

    1. Closure only
    2. Closure + Associativity
    3. Closure + Associativity + Identity + Inverse
    4. Commutativity

  7. Homomorphism preserves

    1. Elements
    2. Size
    3. Structure
    4. Order only

  8. A graph with no cycles is called

    1. Complete graph
    2. Bipartite graph
    3. Tree
    4. Directed graph

  9. Maximum edges in a simple graph with n vertices

    1. n
    2. n2
    3. n(n−1)/2
    4. 2n

  10. Degree sum formula states

    1. Sum of degrees = n
    2. Sum of degrees = edges
    3. Sum of degrees = 2 × edges
    4. Sum of degrees = vertices2
Q.2 (a) Prove by induction: 1/(1.2) + 1/(2.3) + ··· + 1/(n(n+1)) = n/(n+1)[7]
(b) Solve the recurrence relation yn+2 − 5yn+1 + 6yn = 5n subject to the condition y0 = 0, y1 = 2.[7]
Q.3 (a) Prove that every finite subset of a lattice has an LUB and a GLB.[7]
(b) In a Lattice if a ≤ b ≤ c, then show that (a ∨ b) ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c) = b.[7]
Q.4 (a) State and prove Lagrange's theorem for group. Is the converse true?[7]
(b) Let G be the set of all non-zero real number and let a * b = ab/2. Show that (G,*) be an abelian group.[7]
Q.5 (a) Prove that a simple graph with n vertices and k components can have at most (n−k)(n−k+1)/2 edges.[7]
(b) Prove that a connected graph G is Euler graph if and only if every vertex G is of even degree.[7]
Q.6 (a) Let (A, ≤) be a partially ordered set. Let ≤ be a binary relation on A such that for a and b in A, a is related to b iff b ≤ a. Show that ≤ is partially ordered relation.[7]
(b) Show that ((p ∨ q) ∧ (∼ p ∧ (∼ q ∨ ∼ r))) ∨ (∼ p ∧ q) ∨ (∼ p ∨ r). Is a tautology without using the truth table.[7]
Q.7 (a) If f: A → B, g: B → C are invertible functions, then show that gof: A → C is invertible and (gof)-1 = f-1og-1.[7]
(b) Determine whether the following function is a bijection from R to R: f(x) = (x2+1)/(x2+2).[7]
Q.8 (a) Rewrite the following arguments using quantifiers, variables and predicate symbols: (i) All birds can fly (ii) Some men are genius (iii) Some numbers are not rational[7]
(b) Write the symbolic form and negate the following statements: (i) Everyone who is healthy can do all kinds of work (ii) Some people are not admired by everyone (iii) Everyone should help his neighbours, or his neighbours will not help him[7]
Q.9 Write short note on any two of the following:[7×2=14]
  1. Euler Graph and Hamiltonian Graph
  2. Homomorphism and Isomorphism Graph
  3. Planar and Complete Bipartite Graph
  4. Adjacency matrix of a graph

Related Official Syllabus

Discrete Mathematics and Graph Theory

105304

Official BEU curriculum units & topics for this examination subject.

Unit 1.0: Sets, Relation and Function

Operations and Laws of Sets • Cartesian Products • Binary Relation, Partial Ordering Relation, Equivalence Relation • Image of a Set • Sum and Product of Functions • Bijective functions, Inverse and Composite Function • Size of a Set, Finite and infinite Sets • Countable and uncountable Sets • Cantor's diagonal argument and The Power Set theorem • Schroeder-Bernstein theorem

Unit 2.0: Principles of Mathematical Induction

The Well-Ordering Principle • Recursive definition • The Division algorithm: Prime Numbers • The Greatest Common Divisor: Euclidean Algorithm • The Fundamental Theorem of Arithmetic • Basic counting techniques: inclusion and exclusion • Pigeon-hole principle • Permutation and combination

Unit 3.0: Propositional Logic

Syntax, Semantics • Validity and Satisfiability • Basic Connectives and Truth Tables • Logical Equivalence: The Laws of Logic • Logical Implication • Rules of Inference • The use of Quantifiers

Unit 4.0: Proof Techniques

Some Terminology • Proof Methods and Strategies • Forward Proof • Proof by Contradiction • Proof by Contraposition • Proof of Necessity and Sufficiency

Unit 5.0: Algebraic Structures and Morphism

Algebraic Structures with one Binary Operation • Semi Groups, Monoids, Groups • Congruence Relation and Quotient Structures • Free and Cyclic Monoids and Groups • Permutation Groups, Substructures, Normal Subgroups • Algebraic Structures with two Binary Operation • Rings, Integral Domain and Fields • Boolean Algebra and Boolean Ring • Identities of Boolean Algebra, Duality • Representation of Boolean Function • Disjunctive and Conjunctive Normal Form

View Complete 3rd Semester Syllabus

Prepare Better with BEU Connect

  • Download papers for 100% offline study
  • Ask AI for step-by-step problem breakdown
  • Attempt official GATE CBT mock tests
  • Calculate SGPA and track attendance
Download Android App