Discrete Mathematics Short Notes for GATE CS

GATE CS Discrete Mathematics: 7 chapters, 47 previous year questions (45% of Engineering Mathematics), 757 practice questions and one solved question from each chapter.

About Discrete Mathematics Short Notes

Quick revision sheets for Discrete Mathematics in GATE CS. Every chapter is condensed into key formulas, shortcuts and common traps so you can revise 7 chapters fast before the exam.

Discrete Mathematics Weightage in GATE CS

Discrete Mathematics accounts for 47 of 105 Engineering Mathematics previous year questions in our bank (45%), about 4.7 per paper across 10 papers.

Discrete Mathematics Chapter Matrix

Chapter	Topics	PYQs	Share of unit PYQs	Practice questions
Logic and Proof Techniques	Propositional Translation and Implication, Tautologies, Contradictions and Logical Equivalence, Predicate Logic and Quantifier Translation, Quantified Reasoning and Mathematical Induction	7	15%	109
Sets, Relations, Functions and Order Structures	Function Properties, Composition and Cardinality, Equivalence Relations and Quotient Mappings, Relation Properties and Equivalence Conditions, Partial Orders, Linear Extensions and Lattices	8	17%	133
Combinatorics and Counting	Stars and Bars and Integer Partitions, String Counting and Complementary Counting, Permutations, Assignments and Order Constraints, Subset and Binary Matrix Counting	7	15%	120
Recurrences and Generating Functions	Generating Functions for Sequences, Linear Recurrences and Characteristic Roots, Binary and Divide-and-Conquer Recurrences	3	6%	48
Algebraic Structures and Groups	Binary Operations and Algebraic Laws, Monoids of Functions under Pointwise Operations, Groups from Set Operations and Direct Products, Group Properties, Cyclicity and Subgroups	6	13%	94
Graph Fundamentals, Trees and Connectivity	Spanning Tree Enumeration and Comparison, Weighted Spanning Trees and Edge Parity, Connectivity, Edge Bounds and Planarity, Matchings, Distances and Graph Powers	8	17%	127
Graph Coloring, Covers, Matrices and Special Graphs	Graph Coloring and Bipartite Graphs, Adjacency Matrices and Walk or Cycle Counting, Minimum Vertex Covers and Degree Constraints, Petersen Graph, Hamiltonicity and Isomorphism	8	17%	126

One Solved Question from Each Discrete Mathematics Chapter

Question 1 · Logic and Proof Techniques MCQ

Consider the following logical rules for a server cluster:

The cluster is healthy ( $H$ ) if the CPU usage ( $U$ ) is below 80% and the network is stable ( $N$ ).
The cluster triggers an alarm ( $A$ ) unless it is healthy ( $H$ ) and the power is redundant ( $P$ ).
The power is redundant ( $P$ ) only if the network is not stable ( $\neg N$ ).

It is observed that the cluster is healthy ( $H$ is True), no alarm is triggered ( $A$ is False), and the CPU usage is below 80% ( $U$ is True).

Which one of the following is the CORRECT truth value of the network being stable ( $N$ )?

A.
False
B.
True
C.
Cannot be determined from the given information
D.
The given conditions are contradictory

Correct Answer:

Step-by-Step Solution

Key idea: This is a multi-step propositional translation question. The trap lies in correctly translating the keywords "if", "unless", and "only if" into their precise logical implications without reversing the arrows.

Step 1: Translate Rule 1. " $H$ if ( $U$ and $N$ )" means the condition ( $U \land N$ ) is sufficient for $H$ . Translation: $(U \land N) \to H$ .

Step 2: Translate Rule 2. " $A$ unless ( $H$ and $P$ )" means if ( $H$ and $P$ ) is false, then $A$ happens. Translation: $\neg (H \land P) \to A$ .

Step 3: Translate Rule 3. " $P$ only if $\neg N$ " means $P$ is sufficient for $\neg N$ , or $\neg N$ is necessary for $P$ . Translation: $P \to \neg N$ .

