Discrete Mathematics – GATE CS Premium Module

Discrete Mathematics forms the backbone of Computer Science. In GATE CS, it contributes 2–3 marks, and questions usually target combinatorics, graph theory basics, and logical reasoning.

This chapter is extremely scoring because questions are direct, formula-based, and less time-consuming.

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 ext{ or } x in B}

]

Intersection

[

A cap B = {x mid x in A ext{ and } x in B}

]

Difference

[

A - B = {x in A mid x

otin 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 give guaranteed 1–2 marks because formulas are straightforward.

2.1 Permutations (Order Matters)

Arrangements where order is important.

[

P(n,r) = rac{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) = inom{n}{r} = rac{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:

[

]

Three sets:

[

]

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 o v).

Complete Graph (K_n)

Every pair of vertices is connected.

Number of edges:

[

|E| = rac{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 (( o)) – 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 o 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) = rac{9!}{(9-4)!} = rac{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 o B) land A)

Rewrite implication:

[

A o 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:

[

oxed{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

[