Discrete Mathematics Previous Year Questions
Discrete Mathematics PYQs in GATE CS can be grouped into clear families. Mastering these patterns and practicing the associated reasoning techniques direct...
PYQ Patterns: Relations, Functions, and Counting Problems
Discrete Mathematics PYQs in GATE CS can be grouped into clear families. Mastering these patterns and practicing the associated reasoning techniques directly improves your score without requiring new theory.
Relation property identification is one of the most consistent question types. A typical GATE question defines a relation through a rule like "R on integers where (a,b) in R if and only if a minus b is divisible by 3" and asks which properties hold. Divisibility by 3 is reflexive (a-a=0 is divisible by 3), symmetric (if 3 divides a-b then 3 divides b-a), and transitive (if 3 divides a-b and 3 divides b-c then 3 divides a-c). This makes R an equivalence relation with three equivalence classes: residue 0, residue 1, and residue 2.
Counting function questions appear regularly. A common format: "How many surjections exist from a set of 4 elements to a set of 3 elements?" Apply inclusion-exclusion. Total functions = 3^4 = 81. Subtract functions missing at least one range element. Functions missing element 1 = 2^4 = 16, similarly for elements 2 and 3. Add back functions missing two elements: 1^4 = 1 each, three such pairs. Subtract functions missing all three: 0. Surjections = 81 - 3(16) + 3(1) - 0 = 81 - 48 + 3 = 36.
Pigeonhole applications in GATE often require identifying what the pigeons and holes are. A classic GATE-style question: "From integers 1 to 10, how many must you choose to guarantee two sum to 11?" Pair them as (1,10), (2,9), (3,8), (4,7), (5,6) — five pairs. By pigeonhole, choosing 6 numbers guarantees at least one complete pair. The answer is 6.
Partial order and Hasse diagram questions ask you to draw or interpret Hasse diagrams of posets. A typical question presents the divisibility relation on a set like {1, 2, 3, 6, 12, 24} and asks for the number of elements covering a specific element, or asks to identify the least upper bound (join) and greatest lower bound (meet) of two elements. These are direct applications of lattice theory.
Generating functions and recurrence questions have increased in recent GATE papers. A question might give a recurrence like a(n) = 3a(n-1) - 2a(n-2) with initial conditions a(0)=1, a(1)=2 and ask for a closed form or the value at a(5). Solve by finding the characteristic equation r^2 - 3r + 2 = 0 with roots r=1 and r=2. General solution: a(n) = A(1)^n + B(2)^n. Using initial conditions: A+B=1 and A+2B=2 gives B=1, A=0. So a(n) = 2^n.
PYQ Patterns: Graph Theory Problems and Solution Strategies
Graph theory PYQs in GATE are among the most analytically diverse questions in Discrete Mathematics. They reward students who can translate verbal descriptions into graph structures and apply standard theorems efficiently.
Degree sequence questions are among the simplest graph PYQs but require vigilance. GATE presents a sequence and asks whether it is graphical (realizable as a graph). Apply the Erdos-Gallai theorem, or use the simpler procedure: sort in non-increasing order, then for each prefix of length k, verify that the sum of the first k degrees is at most k(k-1) plus the sum of min(d_i, k) for the remaining degrees. For small sequences like (3,3,3,3), verify the sum is 12 (even), then check realizability — this sequence corresponds to K4 with degrees all 3.
Spanning tree counting questions may give a small graph and ask for the number of spanning trees. For K3 (complete graph on 3 vertices), Cayley's formula gives 3^(3-2) = 3. For K4, it gives 4^2 = 16. For other graphs, use Kirchhoff's matrix tree theorem: the number of spanning trees equals any cofactor of the Laplacian matrix L = D - A, where D is the degree matrix and A is the adjacency matrix. For a small cycle C4 with 4 vertices, the answer is 4.
Planarity questions frequently ask whether a given graph is planar and why. If V=6, E=12, check if E <= 3V-6 = 12. Since E equals the bound, planarity is not ruled out, and further checking is needed. If E > 3V-6, the graph is definitely not planar. GATE also asks whether a graph contains K5 or K3,3 as a minor or subdivision, using Kuratowski's theorem as the reasoning tool.
Graph coloring questions in GATE often provide a graph and ask for its chromatic number or chromatic polynomial. Bipartite graphs always have chromatic number 2 (if non-empty). Odd cycles have chromatic number 3. For small graphs, determine the chromatic number by trying to color with the minimum number of colors. A question on the Petersen graph (chromatic number 3) has appeared in competitive exam contexts.
Connectivity-related PYQs ask for the minimum number of vertices or edges whose removal disconnects the graph. This is the vertex connectivity (kappa) and edge connectivity (lambda). Whitney's inequality states kappa <= lambda <= delta, where delta is the minimum degree. For K-n, all three values equal n-1. GATE uses this inequality to bound connectivity values from degree information alone.
PYQ Patterns: Logic and Predicate Calculus Questions
Logic questions in GATE Discrete Mathematics test both computational ability (evaluating truth values) and structural understanding (identifying tautologies, contradictions, and valid arguments). This section covers the dominant logic PYQ patterns and efficient resolution strategies.
Tautology identification questions give a propositional formula and ask whether it is a tautology. The fastest approach for formulas with 2-3 variables is truth table evaluation. For more complex formulas, try to find a falsifying assignment first — if the formula can be false, it is not a tautology. For example, "(p implies q) AND (q implies p) IFF (p IFF q)" — the left side is p IFF q by definition, so this becomes (p IFF q) IFF (p IFF q), which is always true, hence a tautology.
Logical equivalence questions present two formulas and ask if they are equivalent. Efficient method: check one or two input combinations where the formulas might differ. If they always agree, they are equivalent. For example, "p implies (q implies r)" and "(p AND q) implies r" — substitute p=T, q=T, r=F: left gives T implies (T implies F) = T implies F = F; right gives (T AND T) implies F = T implies F = F. Same so far. Check another: p=F, q=T, r=F: left gives F implies (T implies F) = F implies F = T; right gives (F AND T) implies F = F implies F = T. These are equivalent — the law of exportation.
Predicate logic questions ask you to formalize or evaluate statements. A GATE-style question: "Express 'Every student who passes all exams will graduate' in predicate logic." Let S(x) = x is a student, P(x,e) = x passes exam e, E(e) = e is an exam, G(x) = x graduates. Formalization: for all x (S(x) AND (for all e (E(e) implies P(x,e))) implies G(x)). GATE tests whether you can correctly scope quantifiers.
Argument validity questions check whether a conclusion follows from given premises. Method: assume the conclusion is false and check if the premises can all be true simultaneously. If yes, the argument is invalid (premises do not entail conclusion). If no, the argument is valid (true premises force the conclusion). This proof-by-contradiction approach is faster than constructing a full proof.
Resolution proof questions give clauses (disjunctions of literals) and ask you to derive a specific conclusion or show unsatisfiability. Apply the resolution rule: from (A OR p) and (B OR not-p), derive (A OR B). Chain resolutions until you derive the empty clause (contradiction) or the desired conclusion. GATE questions on resolution typically involve 3-5 clauses and 2-3 resolution steps, making them tractable within exam time if you work systematically.