Step 4: Substitute the given truth values: $H = True$ , $A = False$ , $U = True$ .

Step 5: Evaluate Rule 2. Since $A$ is False, the antecedent $\neg (H \land P)$ must be False (to avoid a True $\to$ False scenario). Therefore, $H \land P$ must be True. Since $H$ is True, $P$ must be True.

Step 6: Evaluate Rule 3. Since $P$ is True, and $P \to \neg N$ , the consequent $\neg N$ must be True. Therefore, $N$ must be False.

Step 7: Verify Rule 1. $(U \land N) \to H$ becomes $(True \land False) \to True$ , which is $False \to True$ . This is a valid implication (vacuously true).

Answer: The truth value of $N$ is False. Option A.

Question 2 · Sets, Relations, Functions and Order Structures MCQ

Match the items in List I with the correct number of relations/structures in List II.

List I

P. The number of equivalence relations on ${1, 2, 3, 4}$ containing the pair $(1, 2)$ .

Q. The number of reflexive and transitive relations on ${1, 2, 3}$ containing $(1, 2)$ and $(2, 1)$ .

R. The number of partial orders on ${1, 2, 3}$ where $1$ and $2$ are incomparable.

S. The number of equivalence relations on ${1, 2, 3, 4, 5}$ with exactly $2$ equivalence classes.

List II

$15$
$7$
$4$
$5$

Select the correct matching from the options below:

A.
P-1, Q-2, R-3, S-4
B.
P-4, Q-2, R-3, S-1
C.
P-4, Q-3, R-2, S-1
D.
P-1, Q-3, R-2, S-4

Correct Answer:

Step-by-Step Solution

Key idea: This is a structural bounding question. We must count relations by translating the conditions into constraints on partitions (for equivalence relations) or preorders/partial orders.

Step 1: Evaluate P. An equivalence relation on ${1, 2, 3, 4}$ containing $(1, 2)$ means $1$ and $2$ must be in the same equivalence class. We can treat ${1, 2}$ as a single block. The problem reduces to finding the number of partitions of a 3-element set: ${{1, 2}, 3, 4}$ . The Bell number $B_{3} = 5$ . So, P = 5.

Step 2: Evaluate Q. A reflexive and transitive relation containing $(1, 2)$ and $(2, 1)$ means $1$ and $2$ are in the same strongly connected component. This is equivalent to a preorder on the set where $1$ and $2$ are identified as a single element. The quotient set is ${{1, 2}, 3}$ , which has 2 elements. The number of preorders on a 2-element set is equal to the number of partial orders on a 2-element set, which is 3 (incomparable, $X < Y$ , $Y < X$ ). Wait, a preorder can also have $X = Y$ . So there are 4 preorders: incomparable, $X < Y$ , $Y < X$ , and $X = Y$ . Thus, Q = 4.

Step 3: Evaluate R. We need the number of partial orders (posets) on ${1, 2, 3}$ where $1$ and $2$ are incomparable. The total number of posets on 3 elements is 19. The number of posets where $1$ and $2$ are comparable is 12 (6 chains + 6 other structures). Alternatively, we can directly list the Hasse diagrams where 1 and 2 are incomparable:

Antichain (1)
3 above 1, 2 isolated (1)
3 below 1, 2 isolated (1)
3 above 2, 1 isolated (1)
3 below 2, 1 isolated (1)
3 above both 1 and 2 (V-shape) (1)
3 below both 1 and 2 (inverted V) (1)

Total = 7. So, R = 7.

Step 4: Evaluate S. An equivalence relation on ${1, 2, 3, 4, 5}$ with exactly 2 classes corresponds to partitions of 5 into 2 parts. The possible sizes are $1 + 4$ and $2 + 3$ .

Number of $1 + 4$ partitions: $(1 5) = 5$ .
Number of $2 + 3$ partitions: $(2 5) = 10$ .

