Discrete Mathematics 2025

(a) If $A = \{1, 2, 3\}$, how many subsets does $A$ have?

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

(b) Principle of induction is used to prove statements about

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

(c) The base step in induction verifies

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

(d) $p \rightarrow q$ is false when

1. $p = \text{T}, q = \text{T}$
2. $p = \text{T}, q = \text{F}$
3. $p = \text{F}, q = \text{T}$
4. $p = \text{F}, q = \text{F}$

(e) Contrapositive of $p \rightarrow q$ is

1. $\sim p \rightarrow \sim q$
2. $q \rightarrow p$
3. $\sim q \rightarrow \sim p$
4. $p \rightarrow \sim q$

(f) A group must satisfy

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

(g) Homomorphism preserves

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

(h) A complete bipartite graph $K_{3,3}$ has

1. Complete graph
2. Bipartite graph
3. 9 edges
4. Regular graph

(i) Maximum number of edges in a simple graph with $n$ vertices

1. $n$

2. $n^2$

3. $n(n-1)/2$

4. $2n$

(j) Degree sum formula states

1. Sum of degrees $= n$
2. Sum of degrees $= \text{edges}$
3. Sum of degrees $= 2 \times \text{edges}$
4. Sum of degrees $= \text{vertices}$

(a) Prove by induction $\frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \dots + \frac{1}{n(n+1)} = \frac{n}{n+1}$

(b) Solve the recurrence relation $y_{n+2} - 5y_{n+1} + 6y_n = 5^n$ connected with the condition $y_0 = 0, y_1 = 2$.

(a) Prove that every finite subset of a lattice has an LUB and a GLB.

(b) In a Lattice if $a \le b \le c$ then show that $(a \vee b) \vee (b \wedge c) = (a \vee b) \wedge (a \vee c) = b$.

(a) State and prove Lagrange's theorem for group. Is the converse true?

(b) Let $G$ be the set of all non-zero real numbers and let $a * b = ab/2$. Show that $(G, *)$ is an abelian group.

(a) Prove that a simple graph with $n$ vertices and $k$ components can have at most $\frac{(n-k)(n-k+1)}{2}$ edges.

(b) Prove that a connected graph $G$ is an Euler graph if and only if every vertex in $G$ is of even degree.

(a) Let $(A, \le)$ be a partially ordered set. Let $\le$ be a binary relation on $A$ such that for $a$ and $b$ in $A$, $a$ is related to $b$ iff $b \le a$. Show that $\le$ is a partially ordered relation.

(b) Show that $((p \vee q) \wedge \sim(\sim p \wedge (\sim q \vee \sim r))) \vee (\sim p \wedge q) \vee (\sim p \vee r)$ is a tautology without using the truth table.

(a) If $f : A \rightarrow B, g : B \rightarrow C$ are invertible functions, then show that $g \circ f : A \rightarrow C$ is invertible and $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$.

(b) Determine whether the following function is a bijection from $\mathbb{R}$ to $\mathbb{R}$:
$f(x) = \frac{x^2 + 1}{x^2 + 2}$

(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

(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

Write short notes on any two of the following:

(a) Euler Graph and Hamiltonian Graph

(b) Homomorphism and Isomorphism Graph

(c) Planar and Complete Bipartite Graph

(d) Adjacency matrix of a graph