Discrete Mathematics PYQs 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 Previous Year Questions (PYQs)

47 previous year questions from Discrete Mathematics in GATE CS, grouped by chapter with the exam year, answer key and step-by-step solution for each.

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 · 2026_Set2 MCQ

For two different persons

x

and

y

, the predicate

M (x, y)

denotes that x knows y. Consider the following statement.

There is a person who does not know anyone else, but that person is known by everyone else.

Which one of the following expressions represents the above statement?

A.
$(\exists y) (\forall x) ((x \neq = y) \to (M (x, y) \land \neg M (y, x)))$
B.
$(\forall y) (\exists x) ((x \neq = y) \to (M (x, y) \land \neg M (y, x)))$
C.
$(\exists y) (\exists x) ((x \neq = y) \to (M (x, y) \land \neg M (y, x)))$
D.
$(\forall y) (\forall x) ((x \neq = y) \to (M (x, y) \land \neg M (y, x)))$

Correct Answer:

Step-by-Step Solution

Key idea: This is a nested quantifier translation question, recognizable because it describes a specific relational property ("knows") among a domain of people using phrases like "There is a person" and "everyone else".

Step 1: Identify the core components.

"There is a person" $\to \exists y$ . Let this person be $y$ .

"who does not know anyone else" $\to$ For all $x \neq = y$ , $y$ does not know $x$ . This is $\neg M (y, x)$ .

"but that person is known by everyone else" $\to$ For all $x \neq = y$ , $x$ knows $y$ . This is $M (x, y)$ .

Step 2: Combine the conditions for "everyone else".

For any $x$ , if $x \neq = y$ , then both conditions must hold: $M (x, y) \land \neg M (y, x)$ .

This translates to: $\forall x ((x \neq = y) \to (M (x, y) \land \neg M (y, x)))$ .

Step 3: Attach the outer quantifier.

"There is a person $y$ " wraps around the above:

$\exists y \forall x ((x \neq = y) \to (M (x, y) \land \neg M (y, x)))$ .

Step 4: Match with options.

Option A matches this exactly.

Answer: A

Question 2 · Sets, Relations, Functions and Order Structures · 2026_Set2 MSQ

Let $R$ be a binary relation on the set ${1, 2, \dots, 10}$ , where $(x, y) \in R$ if the product of $x$ and $y$ is square of an integer. Which of the following properties is/are satisfied by $R$ ?

A.
Reflexive
B.
Symmetric
C.
Transitive
D.
Antisymmetric

Correct Answer:

["A","B","C"]

Step-by-Step Solution

Key idea: This is a relation properties question, recognizable by the condition that the product of two elements is a perfect square.

Step 1: Check Reflexivity. For any $x \in {1, \dots, 10}$ , $x \cdot x = x^{2}$ , which is a perfect square. Thus, $(x, x) \in R$ . Reflexive is TRUE.

Step 2: Check Symmetry. If $(x, y) \in R$ , then $x \cdot y = k^{2}$ . Since multiplication is commutative, $y \cdot x = k^{2}$ , so $(y, x) \in R$ . Symmetric is TRUE.

Step 3: Check Transitivity. Suppose $(x, y) \in R$ and $(y, z) \in R$ . Then $x \cdot y = a^{2}$ and $y \cdot z = b^{2}$ for some integers $a, b$ . We need to check if $x \cdot z$ is a perfect square. Notice that $(x \cdot y) (y \cdot z) = a^{2} b^{2} ⟹ x \cdot z \cdot y^{2} = (ab)^{2} ⟹ x \cdot z = (ab / y)^{2}$ . For $x \cdot z$ to be an integer square, $y$ must divide $ab$ . Let the prime factorization of $y$ have $p^{e}$ . Since $y ∣ a^{2}$ , $e \leq 2 α$ (where $p^{α} ∣∣ a$ ). Similarly, $e \leq 2 β$ (where $p^{β} ∣∣ b$ ). We need $e \leq α + β$ . This is always true because if $e > α + β$ , then $2 e > 2 α + 2 β$ , which contradicts $e \leq 2 α$ and $e \leq 2 β$ . Thus, $y$ always divides $ab$ , making $ab / y$ an integer. Therefore, $x \cdot z$ is always a perfect square. Transitive is TRUE.