Total = $5 + 10 = 15$ . So, S = 15.

Step 5: Match the values.

P = 5 $⟹$ 4

Q = 4 $⟹$ 3

R = 7 $⟹$ 2

S = 15 $⟹$ 1

The correct matching is P-4, Q-3, R-2, S-1.

Answer: P-4, Q-3, R-2, S-1.

Question 3 · Combinatorics and Counting MCQ

Consider three scenarios involving the distribution of 6 identical apples into 3 distinct boxes:

Scenario A: Each box must contain an even number of apples (including 0).

Scenario B: Each box must contain a prime number of apples.

Scenario C: The number of apples in each box must be distinct.

Let $N_{A}, N_{B}, N_{C}$ be the number of valid distributions for Scenarios A, B, and C respectively.

Which of the following correctly ranks these quantities?

A.
$N_{A} < N_{B} < N_{C}$
B.
$N_{C} < N_{A} < N_{B}$
C.
$N_{B} < N_{C} < N_{A}$
D.
$N_{B} < N_{A} < N_{C}$

Correct Answer:

Step-by-Step Solution

Key idea: Translate each English constraint into a precise algebraic or combinatorial condition, then evaluate each scenario independently before ranking.

Step 1: Evaluate Scenario A. We need $x_{1} + x_{2} + x_{3} = 6$ with $x_{i} \in {0, 2, 4, 6}$ . Let $x_{i} = 2 y_{i}$ . The equation becomes $y_{1} + y_{2} + y_{3} = 3$ with $y_{i} \geq 0$ . By Stars and Bars, $N_{A} = (3 - 1 3 + 3 - 1) = (2 5) = 10$ .

Step 2: Evaluate Scenario B. We need $x_{1} + x_{2} + x_{3} = 6$ with $x_{i} \in {2, 3, 5}$ . The only combination of three primes that sums to 6 is $2 + 2 + 2$ . Since the boxes are distinct but all get the same amount, there is only $N_{B} = 1$ way.

Step 3: Evaluate Scenario C. We need $x_{1} + x_{2} + x_{3} = 6$ with $x_{i}$ all distinct. The possible sets of values are ${0, 1, 5}$ , ${0, 2, 4}$ , and ${1, 2, 3}$ . Since the boxes are distinct, each set can be assigned to the 3 boxes in $3! = 6$ ways. Thus, $N_{C} = 3 \times 6 = 18$ .

Step 4: Rank the results. We have $N_{B} = 1$ , $N_{A} = 10$ , and $N_{C} = 18$ . Therefore, $N_{B} < N_{A} < N_{C}$ .

Answer: D

Question 4 · Recurrences and Generating Functions MCQ

Consider the generating function $A (x) = \frac{x ^{2}}{( 1 - 2 x ) ^{3}}$ .

Assertion (A): The coefficient of $x^{n}$ in $A (x)$ is $a_{n} = n (n - 1) 2^{n - 3}$ for $n \geq 2$ , and $a_{0} = a_{1} = 0$ .

Reason (R): Since $\frac{1}{( 1 - 2 x ) ^{3}} = \sum_{n = 0}^{\infty} (2 n + 2) 2^{n} x^{n}$ , multiplying by $x^{2}$ gives $a_{n} = (2 n + 2) 2^{n - 2}$ for $n \geq 2$ .

A.
Both (A) and (R) are true, and (R) is the correct explanation of (A).
B.
Both (A) and (R) are true, but (R) is NOT the correct explanation of (A).
C.
(A) is true but (R) is false.
D.
(A) is false but (R) is true.

Correct Answer:

Step-by-Step Solution

Key idea: This is an assertion-reason question about coefficient extraction with index shifting. You need to verify both the assertion and the reason independently.

Step 1: Verify the assertion (A).

We know $\frac{1}{( 1 - 2 x ) ^{3}} = \sum_{n = 0}^{\infty} (2 n + 2) (2 x)^{n} = \sum_{n = 0}^{\infty} (2 n + 2) 2^{n} x^{n}$ .

