Discrete Mathematics and Engineering Mathematics
This domain supplies roughly 5–7 questions and mixes pure discrete mathematics (logic, sets, relations, combinatorics, graph theory, algebraic structures) with the engineering mathematics GATE expects: linear algebra, calculus and probability. Questions are short but exacting - one wrong quantifier or one forgotten case loses the mark.
Core rules
- Negation swaps quantifiers: ¬∀x P(x) ≡ ∃x ¬P(x).
- Counting: product rule, sum rule, and inclusion–exclusion |A∪B∪C| = Σ|A| − Σ|A∩B| + |A∩B∩C|.
- Handshaking lemma: Σdeg(v) = 2|E|, so the number of odd-degree vertices is even. A connected graph has an Euler circuit iff every degree is even; an Euler path iff exactly zero or two vertices have odd degree.
- A tree on n vertices has n−1 edges and a unique path between any pair.
- In a finite group, the order of any element divides |G| (Lagrange).
- Eigenvalues from det(A − λI) = 0; their sum equals the trace and their product equals the determinant.
Worked example
Number of onto (surjective) functions from a 4-element set to a 3-element set. Total functions = 3⁴ = 81. Subtract those missing at least one image: C(3,1)·2⁴ = 48. Add back the doubly-subtracted cases: C(3,2)·1⁴ = 3. Result = 81 − 48 + 3 = 36. Note the same question asked as "number of ways to partition 4 distinct items into 3 non-empty labelled boxes" gives the same 36.
Traps that cost marks
- Confusing one-one, onto and bijection - for equal finite sets they differ from each other unless the sizes match.
- Forgetting that a probability question asking "given that" requires conditional (Bayes) reasoning.
- Applying the master theorem to recurrences that are not of the required polynomial form.