Step 4: Check Antisymmetry. $(1, 4) \in R$ since $1 \cdot 4 = 2^{2}$ , and $(4, 1) \in R$ , but $1 \neq = 4$ . Thus, it is NOT antisymmetric.

Answer: Options A, B, and C.

Question 3 · Combinatorics and Counting · 2026_Set1 MCQ

Consider $4 \times 4$ matrices with their elements from ${0, 1}$ . The number of such matrices with even number of $1$ s in every row and every column is

A.
512
B.
1025
C.
1023
D.
255

Correct Answer:

Step-by-Step Solution

Key idea: This is a binary matrix counting problem with parity constraints, recognizable by the requirement of an "even number of 1s in every row and every column". We solve this by determining the degrees of freedom in the matrix.

Step 1: Consider the top-left $3 \times 3$ submatrix (rows 1-3, columns 1-3). The entries in this submatrix can be chosen completely freely.

Number of ways to fill this $3 \times 3$ block = $2^{3 \times 3} = 2^{9} = 512$ .

Step 2: Determine the remaining cells in the first 3 rows.

For each of the first 3 rows, the entry in the 4th column is uniquely forced to make the row sum even.

Step 3: Determine the remaining cells in the first 3 columns.

For each of the first 3 columns, the entry in the 4th row is uniquely forced to make the column sum even.

Step 4: Determine the bottom-right cell (row 4, column 4).

This cell must satisfy both the 4th row parity and the 4th column parity. In a binary matrix, the sum of all row parities equals the sum of all column parities (both equal the total sum of all elements mod 2). Thus, the two constraints on the bottom-right cell are perfectly consistent, and it is uniquely determined.

Step 5: Calculate the total.

Since all other cells are uniquely determined by the free choices in the $3 \times 3$ submatrix, the total number of valid matrices is exactly 512.

Answer: A

Question 4 · Recurrences and Generating Functions · 2023 MCQ

The Lucas sequence

L_{n}

is defined by the recurrence relation:

L_{n} = L_{n - 1} + L_{n - 2}, for n \geq 3,

with

L_{1} = 1

and

L_{2} = 3

.

Which one of the options given is TRUE?

A.
$L_{n} = (\frac{1 + 5}{2})^{n} + (\frac{1 - 5}{2})^{n}$
B.
$L_{n} = (\frac{1 + 5}{2})^{n} - (\frac{1 - 5}{3})^{n}$
C.
$L_{n} = (\frac{1 + 5}{2})^{n} + (\frac{1 - 5}{3})^{n}$
D.
$L_{n} = (\frac{1 + 5}{2})^{n} - (\frac{1 - 5}{2})^{n}$

Correct Answer:

Step-by-Step Solution

Insight: This is a second-order linear homogeneous recurrence. The characteristic roots are the golden ratio and its conjugate, and the initial conditions perfectly match the sum of their powers.

Exam route: Write the characteristic equation $r^{2} - r - 1 = 0$ . The roots are $α = \frac{1 + 5}{2}$ and $β = \frac{1 - 5}{2}$ . Notice that $α + β = 1$ and $α^{2} + β^{2} = (α + β)^{2} - 2 α β = 1^{2} - 2 (- 1) = 3$ . These exactly match $L_{1} = 1$ and $L_{2} = 3$ . Thus, the coefficients are both 1.

Learning route:

Step 1: Identify the recurrence type. The relation $L_{n} = L_{n - 1} + L_{n - 2}$ is a linear homogeneous recurrence with constant coefficients.

Step 2: Form the characteristic equation. Rewrite as $L_{n} - L_{n - 1} - L_{n - 2} = 0$ . The characteristic equation is $r^{2} - r - 1 = 0$ .