Multiplying by $x^{2}$ : $A (x) = x^{2} \sum_{n = 0}^{\infty} (2 n + 2) 2^{n} x^{n} = \sum_{n = 0}^{\infty} (2 n + 2) 2^{n} x^{n + 2}$ .

Let $m = n + 2$ , so $n = m - 2$ . Then $A (x) = \sum_{m = 2}^{\infty} (2 m) 2^{m - 2} x^{m}$ .

So $a_{m} = (2 m) 2^{m - 2} = \frac{m ( m - 1 )}{2} 2^{m - 2} = m (m - 1) 2^{m - 3}$ for $m \geq 2$ .

And $a_{0} = a_{1} = 0$ since the sum starts at $m = 2$ .

Thus, assertion (A) is TRUE.

Step 2: Verify the reason (R).

The reason states that multiplying by $x^{2}$ gives $a_{n} = (2 n + 2) 2^{n - 2}$ .

But from Step 1, the correct formula is $a_{n} = (2 n) 2^{n - 2}$ , not $(2 n + 2) 2^{n - 2}$ .

The error is in not adjusting the binomial coefficient index after the shift.

Thus, reason (R) is FALSE.

Answer: (C) (A) is true but (R) is false.

Question 5 · Algebraic Structures and Groups MCQ

Let $*$ be a binary operation on $Z$ defined by $a * b = a + b - ab$ . For $a, b \in {- 3, - 2, - 1, 0, 1, 2}$ , find the maximum possible value of $(a * b) * 2$ subject to the condition that $a * b \geq - 5$ .

A.
7
B.
9
C.
-3
D.
5

Correct Answer:

Step-by-Step Solution

Key idea: This is an optimization problem disguised as a custom operator. The algebraic structure of $a * b = a + b - ab$ can be factored as $1 - (1 - a) (1 - b)$ . This observation transforms a complex search into a simple product maximization.

Step 1: Simplify the inner operation.

$a * b = a + b - ab = 1 - (1 - a + 1 - b - 1 + ab) = 1 - (1 - a) (1 - b)$ .

Step 2: Simplify the outer operation. Let $K = a * b$ . We want to maximize $K * 2$ .

$K * 2 = K + 2 - 2 K = 2 - K$ .

To maximize $2 - K$ , we must MINIMIZE $K$ .

Step 3: Apply the condition. We are given $K \geq - 5$ .

$1 - (1 - a) (1 - b) \geq - 5 ⟹ (1 - a) (1 - b) \leq 6$ .

Step 4: Find the minimum $K$ . Since $K = 1 - (1 - a) (1 - b)$ , minimizing $K$ means MAXIMIZING the product $P = (1 - a) (1 - b)$ subject to $P \leq 6$ .

Step 5: Evaluate possible values for $a, b \in {- 3, - 2, - 1, 0, 1, 2}$ .

The terms $(1 - a)$ and $(1 - b)$ belong to the set ${4, 3, 2, 1, 0, - 1}$ .

We want the maximum product of two numbers from this set that is $\leq 6$ .

$4 \times 4 = 16$ (Too large)
$4 \times 3 = 12$ (Too large)
$4 \times 2 = 8$ (Too large)
$3 \times 2 = 6$ (Valid!)

The maximum valid product is $P = 6$ .

Step 6: Calculate the final answer.

Min $K = 1 - 6 = - 5$ .

Max $(a * b) * 2 = 2 - (- 5) = 7$ .

(This is achieved when $1 - a = 3, 1 - b = 2 ⟹ a = - 2, b = - 1$ ).

Answer: 7

Question 6 · Graph Fundamentals, Trees and Connectivity MSQ

Let

G

be a simple connected graph on

n

vertices whose Laplacian matrix

L

has rank

n - 1

. Suppose

G

has exactly

m

edges. Consider the following statements:
(S1) Every cofactor of

L

equals the number of spanning trees of

G

