Back to Study Material GATE Exam

Discrete Mathematics

Discrete Mathematics is one of the highest-weighted topics in GATE CS, contributing 8 to 10 marks per year across multiple sections. Set theory provides th...

Discrete Mathematics

Set Theory, Relations, and Functions: Core Concepts for GATE

Discrete Mathematics is one of the highest-weighted topics in GATE CS, contributing 8 to 10 marks per year across multiple sections. Set theory provides the mathematical vocabulary used throughout computer science, and mastery here accelerates learning in algorithms, databases, and formal languages.

A set is a well-defined collection of distinct objects. Basic operations include union, intersection, difference, and complement, all governed by familiar algebraic laws. De Morgan's laws for sets state that the complement of the union of A and B equals the intersection of their complements, and the complement of the intersection equals the union of complements. The power set of a set with n elements has exactly 2 to the power n elements. The Cartesian product A times B has |A| times |B| ordered pairs.

Relations formalize connections between elements. A relation R on set A is a subset of A times A. Properties tested in GATE include reflexivity (every element is related to itself), symmetry (if A relates to B then B relates to A), antisymmetry (if A relates to B and B relates to A then A equals B), and transitivity (if A relates to B and B relates to C then A relates to C). An equivalence relation is reflexive, symmetric, and transitive, and it partitions the set into equivalence classes. A partial order is reflexive, antisymmetric, and transitive.

Counting equivalence classes or determining which properties a given relation satisfies are standard GATE question formats. For example, the relation "divides" on positive integers is reflexive (a divides a), antisymmetric (if a divides b and b divides a then a equals b), and transitive, so it is a partial order but not an equivalence relation because it is not symmetric.

Functions map each element of a domain to exactly one element of a codomain. Injective (one-to-one) functions map distinct elements to distinct images. Surjective (onto) functions cover every element of the codomain. Bijective functions are both, enabling the construction of an inverse. GATE asks you to count the number of injections from a set of m elements to a set of n elements, which is n factorial divided by (n minus m) factorial, valid only when n is at least m.

Composition of functions is associative but generally not commutative. If f maps A to B and g maps B to C, then g composed with f maps A to C. The number of functions from an m-element set to an n-element set is n to the power m — a formula GATE uses in combinatorics questions.

Graph Theory: Traversals, Trees, and Graph Properties

Graph theory is arguably the most critical sub-topic within Discrete Mathematics for GATE CS because it bridges directly into algorithms (BFS, DFS, shortest paths) and data structures. GATE allocates substantial marks to graph-theoretic reasoning, and questions appear in both the Mathematics section and the Algorithms section.

A graph G consists of a vertex set V and an edge set E. Edges can be directed (digraph) or undirected. The degree of a vertex is the number of edges incident to it; in a directed graph, in-degree and out-degree are tracked separately. The handshaking lemma states that the sum of all vertex degrees equals twice the number of edges, implying the number of odd-degree vertices is always even. GATE directly tests this with questions like "A graph has 5 vertices with degrees 2, 3, 3, 3, and d. What must d be?" The sum must be even, so 2+3+3+3+d must be even, giving d=3.

Connectivity is central. An undirected graph is connected if there is a path between every pair of vertices. A strongly connected directed graph has a directed path between every ordered pair. Articulation points (cut vertices) are vertices whose removal disconnects the graph; bridges are edges whose removal disconnects it. GATE questions on these topics often require analyzing a given graph visually or through adjacency matrix reasoning.

Trees are connected acyclic undirected graphs. A tree with n vertices has exactly n minus 1 edges. A spanning tree of a connected graph is a subgraph that is a tree containing all vertices. The number of spanning trees of a complete graph K-n is n to the power n minus 2 by Cayley's formula — GATE has tested this for small values.

Euler paths and Hamiltonian paths differ critically. An Euler path traverses every edge exactly once; it exists if and only if the graph has exactly 0 or 2 vertices of odd degree. An Euler circuit exists if and only if all vertices have even degree. A Hamiltonian path visits every vertex exactly once; no simple necessary-and-sufficient condition exists, making these problems computationally hard in general.

Planarity: a graph is planar if it can be drawn in a plane without edge crossings. Euler's formula for connected planar graphs: V minus E plus F equals 2, where F is the number of faces including the outer face. K5 and K3,3 are the minimal non-planar graphs (Kuratowski's theorem). GATE tests planarity by asking students to verify Euler's formula or identify whether a given graph is planar.

Combinatorics, Logic, and Recurrences for GATE

Combinatorics, propositional logic, and recurrence relations together constitute a significant portion of GATE's Discrete Mathematics marks. These topics interweave with algorithms and theory of computation, making them doubly important.

Counting principles start with the rule of sum (if A and B are disjoint, total choices = |A| + |B|) and the rule of product (if choices are independent, total = |A| times |B|). Permutations count arrangements where order matters: P(n,r) = n factorial divided by (n minus r) factorial. Combinations count selections where order does not matter: C(n,r) = n factorial divided by (r factorial times (n minus r) factorial). The binomial theorem states that (x+y) raised to n equals the sum from k=0 to n of C(n,k) times x-to-the-k times y-to-the-(n-k).

Inclusion-exclusion principle computes the size of a union by alternating addition and subtraction of intersections: |A union B union C| = |A| + |B| + |C| minus |A intersect B| minus |A intersect C| minus |B intersect C| plus |A intersect B intersect C|. GATE uses this to count surjective functions (onto functions) — the number of surjections from n to m is computed using inclusion-exclusion over functions that miss at least one element of the codomain.

Propositional logic tests your ability to evaluate and manipulate logical statements. A proposition is either true or false. Connectives include AND (conjunction), OR (disjunction), NOT (negation), IMPLIES (implication), and IFF (biconditional). The implication p implies q is false only when p is true and q is false. Contrapositive (not-q implies not-p) is logically equivalent to the original, but converse (q implies p) and inverse (not-p implies not-q) are not.

Predicate logic extends propositional logic with quantifiers. The universal quantifier (for all) states that a predicate holds for every element; the existential quantifier (there exists) states it holds for at least one. Negating quantified statements: the negation of "for all x P(x)" is "there exists x such that not P(x)."

Recurrence relations define sequences in terms of previous values. The Fibonacci sequence satisfies F(n) = F(n-1) + F(n-2). The solution to the recurrence T(n) = T(n/2) + O(1) is T(n) = O(log n), which describes binary search. GATE solves recurrences using substitution, recurrence trees, or the Master Theorem: if T(n) = aT(n/b) + f(n), compare f(n) to n to the log base b of a to determine the dominant term. These appear in both Discrete Mathematics and Algorithm Analysis sections.