What are common examiner traps in Discrete Mathematics?

Confusing '\ x (P(x) \ Q(x))' with '\ x P(x) \ \ x Q(x)' (universal quantifier does NOT distribute over disjunction). Forgetting that the empty relation is vacuously symmetric and transitive, but NOT reflexive on a non-empty set. Neglecting the empty matching when counting total matchings of a graph. Assuming every group of composite order is cyclic (e.g., order 6 can be S3 which is non-cyclic and non-abelian). Confusing A \ B element assignment choices (3n) with independent subset pairs (4n). Overlooking the requirement of unique greatest lower bounds and unique least upper bounds when testing whether a poset is a lattice.

Discrete Mathematics

50 Qs · since 2011 · 71 marks · 2.7 marks/paperHigh yield

Take topic test

In GATE Computer Science, Discrete Mathematics is heavily tested across mathematical logic, set theory, relations & partial orders/lattices, group theory, combinatorics, and graph… Guide

Type

Topic guide

What does GATE test in Discrete Mathematics?

In GATE Computer Science, Discrete Mathematics is heavily tested across mathematical logic, set theory, relations & partial orders/lattices, group theory, combinatorics, and graph theory. Questions evaluate formal reasoning, counterexample construction, and structural counting principles. Over recent years, question formats have transitioned from standard single-choice definitions to multi-select properties (MSQs) and exact integer/combinatorial numerical answers (NATs).

Core concepts

Propositional Logic, truth tables, tautologies, contradictions, and sound inference rules
First-Order Logic (FOL), quantifiers ( , ), and negation distribution
Set identities, power sets, Cartesian products, and symmetric differences
Binary relations: reflexivity, symmetry, transitivity, antisymmetry, and circularity
Partial Orders, Hasse diagrams, lattices, meets/joins, and linear extensions / topological sorts
Function properties: injectivity, surjectivity, bijectivity, and composition properties
Group theory basics: order of elements, cyclic groups, subgroups, self-inverse elements, and direct products
Graph theory fundamentals: Handshaking Lemma, bipartite graphs, trees, planarity, chromatic numbers, matchings, vertex covers, and diameter

Recurring question patterns

Graph Invariants and Degree-Sum Counting
common · mixed · 1 marks · 2022, 2018, 2017, 2016
Problems leveraging the Handshaking Lemma ( $\sum \text{deg}(v) = 2|E|$ ), counting bounds on planar graphs, bipartite graph edge maximization, or tree edge-degree equations to deduce vertex degrees, component counts, or chromatic numbers.
Predicate Logic Equivalences and English-to-Logic Translation
common · MCQ · 1 marks · 2025, 2017, 2016, 2015
Translating natural language statements containing quantifiers ( $\forall, \exists$ ) and implications into First-Order Logic (FOL), or determining valid entailments and equivalences using quantifier negation rules.
Binary Relations, Equivalence Classes, and Posets/Lattices
common · mixed · 2 marks · 2026, 2025, 2024, 2023
Analyzing binary relation properties (reflexive, symmetric, transitive, antisymmetric, circular), counting relations/linear extensions, or verifying whether a given poset satisfies lattice properties (existence of unique GLB/meet and LUB/join).
Group Theory Structures and Subgroups
occasional · mixed · 1.5 marks · 2024, 2021, 2020, 2019
Testing properties of groups, subgroup orders using Lagrange's theorem, cyclic group properties of prime order, and counting self-inverse elements in direct products of cyclic groups.
Combinatorial and Recursive Counting
common · NAT · 1.5 marks · 2026, 2024, 2022, 2021
Counting subsets satisfying constraints, integer partitions (identical items into identical bins), topological sorts/linear extensions, or finding matchings via recurrence relations (e.g., Fibonacci-like sequences on paths).

Formulas GATE uses

Handshaking Lemma

\sum_{v \in V} \text{deg}(v) = 2|E|

Relating vertex degrees to the total number of edges in an undirected graph.

Fermat's Little Theorem

a^{p-1} \equiv 1 \pmod p \quad (\text{where } p \text{ is prime and } \gcd(a, p) = 1)

Computing large exponent modular reductions.

Number of Reflexive Relations

2^{n(n-1)} = 2^{n^2 - n}

Counting binary relations on an $n$ -element set that contain all diagonal pairs $(x, x)$ .

Lagrange's Subgroup Theorem

|H| \text{ divides } |G|

Constraining possible subgroup sizes for any finite group $G$ .

Maximum Edges in a Bipartite Graph

\lfloor n/2 \rfloor \cdot \lceil n/2 \rceil = \left\lfloor \frac{n^2}{4} \right\rfloor

Finding the edge maximum for a bipartite graph on $n$ vertices.

Disconnected Graph Maximum Edges

\binom{n-1}{2} = \frac{(n-1)(n-2)}{2}

Maximizing edges in a disconnected simple graph on $n$ vertices.

Number of Matchings in a Path Graph

M(n) = M(n-1) + M(n-2) = F_{n+1}

Recursive counting of valid matchings (including the empty matching) in a path $P_n$ .

Examiner traps in Discrete Mathematics

Confusing '\ x (P(x) \ Q(x))' with '\ x P(x) \ \ x Q(x)' (universal quantifier does NOT distribute over disjunction).
Forgetting that the empty relation is vacuously symmetric and transitive, but NOT reflexive on a non-empty set.
Neglecting the empty matching when counting total matchings of a graph.
Assuming every group of composite order is cyclic (e.g., order 6 can be S3 which is non-cyclic and non-abelian).
Confusing A \ B element assignment choices (3n) with independent subset pairs (4n).
Overlooking the requirement of unique greatest lower bounds and unique least upper bounds when testing whether a poset is a lattice.

How questions are asked

Logical equivalence / translation identification (MCQ)
Hasse diagram / poset property evaluation and pair counting (NAT / MSQ)
Graph property & invariant calculation using degree sum / planarity / connectivity (NAT / MCQ)
Linear extensions / topological sort counting for given posets (NAT)
Group subgroup order / self-inverse element counting (NAT / MCQ)
Relational property multi-statement checks (MSQ)

Paper trends

Shift from standard single-choice logical translations and definition-checking MCQs to combinatorial and structural NATs (e.g., linear extensions, subset pair counting, modular arithmetic).
2026, 2024, 2022, 2021, 2020, 2017, 2016, 2014
Introduction of MSQ items requiring multi-angle verification of algebraic and relation structures (e.g., circular relations, function-induced equivalence relations, function posets/lattices, vertex cover constraints).
2026, 2025, 2023, 2021
Deepening integration of linear algebra/matrices with graph structures (e.g., matrix power walks, adjacency matrix self-inverses determining 1-regular/matching graphs).
2026, 2024, 2021

Difficulty notes

Easy: Direct application of single formulas (Lagrange's theorem, Handshaking Lemma, Fermat's Little theorem, direct logical truth table checks). Medium: Multi-step reasoning involving counterexample elimination (validity of FOL statements, transitivity counterexamples, linear extensions counting, non-distributive lattice analysis). Hard: Abstract poset relations over sets, intricate structural proofs on graph covers/matchings requiring combinatorics or invariant derivations.