.
(S2) If

G

is a cycle

C_{n}

, the number of spanning trees is

n

.
(S3) The sum of entries in any row of

L

is zero.
Which combination is TRUE?

A.
(S1) only
B.
(S1) and (S3)
C.
(S2) and (S3)
D.
(S1), (S2) and (S3)

Correct Answer:

["B","C","D"]

Step-by-Step Solution

Key idea: this tests three independent Laplacian facts; verify each against the definition rather than trusting memory.

Step 1: (S1) is the Matrix Tree Theorem — every cofactor of $L$ equals $τ (G)$ . TRUE.

Step 2: (S3): row $i$ of $L$ has $de g (v_{i})$ on the diagonal and $- 1$ for each neighbour; sum $= de g (v_{i}) - de g (v_{i}) = 0$ . TRUE.

Step 3: (S2): deleting one edge from the cycle $C_{n}$ leaves a path spanning all $n$ vertices; there are $n$ edges to delete, so $τ (C_{n}) = n$ . TRUE.

Step 4: Since S1, S2, S3 are all true, the option listing all three is correct; the pairwise options are also logically satisfied subsets but in MSQ we mark every option whose stated combination is entirely true. Option B (S1&S3) true, C (S2&S3) true, D (all) true. Option A ("S1 only") is FALSE because S2,S3 also hold.

Answer: B, C, D

Question 7 · Graph Coloring, Covers, Matrices and Special Graphs MCQ

Given below are two statements, one labeled as Assertion (A) and the other as Reason (R).

Assertion (A): The number of simple cycles of length 4 in a simple undirected graph $G$ is exactly $\frac{Tr ( A ^{4} )}{8}$ , where $A$ is the adjacency matrix of $G$ .

Reason (R): The trace of $A^{4}$ equals the total number of closed walks of length 4 in $G$ , and each simple cycle of length 4 generates exactly 8 such closed walks.

A.
Both (A) and (R) are true and (R) is the correct explanation of (A).
B.
Both (A) and (R) are true but (R) is NOT the correct explanation of (A).
C.
(A) is true but (R) is false.
D.
(A) is false but (R) is true.

Correct Answer:

Step-by-Step Solution

Key idea: This is a language-to-math translation question testing the distinction between walks and simple cycles for $k \geq 4$ .

Step 1: Evaluate Reason (R). The trace of $A^{k}$ counts all closed walks of length $k$ . For $k = 4$ , a simple cycle of length 4 (e.g., $u - v - w - x - u$ ) can be traversed starting from any of its 4 vertices and in 2 directions, giving $4 \times 2 = 8$ closed walks. Thus, (R) is a true statement.

Step 2: Evaluate Assertion (A). Does $Tr (A^{4})$ count ONLY simple 4-cycles? No. $A^{4}$ also counts non-simple closed walks, such as $u - v - u - v - u$ (traversing the same edge back and forth twice) or $u - v - w - v - u$ (a triangle with a tail).

Step 3: Because $Tr (A^{4})$ includes these non-simple walks, dividing by 8 does not yield the number of simple 4-cycles. The formula $Tr (A^{k}) /2 k$ only works cleanly for $k = 3$ because you cannot form a non-simple closed walk of length 3 in a simple graph without immediately repeating an edge, which is impossible in 3 steps. Thus, (A) is false.

Step 4: Since (A) is false and (R) is true, the correct option is D.

Answer: D

A question from this chapter

Login to view the complete short notes

Personalised first. High quality throughout.

Built around you, not around a syllabus PDF

Revision that hits your weak spots

Questions calibrated to the real exam

Notes written for recall, not for volume

One place for everything

Honest progress

Unlock the whole course

Discrete Mathematics Short Notes for GATE CS

About Discrete Mathematics Short Notes

Discrete Mathematics Weightage in GATE CS

Discrete Mathematics Chapter Matrix

More from Engineering Mathematics

One Solved Question from Each Discrete Mathematics Chapter

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution