Back to Study Material GATE Exam

Last Minute Notes Discrete Mathematics

This rapid-revision block consolidates the most GATE-testable facts in Discrete Mathematics. Read each point, close your eyes, and recall it before moving ...

Last Minute Notes Discrete Mathematics

Quick Revision: Sets, Relations, Functions, and Counting

This rapid-revision block consolidates the most GATE-testable facts in Discrete Mathematics. Read each point, close your eyes, and recall it before moving forward.

Set operations: A union B contains all elements in A or B. A intersect B contains elements in both. A minus B contains elements in A but not B. Complement of A contains elements not in A. De Morgan's: complement of (A union B) = complement-A intersect complement-B. Complement of (A intersect B) = complement-A union complement-B.

Power set: if |A| = n then |P(A)| = 2 to the n. Cartesian product: |A times B| = |A| times |B|.

Relation properties checklist: reflexive means (a,a) in R for all a. Symmetric means if (a,b) in R then (b,a) in R. Antisymmetric means (a,b) in R and (b,a) in R implies a=b. Transitive means (a,b) and (b,c) in R implies (a,c) in R.

Equivalence relation = reflexive + symmetric + transitive. Partial order = reflexive + antisymmetric + transitive. Total order = partial order where every pair is comparable.

Function types: injective means f(a)=f(b) implies a=b. Surjective means every element in codomain is mapped to. Bijective means both. Number of functions from |A|=m to |B|=n is n to the m. Number of injections is n!/(n-m)! if n >= m. Number of bijections is n! if n=m. Number of surjections requires inclusion-exclusion.

Pigeonhole principle: if n+1 pigeons occupy n holes, at least one hole has 2 pigeons. Generalized: if kn+1 items are placed in n containers, some container has at least k+1 items.

Counting: C(n,r) = n! / (r! (n-r)!). Binomial expansion: (1+x)^n summed as C(n,k) x^k. Number of subsets of size r from n elements = C(n,r).

Inclusion-exclusion: |A union B| = |A| + |B| - |A intersect B|. Extend similarly for three or more sets. Sum of degrees of all vertices in a graph = 2 times number of edges. Number of odd-degree vertices is always even.

Propositional equivalences: p implies q = not-p OR q. p IFF q = (p implies q) AND (q implies p). Contrapositive of (p implies q) is (not-q implies not-p), logically equivalent. Double negation: not(not-p) = p.

Quick Revision: Graph Theory Key Facts and Theorems

Graph theory facts must be at your fingertips for GATE. This section compresses everything you need into a scannable format for last-minute review.

Definitions: simple graph has no self-loops or multiple edges. Complete graph K-n has n(n-1)/2 edges. Complete bipartite graph K-m,n has mn edges. A tree with n vertices has n-1 edges. A forest with n vertices and k components has n-k edges.

Degree sequence: sum of all degrees = 2|E|. Minimum degree denoted delta, maximum degree denoted Delta. A regular graph has all degrees equal. K-n is (n-1)-regular.

Connectivity: graph is connected if every pair of vertices has a path. A connected component is a maximal connected subgraph. Number of connected components = n minus rank of adjacency matrix over GF(2) (linear algebra connection).

Euler path exists if exactly 0 or 2 vertices have odd degree. Euler circuit (closed Euler path) exists if all vertices have even degree. Remember: Euler is about edges. Hamiltonian is about vertices — no simple characterization.

Planar graphs: Euler formula V - E + F = 2 for connected planar graph. For simple planar graphs E is at most 3V - 6 (triangulation bound). For bipartite planar graphs E is at most 2V - 4. Use these inequalities to prove non-planarity without computing.

Coloring: chromatic number of a graph is the minimum number of colors for proper vertex coloring (adjacent vertices get different colors). K-n needs n colors. Bipartite graphs are 2-colorable (chromatic number 2) if and only if they have no odd cycles. Planar graphs need at most 4 colors (four color theorem, not required to prove for GATE).

Spanning trees: a connected graph with n vertices has at least one spanning tree with n-1 edges. Number of spanning trees of K-n = n to the power n-2 (Cayley's formula). For K-3 this gives 3 spanning trees; for K-4 this gives 16.

BFS and DFS on graphs: BFS gives shortest path in unweighted graphs. DFS classifies edges into tree, back, forward, and cross edges. A graph has a cycle if DFS finds a back edge.

Matrix representations: adjacency matrix A has A[i][j]=1 if edge exists. A^k gives the number of walks of length k between pairs. Incidence matrix has rows for vertices and columns for edges, with 1 if vertex is endpoint of edge.

Quick Revision: Logic, Recurrences, and Combinatorics Summary

This final rapid-revision block on Discrete Mathematics focuses on propositional logic, predicate logic, recurrence solving, and combinatorial formulas that GATE tests both directly and as tools in other problems.

Propositional logic truth table essentials: conjunction (AND) is true only when both operands are true. Disjunction (OR) is false only when both are false. Implication (p implies q) is false only when p is true and q is false — equivalently, not-p OR q. Biconditional (p IFF q) is true when both have the same truth value. XOR is true when they differ.

Tautology: a formula true for all truth assignments. Contradiction: always false. Satisfiable: true for at least one assignment. To check tautology, check if the negation is unsatisfiable (useful in resolution proofs).

Predicate logic: universal quantifier "for all x P(x)" — false if even one counterexample exists. Existential "there exists x P(x)" — true if at least one element satisfies P. Negation: not(for all x P(x)) = there exists x not-P(x). Not(there exists x P(x)) = for all x not-P(x).

Recurrence solutions quick list: T(n) = T(n-1) + c gives T(n) = O(n). T(n) = 2T(n-1) + c gives T(n) = O(2^n). T(n) = T(n/2) + c gives T(n) = O(log n). T(n) = 2T(n/2) + c gives T(n) = O(n). T(n) = 2T(n/2) + n gives T(n) = O(n log n) (Merge Sort). T(n) = 4T(n/2) + n gives T(n) = O(n^2) (Master Theorem case 1).

Master theorem cases: let a>=1, b>1, f(n) given. Compare f(n) to n^(log_b a). Case 1: if f(n) = O(n^(log_b a - epsilon)), then T(n) = Theta(n^(log_b a)). Case 2: if f(n) = Theta(n^(log_b a) log^k n), then T(n) = Theta(n^(log_b a) log^(k+1) n). Case 3: if f(n) = Omega(n^(log_b a + epsilon)) and regularity condition holds, T(n) = Theta(f(n)).

Combinatorics quick formulas: arrangements of n distinct objects = n!. Arrangements with repetition of n objects with duplicates n1, n2, ... = n! / (n1! n2! ...). Stars and bars: number of non-negative integer solutions to x1+x2+...+xk=n is C(n+k-1, k-1). Derangements: number of permutations with no fixed point = n! times sum from k=2 to n of ((-1)^k / k!), approximately n!/e.