GATE CS - ENGINEERING MATHEMATICS:Discrete Mathematics

Mastering discrete mathematics concepts and implementation.

Discrete Mathematics for GATE CS

Discrete Math usually contributes about 2–3 marks (sometimes more when counted with “math-shaped” CS questions). Expect combinatorics ( $P$ , $C$ ), basic graph counting (handshaking, trees), and propositional logic. Formulas first; then one careful count.

1. Set Theory (Foundation for Logic & CS Theory)

A set is a well-defined collection of elements.

Notation:

$A = \{1, 2, 3\}$
$x \in A$ → x is in A
$|A|$ → cardinality (number of elements)

1.1 Set Operations

Union

A \cup B = \{x \mid x \in A \text{ or } x \in B\}

Intersection

A \cap B = \{x \mid x \in A \text{ and } x \in B\}

Difference

A - B = \{x \in A \mid x \notin B\}

Complement

If $U$ is the universal set:

A' = U - A

1.2 Important Set Properties (Frequently Asked)

Commutative

$A \cup B = B \cup A$
$A \cap B = B \cap A$

Associative

$(A \cup B) \cup C = A \cup (B \cup C)$
$(A \cap B) \cap C = A \cap (B \cap C)$

Distributive

$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$
$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$

De Morgan’s Laws

(A \cup B)' = A' \cap B'

(A \cap B)' = A' \cup B'

GATE Tip:

Expect MCQs involving Venn diagrams, complements, or inclusion–exclusion.

2. Combinatorics (Most Tested Area)

Combinatorics questions are usually straightforward once the counting setup is clear.

2.1 Permutations (Order Matters)

Arrangements where order is important.

P(n,r) = \frac{n!}{(n-r)!}

Example: Ways to arrange 5 distinct books = $5! = 120$ .

2.2 Combinations (Order Doesn’t Matter)

Selections where order is not important.

C(n,r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}

Example: Ways to choose 3 students from 10:

C(10,3) = 120

2.3 Pigeonhole Principle

If $n+1$ objects are placed in $n$ boxes, at least one box contains $\ge 2$ objects.

Generalised:

If $kn + 1$ objects are placed in $n$ boxes, at least one box contains $\ge k+1$ objects.

GATE Usage:

Algorithm analysis (collisions)
Existence proofs
Graph theory degree bounds

2.4 Inclusion–Exclusion Principle

Two sets:

|A \cup B| = |A| + |B| - |A \cap B|

Three sets:

|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|

GATE often hides this inside counting problems.

3. Graph Theory (Very Common in GATE)

A graph $G = (V, E)$ consists of:

$V$ : set of vertices
$E$ : set of edges

3.1 Types of Graphs

Undirected Graph – edges have no direction.

Directed Graph (Digraph) – edges are arrows $u \to v$ .

Complete Graph $K_n$

Every pair of vertices is connected.

Number of edges:

|E| = \frac{n(n-1)}{2}

Tree

Connected, acyclic graph
For $n$ vertices: $|E| = n - 1$
Extremely important in GATE.

3.2 Key Graph Properties

Degree

Number of edges incident on a vertex.

Handshaking Lemma

\sum \deg(v) = 2|E|

This is very common in GATE.

Path – sequence of vertices with connecting edges.

Cycle – path where first and last vertices are same.

Connected graph – path exists between every pair of vertices.

4. Propositional Logic (Constant 1‑Mark Area)

Logic is core to algorithms, proofs, and Boolean algebra.

4.1 Logical Operators

AND ($\land$) – true if both operands are true
OR ($\lor$) – true if at least one is true
NOT ($\lnot$) – negation
Implication ($\to$) – false only when A = true, B = false
Biconditional ($\leftrightarrow$) – true when both have same truth value

4.2 Logical Equivalences (Must Know for GATE)

Idempotent

$A \lor A = A$
$A \land A = A$

Absorption

$A \lor (A \land B) = A$
$A \land (A \lor B) = A$

De Morgan

$\lnot(A \lor B) = \lnot A \land \lnot B$
$\lnot(A \land B) = \lnot A \lor \lnot B$

Implication

A \to B \equiv \lnot A \lor B

These help simplify formulas and solve truth-table questions quickly.

5. GATE PYQ‑Style Solved Questions

Q1. Combinatorics (PYQ)

How many 4‑digit numbers can be formed using digits 1–9 without repetition?

P(9,4) = \frac{9!}{(9-4)!} = \frac{9!}{5!} = 9 \cdot 8 \cdot 7 \cdot 6 = 3024

Q2. Pigeonhole Principle (PYQ)

In a group of 13 people, prove that at least 2 people have the same birth month.

12 months, 13 people → by pigeonhole principle, at least one month has ≥2 people.

Q3. Handshaking Lemma (PYQ)

A graph has 6 vertices and each vertex has degree 3. Find number of edges.

\sum \deg(v) = 6 \cdot 3 = 18 = 2|E| \Rightarrow |E| = 9

Q4. Logic Simplification (PYQ)

Simplify: $(A \to B) \land A$

Rewrite implication:

A \to B \equiv \lnot A \lor B

So:

(\lnot A \lor B) \land A = (A \land \lnot A) \lor (A \land B)

First term is false, so:

\boxed{A \land B}

6. Common Mistakes to Avoid

Confusing permutations with combinations
Forgetting subtraction term in inclusion–exclusion
Assuming all graphs are connected by default
Mixing up the implication truth table
Miscalculating in‑degree/out‑degree in directed graphs
Ignoring factorial growth when estimating counts

Avoiding these mistakes prevents losses in direct formula-based questions.

7. Fast Revision Sheet (Night Before Exam)

Permutations

P(n,r) = \frac{n!}{(n-r)!}

Combinations

C(n,r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}

Complete Graph

Edges = $\dfrac{n(n-1)}{2}$