Step 3: Find the roots. Using the quadratic formula, $r = \frac{1 \pm 1 - 4 ( 1 ) ( - 1 )}{2} = \frac{1 \pm 5}{2}$ . Let $α = \frac{1 + 5}{2}$ and $β = \frac{1 - 5}{2}$ .

Step 4: Write the general solution. Since the roots are distinct, $L_{n} = c_{1} α^{n} + c_{2} β^{n}$ .

Step 5: Apply initial conditions.

For $n = 1$ : $c_{1} α + c_{2} β = 1$ .

For $n = 2$ : $c_{1} α^{2} + c_{2} β^{2} = 3$ .

We know $α + β = 1$ (sum of roots) and $α β = - 1$ (product of roots).

Calculate $α^{2} + β^{2} = (α + β)^{2} - 2 α β = 1^{2} - 2 (- 1) = 3$ .

Comparing this with the $n = 2$ condition, we see that $c_{1} = 1$ and $c_{2} = 1$ is a valid solution.

Step 6: Verify with $n = 1$ . $1 \cdot α + 1 \cdot β = α + β = 1$ , which matches $L_{1} = 1$ .

Therefore, the closed form is $L_{n} = α^{n} + β^{n} = (\frac{1 + 5}{2})^{n} + (\frac{1 - 5}{2})^{n}$ .

Answer: A

Question 5 · Algebraic Structures and Groups · 2025_Set1 MSQ

A = {0, 1, 2, 3, \dots}

is the set of non-negative integers. Let

F

be the set of functions from

A

to itself. For any two functions,

f_{1}, f_{2} \in F

, we define

(f_{1} ⨀ f_{2}) (n) = f_{1} (n) + f_{2} (n)

for every number

n

A

. Which of the following is/are CORRECT about the mathematical structure

(F, ⨀)

A.
$(F, ⨀)$ is an Abelian group.
B.
$(F, ⨀)$ is an Abelian monoid.
C.
$(F, ⨀)$ is a non-Abelian group.
D.
$(F, ⨀)$ is a non-Abelian monoid.

Correct Answer:

["B"]

Step-by-Step Solution

Insight: Pointwise operations inherit algebraic properties from the base set. The base set here is non-negative integers under addition, which forms a monoid but not a group.

Exam route: Check the axioms in order. Closure: sum of non-negative integers is non-negative (Yes). Associativity: inherited from integer addition (Yes). Identity: the zero function $z (n) = 0$ maps $A \to A$ (Yes). Inverses: for $f (n) = 1$ , the inverse would need $g (n) = - 1 \in / A$ (No). Commutativity: integer addition is commutative (Yes). Thus, it is an Abelian monoid.

Learning route:

The set $F$ contains functions $f : A \to A$ where $A = {0, 1, 2, \dots}$ .
The operation is $(f_{1} ⨀ f_{2}) (n) = f_{1} (n) + f_{2} (n)$ .
Since $f_{1} (n) \geq 0$ and $f_{2} (n) \geq 0$ , their sum is $\geq 0$ , so the result is in $F$ . Closure holds.
Associativity and commutativity follow directly from the properties of standard addition.
The identity is the constant function $e (n) = 0$ . Since $0 \in A$ , $e \in F$ .
For inverses, consider $f (n) = 1$ . We need $g (n)$ such that $1 + g (n) = 0 ⟹ g (n) = - 1$ . But $- 1 \in / A$ , so $g \in / F$ . Inverses fail.

Conclusion: It is an Abelian monoid.

Question 6 · Graph Fundamentals, Trees and Connectivity · 2026_Set2 MCQ

Consider a complete graph

K_{n}

with

n

vertices

(n > 4)

. Note that multiple spanning trees can be constructed over

K_{n}

. Each of these spanning trees is represented as a set of edges. The Jaccard coefficient between any two sets is defined as the ratio of the size of the intersection of the two sets to the size of the union of the two sets.

Which one of the following options gives the lowest possible value for the Jaccard coefficient between any two spanning trees of

K_{n}

