IT-302 Discrete structure - Dec 2025 Question Paper

Under each question, How to answer lists the points an answer should cover, outlined by CampusPrep from the syllabus. Check the details against your textbook.

1. 7 Marks
   aFind the number between 1 to 500 that are not divisible by any of the integers 2 or 3 or 7.
   How to answer

   • State inclusion-exclusion principle for three sets
   • Count numbers divisible by 2, 3, 7 and pairwise / triple intersections up to 500
   • Subtract from 500 to get numbers divisible by none
   • Compute final value
2. 7 Marks
   bProve that $5^{2n}-1$ is divisible by 24, where n is any positive integer.
   How to answer

   • State principle of mathematical induction
   • Verify base case for n=1
   • Assume true for n=k and prove for n=k+1 using $5^{2(k+1)}-1 = 25\cdot 5^{2k}-1$
   • Conclude divisible by 24
3. 7 Marks
   aWhat is mapping? Explain types of mapping.
   How to answer

   • Define mapping/function as relation with uniqueness
   • Give domain, codomain, image definition
   • Explain injective, surjective, bijective with examples
   • Mention one-one, onto, one-one onto, many-one diagrams
4. 7 Marks
   bDefine relation with example. Explain various types of representation of relation.
   How to answer

   • Define relation as subset of Cartesian product with example
   • Describe roster, matrix, digraph, arrow representations
   • Give example for each representation
   • Mention domain, range
5. 7 Marks
   aProve that $G = \{0, 1, 2, 3, 4, 5, 6\}$ is an abelian group of order 7 with respect to addition modulo 7.
   How to answer

   • Define group and abelian group axioms
   • Show closure, associativity, identity, inverse under addition modulo 7
   • Show commutativity
   • Conclude order is 7
6. 7 Marks
   bWhat is a Ring? Define elementary properties of ring with example
   How to answer

   • Define ring with two binary operations and axioms
   • List elementary properties: $a+0=a$, $a+(-a)=0$, $a0=0$ etc.
   • Prove/illustrate properties briefly
   • Give example e.g. integers, modulo ring
7. 7 Marks
   aConstruct truth table of the following and prove:

   1. a)$(p \leftrightarrow p \land r) \rightarrow (\sim r \rightarrow \sim p)$ is a tautology
   2. b)$(p \land q) \land (\sim p) \land (\sim q)$ is a contradiction.
   How to answer

   • Construct truth tables for $p,q,r$ with $2^2$ and $2^3$ rows
   • Evaluate $(p \leftrightarrow p \land r) \rightarrow (\sim r \rightarrow \sim p)$ to show all true
   • Evaluate $(p \land q) \land (\sim p) \land (\sim q)$ to show all false
   • Conclude tautology and contradiction
8. 7 Marks
   bDefine and explain any four of the following with suitable example.

   1. i)Bipartite graph
   2. ii)Hamiltonian path and circuit
   3. iii)Chromatic number and graph coloring of graph
   4. iv)Adjacency matrix of graph
   5. v)Binary search tree
   How to answer

   • Define each term with formal definition
   • Give suitable example with diagram where needed
   • Explain significance e.g. coloring, adjacency matrix
   • Cover any four items completely
9. 7 Marks
   aProve that $F=\{a + b * \sqrt{2} : a, b \text{ rational}\}$ is a field.
   How to answer

   • Show closure under addition and multiplication
   • Verify field axioms: associativity, identity, inverses
   • Show multiplicative inverse of $a+b\sqrt{2}$ exists for rationals
   • Conclude $F$ is a field
10. 7 Marks
    bProve or disprove that intersection of two normal subgroups of a group $G$ is again a normal subgroup of $G$. Define subgroup, normal subgroup, Quotient group, with an example for each.
    How to answer

    • Define subgroup, normal subgroup, quotient group with examples
    • Take $H,K$ normal in $G$ and $x \in H \cap K$
    • Show $g x g^{-1} \in H \cap K$ for all $g \in G$
    • Conclude intersection is normal
11. 7 Marks
    aExplain the following

    1. i)Euler Graph
    2. ii)Isomorphic Graphs
    3. iii)Minimal spanning tree
    4. iv)Height of the tree
    How to answer

    • Define Euler graph with even-degree condition and example
    • Define isomorphic graphs with bijection preserving adjacency
    • Define minimal spanning tree with weight minimality
    • Define height of tree as longest root-leaf distance
12. 7 Marks
    bDefine planner Graph. Prove that for any connected planner graph, $v-e+r=2$ where $v,e,r$ is the number of vertices, edges, and region of the graph respectively.
    How to answer

    • Define planar graph with embedding without edge crossing
    • State Euler's formula $v-e+r=2$
    • Prove by induction on number of edges/vertices
    • Illustrate with example
13. 7 Marks
    aSolve the following recurrence relation : $$a_r- 7a_{r-1}+10a_{r-2}=3^r \text{ Given that } a_0=0,a_1=1.$$
    How to answer

    • Form homogeneous part and characteristic equation $r^2-7r+10=0$
    • Find complementary solution with roots 2 and 5
    • Find particular solution for $3^r$ term
    • Apply $a_0=0, a_1=1$ to get constants
14. 7 Marks
    bSolve the following recurrence relation using generating function $$G(K)-7G(K-1)+10G(K-2)=8K+6$$
    How to answer

    • Define generating function $G(x)=\sum G(K)x^K$
    • Multiply recurrence and sum to get algebraic equation for $G(x)$
    • Solve for $G(x)$ and expand by partial fractions
    • Extract coefficient $G(K)$
15. 7 Marks
    aDiscuss in brief any two of the following:

    1. i)Partial ordering relation
    2. ii)Poset
    3. iii)Disjunctive normal form
    4. iv)Pigeonhole principle
    How to answer

    • Define partial ordering with reflexive, antisymmetric, transitive
    • Define poset as set with partial order and example
    • Define disjunctive normal form / pigeonhole principle
    • Give examples for chosen two
16. 7 Marks
    bDefine the lattice. Let $(L, \le \lor, \land)$ be a lattice and $a,b,c,d \in L$ such that $a \le b$ and $c \le d$. Show that $a \lor c \le b \lor d$ and $a \land c \le b \land d$.
    How to answer

    • Define lattice $(L, \le, \lor, \land)$ with join and meet
    • Use $a \le b$ implies $a \lor c \le b \lor c$ property
    • Show $a \lor c$ is lower bound argument for $b \lor d$
    • Similarly show $a \land c \le b \land d$