A.
$\frac{1}{n}$
B.
$\frac{1}{2 n - 3}$
C.
0
D.
$\frac{1}{n - 1}$

Correct Answer:

Step-by-Step Solution

Key idea: This is a Jaccard coefficient minimization question on spanning trees of $K_{n}$ , recognisable because it asks for the lowest possible Jaccard value between two spanning trees.

Why this method applies: The Jaccard coefficient $J (T_{1}, T_{2}) = \frac{∣ E _{1} \cap E _{2} ∣}{∣ E _{1} \cup E _{2} ∣}$ . To minimize $J$ , we minimize the intersection. The question is whether two edge-disjoint spanning trees can exist in $K_{n}$ .

Step 1: Each spanning tree of $K_{n}$ has exactly $n - 1$ edges. Two disjoint trees need $2 (n - 1)$ distinct edges.

Step 2: $K_{n}$ has $(2 n) = \frac{n ( n - 1 )}{2}$ edges. For two disjoint spanning trees to exist, we need:

$\frac{n ( n - 1 )}{2} \geq 2 (n - 1) ⟹ \frac{n}{2} \geq 2 ⟹ n \geq 4$

Step 3: Since the problem states $n > 4$ , the condition $n \geq 4$ is satisfied. Therefore, $K_{n}$ contains two completely edge-disjoint spanning trees.

Step 4: When $E_{1} \cap E_{2} = \emptyset$ , the Jaccard coefficient is:

$J = \frac{0}{2 ( n - 1 ) - 0} = 0$

Step 5: Check the options. Option C gives 0, which is achievable.

Answer: C

Question 7 · Graph Coloring, Covers, Matrices and Special Graphs · 2026_Set1 MSQ

Let

G (V, E)

be a simple, undirected graph. A vertex cover of

G

is a subset

V^{'} \subseteq V

such that for every

(u, v) \in E

u \in V^{'}

v \in V^{'}

. Let the size of the smallest vertex cover in

G

k

. Let

S

be any vertex cover of size

k

.

For a vertex

v \in V

, which of the following constraints will always ensure that

v \in S

A.
The degree of $v$ is at least $k + 1$
B.
The vertex $v$ is on a path of length $k + 1$
C.
The vertex $v$ is on a cycle of length $k + 1$
D.
The vertex $v$ is a part of a clique of size $k$

Correct Answer:

["A"]

Step-by-Step Solution

Insight: If a vertex has degree $\geq k + 1$ , excluding it from the vertex cover forces all its neighbors into the cover, requiring at least $k + 1$ vertices, which contradicts the cover size being $k$ .

Exam route: Test the degree condition. If $v$ is not in $S$ , its neighbors must be. If $de g (v) \geq k + 1$ , $∣ S ∣ \geq k + 1$ , a contradiction. Thus $v$ must be in $S$ .

Learning route:

Option A: True. If $v \in / S$ , all $de g (v)$ neighbors must be in $S$ to cover the edges incident to $v$ . Since $de g (v) \geq k + 1$ , this requires $∣ S ∣ \geq k + 1$ , contradicting $∣ S ∣ = k$ . Thus, $v$ must be in $S$ .
Option B: False. Consider a path of length 3 (4 vertices: $a - b - c - d$ ). The minimum vertex cover size is $k = 2$ (e.g., $S = {b, c}$ ). Vertex $a$ is on the path but not in $S$ .
Option C: False. Consider a cycle of length 3 ( $C_{3}$ ). The minimum vertex cover size is $k = 2$ (e.g., $S = {a, b}$ ). Vertex $c$ is on the cycle but not in $S$ .
Option D: False. Consider a clique of size 3 ( $K_{3}$ ). The minimum vertex cover size is $k = 2$ (e.g., $S = {a, b}$ ). Vertex $c$ is part of the clique but not in $S$ .

A question from this chapter

Login to view the complete previous-year questions and solutions

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 PYQs for GATE CS

About Discrete Mathematics Previous Year Questions (PYQs)

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