Discrete Mathematics Gate Questions

Here, We will see Discrete Mathematics GATE Questions from previous year’s papers and the syllabus of Discrete Mathematics for GATE Exam.

1. Discrete Mathematics in Gate CSE Exam

Discrete Mathematics is a foundational pillar of the GATE Computer Science Engineering (CSE) exam, testing candidates’ logical reasoning, problem-solving skills, and understanding of mathematical structures critical to computer science. The subject accounts for a significant portion of the Engineering Mathematics section, with topics like propositional logic, graph theory, combinatorics, and set theory frequently appearing in questions

2. Discrete Mathematics Syllabus

The syllabus for Discrete Mathematics in GATE CSE includes:

1. Mathematical Logic: Propositional and first-order logic, logical equivalences.
2. Set Theory & Algebra: Sets, relations, functions, partial orders, lattices, and groups.
3. Graph Theory: Connectivity, matching, graph coloring, trees, and planar graphs.
4. Combinatorics: Counting principles, recurrence relations, generating functions, permutations, and combinations.
5. Recurrence Relations & Generating Functions: Solving linear recurrences and applications.

Discrete Mathematics Gate Questions

Q. What is the possible number of reflexive relations on a set of 5 elements?

1. 2¹⁰
2. 2¹⁵
3. 2²⁰
4. 2²⁵

Q. For the graph shown, which of the following paths is a Hamilton circuit?

1. ABCDCFDEF
2. AEAAEDCBAF
3. AEFDCBA
4. AFCDEBA

Q. Given r₁₂=0.6, r₁₃=0.5 and r₂₃=0.8, the value of r_12.3 is

1. 0.47
2. 0.40
3. 0.74
4. 0.64

Q. Which one of the following is NOT necessarily a property of a Group?

1. Commutativity
2. Associativity
3. Existence of inverse for every element
4. Existence of identity

Q. Which one is the correct translation of the following statement into mathematical logic?
“None of my friends are perfect.”

1. ¬Ǝx(p(x) Λ q(x))
2. Ǝx(¬p(x) Λ q(x))
3. Ǝx(¬p(x) Λ ¬q(x))
4. Ǝx(p(x) Λ ¬q(x))

Q. Degree of each vertex in K_n is

1. n
2. n-1
3. n-2
4. 2n-1

Q. What is the value of k for which the following system of equations has no solution:
2x-8y=3 and kx+4y=10

1. -2
2. 1
3. -1
4. 2

Q. Let G be a multiplicative group and aЄG. If the order of a is 6, then the order of a⁵ is equal to :

1. 1
2. 5
3. 6
4. 30

Q. Let X1,…..X50 be independent random variables following N(0,1) distribution.
Let ∑_i=1⁵⁰ X_i², and E(Y) = a and Var(Y) = b. Then, the ordered pair (a,b) is:

1. (50,100)
2. (50,50)
3. (25,50)
4. (25,100)

Q. Total number of simple graphs that can be drawn using six vertices are:

1. 2¹⁵
2. 2¹⁴
3. 2¹³
4. 2¹²

Q. The equivalent relational algebra expression for the query “Find the names of suppliers who supplied all the items to all the customers”.

1. ¬t/t Є supplier (Q(t))
2. ∀t [Sname]/t Є supplier (Q(t))
3. t/¬t Є supplier (Q(t))
4. ∀t/(~Q(t))

Q. The number of un-labeled non-isomorphic graphs with four vertices is:

1. 12
2. 11
3. 10
4. 9

Q. The largest number of faces in a simple connected maximal planar graph with 100 vertices is :

1. 200
2. 198
3. 196
4. 96

Q. A connected planar graph having 6 vertices, 7 edges contains ________ regions.

1. 15
2. 11
3. 3
4. 1

Q. The solution of the recurrence relation a_r=a_r-1+2a_r-2 with a₀=2, a₁=7 is

1. a_r = 3^r + 1^r
2. 2a_r = 2^r/3 – 1^r
3. a_r = 3^r+1 – (-1)^r
4. a_r = 3(2)^r – (-1)^r

Q. The ________ of a relationship is 0 if there is no explicit need for the relationship to occur or the relationship is optional.

1. modality
2. cardinality
3. entity
4. structured analysis

Q. The number of ways to cut a six-sided convex polygon whose vertices are labeled into four triangles using diagonal lines that do not cross is

1. 13
2. 14
3. 12
4. 11

Q. For the probability density function f(x) = cx²(1-x), 0<x<1, the value of constant c and mean of the distribution are :

1. 6,0.4
2. 8,0.5
3. 12,0.6
4. 8,0.6

Q. If A and B are two sets. A binary relation from set A and set B is any subset of the ________ .

1. Cartesian Product A×B
2. Union AՍB
3. Intersection A∩B
4. Addition A+B

Q. One root of x³-x-4=0 lies in (1,2). In bisection method, after first iteration the root lies in the interval _______ .

1. (1,1.5)
2. (1.5,2)
3. (1.25,1.75)
4. (1.75,2)

Q. What will be the result of following relational algebra expression?
π_A,B(σ_C=10(R))

1. Print columns A&B from relation R when C=10
2. Print C=10 from relation R
3. Print all data of relation R when C=10
4. Print A,B,C from relation B when C=10

Q. The real root of the equation x³-x-5=0 lying between 1 and 2 after first iteration by Netwon-Raphson method is _______, if initial approximation is taken as x₀ = 2 Є [1,2] :

1. 1.909
2. 1.904
3. 1.921
4. 1.940

Q. Which of the following statements is false?

1. (P Λ Q) V (~P Λ Q) V (P Λ ~Q) is equal to ~Q Λ ~P
2. (P Λ Q) V (~P Λ Q) V (P Λ ~Q) is equal to Q V P
3. (P Λ Q) V (~P Λ Q) V (P Λ ~Q) is equal to Q V (P Λ ~Q)
4. (P Λ Q) V (~P Λ Q) V (P Λ ~Q) is equal to P V (Q Λ ~P)

Q. Let X be uniform random variable on [0,4] and Y be uniform random variable on [0,1]. If X and Y are independent, then P(max{X,Y}>3) is equal to :

1. 1/4
2. 1/2
3. 1/8
4. 1

Q. Find the volume of the solid obtained by rotating the region bound by the curves y = x³+1, x=1, and y=0 about the x-axis

1. 23π/7
2. 16π/7
3. 2π
4. 19π/7

Q. Let P(x) be “x is perfect”, F(x) be “x is your friend” and the domain be all people. The statement, “At least one of your friends is perfect” is :∀→ΛƎ↓↑

1. ∀x (F(x)→P(x))
2. ∀x (F(x)ΛP(x))
3. Ǝx (F(x)ΛP(x))
4. Ǝx (F(x)→P(x))

Q. Consider a relation R with attributes {A,B,C} and functional dependency set S = {A→B,A→C}. Then relation R can be decomposed into two relations :

1. R₁{A,B} AND R₂{A,C}
2. R₁{A,B} AND R₂{B,C}
3. R₁{A,B,C} AND R₂{A,C}
4. None of the above

Q. Let the random variable X has a mixed distributions with probability P(X=0) and the density function.
f_x(x) = βx²(1-x), 0<x<1
=0, otherwise
If the expectation of X is α, then the value of 4α+β is equal to :

1. 9/2
2. 6
3. 9
4. 5/2

Q. Which of the following relational calculus expressions is not safe ?
i. {t | Ǝu Є R₁ ( t[A] = u[A]) Λ ¬Ǝs Є R₂ (t[A] = s[A])}
ii. {t | ∀u Є R₁ (u[A] = “x” ⇒ Ǝs Є R₂ (t[A] = s[A] Λ s[A] = u[A]))}
iii. {t | ¬(t Є R₁)}
iv. {t | Ǝu Є R₁ (t[A] = u[A]) Λ Ǝs Є R₂ (t[A] = s[A])}

1. (i)
2. (ii)
3. (iii)
4. (iv)

Q. L₁ is a recursively enumerable language over ∑. An algorithm A effectively enumerates its words as ꙍ₁,ꙍ₂,ꙍ₃,…Define another language L₂ over ∑ Union {#} as {ꙍ_i#ꙍ_j : ꙍ_i,ꙍ_j Є L₁, i<j. Here # is new symbol. Consider the following assertions.
• S₁ : L₁ is recursive implies L₂ is recursive
• S₂ : L₂ is recursive implies L₁ is recursive
Which of the following statements is true?

1. Both S₁ and S₂ are true
2. S₁ is true but S₂ is not necessarily true
3. S₂ is true but S₁ is not necessarily true
4. Neither is necessarily true

Q. The secant method formula for finding the square root of a real number R from the equation x²-R=0 is:

1. x_i+1 = (x_i.x_i-1)/(x_i+x_i+1)
2. x_i+1 = (x_i.x_i-1+R)/(x_i+x_i-1)
3. x_i+1 = 1/2 (x_i +R/x_i)
4. x_i+1 = (2x_i²+x_i.x_i-1-R)/(x_i+x_i-1)

Q. Which of the following is an advantage of adjacency list representation over adjacency matrix representation of a graph?

1. In adjacency list representation, space is saved for sparse graphs.
2. Deleting a vertex in adjacency list representation is easier than adjacency matrix representation.
3. Adding a vertex in adjacency list representation is easier than adjacency matrix representation.
4. All of the option.

Q. If A and B are two sets and AUB=A∩B then

1. A=Φ
2. B=Φ
3. A≠B
4. A=B

Q. A partial ordered relation is transitive, reflexive and __________

1. antisymmetric
2. bisymmetric
3. antireflexive
4. asymmetric

Q. There are four bus lines between A and B; and three bus lines between B and 1. The number of way a person roundtrip by bus from A to C by way of B will be

1. 12
2. 7
3. 144
4. 264

Q. What is the Cartesian product of A={1,2} and B={a,b}?

1. {(1,a),(1,b),(2,a),(b,b)}
2. {(1,1),(2,2),(a,a),(b,b)}
3. {(1,a),(2,a),(1,b),(2,b)}
4. {(1,1),(a,a),(2,a),(1,b)}

Q. The number of diagonals that can be drawn by joining the vertices of an octagon is

1. 28
2. 48
3. 20
4. None of the option

Q. Let the predicates D(x,y) mean “team x defeated team y” and P(x,y) mean “team x has played team y”. The quantified formula for the statement that there is a team that has beaten every team it has played is: ×→Ǝ∀

1. Ǝx∀y(P(x,y) → D(x,y))
2. Ǝx∀y(D(x,y) → P(x,y))
3. ∀xƎy(P(x,y) → D(x,y))
4. ∀xƎy(D(x,y) → P(x,y))

Q. The function f(x)=x(x+3)e^-x/2 satisfies all the conditions of Rolle’s theorem in [-3,0]. The value of c is :

1. -3
2. -2
3. 3
4. 0

Q. Let the random variable X has a mixed distributions with probability P(X=0)=α and the density function.
fx(x) = {βx²(1-x), 0<x<1
{0, otherwise
If the expectation of X is α, then the value of 4α+β is equal to :

1. 9/2
2. 6
3. 9
4. 5/2

Q. The first order logic statement ((RVQ) Λ (PV~Q)) is equivalent to which of the following?

1. ((RV~Q) Λ (PV~Q) Λ (RVP))
2. ((RVQ) Λ (PV~Q) Λ (RVP))
3. ((RVQ) Λ (PV~Q) Λ (RV~P))
4. ((RVQ) Λ (PV~Q) Λ (~RVP))

Q. With usual notations, the properties of maxima and minima under various conditions are ________ .

1. P-i,Q-iii,R-iv,S-ii
2. P-ii,Q-i,R-iii,S-iv
3. P-iii,Q-iv,R-ii,S-i
4. P-iv,Q-iii,R-ii,S-i

Q. A path in graph G, which contains every vertex of G and only once?

1. Euler circuit
2. Hamiltonian path
3. Euler Path
4. Hamiltonian Circuit

Q. Consider the following graph L and find the bridges,if any.

1. No bridge
2. {d,e}
3. {c,d}
4. {c,d} and {c,f}

Q. On a set A={a,b,c,d} a binary operation * is defined as given in the following table.
The relation is

1. Commutative but not associative
2. Neither commutative nor associative
3. Both commutative and associative
4. Associative but not commutative

Q. Let N={1,2,3,…} be ordered by divisibility, which of the following subset is totally ordered?

1. (2,6,24)
2. (3,5,15)
3. (2,9,16)
4. (4,15,30)

Q. The number of operations in matrix multiplication M1,M2,M3,M4 and M5 of sizes 5×10,10×100,100×2,2×20 and 20×50 respectively will be:

1. 5830
2. 4600
3. 6900
4. 12890

Q. One root of x³-x-4=0 lies in (1,2). In bisection method, after first iteration the root lies in the interval __________ .

1. (1,1.5)
2. (1.5,2)
3. (1.25,1.75)
4. (1.75,2)

Q. Considering the following graph, which one of the following set of edges represents all the bridges of the given graph?

1. (a,b),(e,f)
2. (a,b),(a,c)
3. (c,d),(d,h)
4. (a,b)

Q. How many onto (or surjective) functions are there from an n-element (n>=2) set to a 2-element set?

1. 2ⁿ
2. 2ⁿ -1
3. 2ⁿ -2
4. 2(2ⁿ -2)

Q. In propositional logic, which of the following is equivalent to p→q?

1. ~p→q
2. ~p V q
3. ~pV ~ q
4. p→~q

Q. Let G be a complete undirected graph on 8 vertices. If vertices of G are labelled, then the number of distinct cycles of length 5 in G is equal to:

1. 15
2. 30
3. 56
4. 60

Q. Maximum degree of any node in a simple graph with n vertices is

1. n-1
2. n
3. n/2
4. n-2

Q. Let P(x) be “x is perfect”, F(x) be “x is your friend” and the domain be all people. The statement, “At least one of your friends is perfect” is :

1. ∀x (F(x) → P(x))
2. ∀x (F(x) Λ P(x))
3. Ǝx (F(x) Λ P(x))
4. Ǝx (F(x) → P(x))

Q. Power set of empty set has exactly __________ subset

1. One
2. Two
3. Zero
4. Three

Q. Which of the following statements is/are TRUE for an undirected graph?
P. Number of odd degree vertices is even
Q. Sum of degrees of all vertices is even

1. P only
2. Q only
3. Both P and Q
4. Neither P nor Q

Q. The particular solution of the recurrence relation a_r+2 – 4a_r+1 + 4a_r = 2^r is:

1. r.2^r
2. r(r-1)2^r-1
3. r(r-1)2^r-2
4. r(r-1)2^r-3

Q. An expression in the domain relational calculus is of the form:

1. {P(x₁,x₂,…..,x_n)|<x₁,x₂,…..,x_n>}
2. {x₁,x₂,…..,x_n|<x₁,x₂,…..,x_n>}
3. {x₁,x₂,…..,x_n|x₁,x₂,…..,x_n}
4. {<x₁,x₂,…..,x_n>|P(x₁,x₂,…..,x_n)}

Q. Given an undirected graph G with V vertices and E edges, the sum of the degrees of all vertices is

1. E
2. 2E
3. V
4. 2V

Q. If f:{a,b}* -> {a,b}* be given by f(n)=ax for every value of nЄ{1.b} , then f is

1. one to one not onto
2. one to one and onto
3. not one to one and not onto
4. not one to one and onto

Q. The number of the edges in a regular graph of degree ‘d’ and vertices ‘n’ is

1. Maximum of n,d
2. n+d
3. nd
4. nd/2

Q. A polynomial p(x) is such that p(0)=5, p(1)=4, p(2)=9 and p(3)=20. The minimum degree it can have is

1. 1
2. 2
3. 3
4. 4

Q. Given the truth table of a Binary Operation $ as follows:
Identify the matching Boolean Expression.

1. X$¬Y
2. ¬X$Y
3. ¬X$¬Y
4. none of the options

Q. In an undirected graph, if we add the degrees of all vertices, it is:

1. odd
2. even
3. cannot be determined
4. always n+1, where n is number of nodes

Q. In a given following graph among the following sequences:
I. abeghf
II. abfehg
III. abfhge
IV. afghbe
Which are depth first traversals of the above graph?

1. I,II and IV only
2. I and IV only
3. II,III and IV only
4. I,III and IV only

Q. The following graph has no Euler circuit because

1. It has 7 vertices.
2. It is even-valent (all vertices have even valence).
3. It is not connected.
4. It does not have a Euler circuit.

Q. If ∆f(x)=f(x+h)-f(x), then a constant k, ∆k

1. 1
2. 0
3. f(k)-f(0)
4. f(x+k)-f(x)

Q. Which of the following statements is/are TRUE?
S1:The existence of an Euler circuit implies that an Euler path exists.
S2:The existence of an Euler path implies that an Euler circuit exists.

1. S1 is true.
2. S2 is true.
3. S1 and S2 both are true.
4. S1 and S2 both are false.

Q. If S be an infinite set and S₁…….,S_n be sets such that S₁ U S₂ U ……U S_n, then

1. at least one of the set S_i is a finite set.
2. not more than one of the sets S_i can be finite.
3. at least one of the sets S_i is an infinite set.
4. not more than one of the sets S_i can be infinite.

Q. Which of the following propositions is tautology?

1. (p V q) → q
2. p V (q→p)
3. p V (p→q)
4. Both (B) and (C)

Q. Mala has a colouring book in which each English letter is drawn two times. She wants to paint each of these 52 prints with one of k colours, such that the colour-pairs used to colour ay two letters are different. Both prints of a letter can also be coloured with the same colour. What is the minimum value of k that satisfies this requirement?

1. 9
2. 8
3. 7
4. 6

Q. Let G be a simple undirected graph on n=3x vertices (x≥1) with chromatic number 3, then maximum number of edges in G is

1. n(n-1)/2
2. n^(n-2)
3. nx
4. n

Q. What is the Cardinality of the Power set of the set {0,1,2}?

1. 8
2. 6
3. 7
4. 9

Q. What is the total number of ways to reach from A to B in the network given?

1. 12
2. 16
3. 20
4. 22

Q. Let G be a simple undirected planar graph on 10Nvertices with 15 edges. If G is a connected graph, then the number of bounded faces in any embedding of G on the plane is equal to:

1. 3
2. 4
3. 5
4. 6

Q. If a planner graph, having 25 vertices divides the plane into 17 different regions. Then how many edges are used to connect the vertices in this graph.

1. 20
2. 30
3. 40
4. 50

Q. Consider the set S={1,ω,ω²}, where ω and ω² are cube roots of unity. If * denotes the multiplication operation, the structure (S,*) forms:

1. A group
2. A ring
3. An integral domain
4. A field

Q. The number of integers between 1 and 500 (both inclusive) that are divisible by 3 or 5 or 7 is __________ .

1. 269
2. 270
3. 271
4. 272

Q. If G is an undirected planar graph on N vertices with E edges then

1. e≤n
2. e≤2n
3. e≤3n
4. None of the option

Q. The number of 4 digit numbers which contain not more than two different digits is:

1. 576
2. 567
3. 513
4. 504

Q. The relation {(1,2),(1,3),(3,1),(1,1),(3,3),(3,2),(1,4),(4,2),(3,4)} is

1. Reflexive
2. Transitive
3. Symmetric
4. Asymmetric

Q. Choose the most appropriate definition of plane graph.

1. A simple graph which is isomorphic to hamiltonian graph.
2. A graph drawn in a plane in such a way that if the vertex set of graph can be partitioned into two non-empty disjoint subset X andY in such a way that each edge of G has one end in X and one end in Y.
3. A graph drawn in a plane in such a way that any pair of edges meet only at their end vertices.
4. None of the option.

Q. Let G be a simple connected planar graph with 13 vertices and 19 edges. Then, the number of faces in the planar embedding of the graph is

1. 6
2. 8
3. 9
4. 13

Q. The number of ways in which a team of eleven players can be selected from 22 players including 2 of them and excluding 4 of them is

1. ¹⁶C₁₁
2. ¹⁶C₅
3. ¹⁶C₉
4. ²⁰C₉

Q. Let L be a lattice. Then for every a and b in L which one of the following is correct?

1. aVb = aΛb
2. a V (bVc) = (aVb) V c
3. a V (bΛc) = a
4. a V (bVc) = b

Q. A connected planar graph divides the plane into a number of regions. If the graph has eight vertices and these are linked by 13 edges, then the number of regions is

1. 5
2. 6
3. 7
4. 8

Q. Which of the following is FALSE?
Read Λ as AND, V as OR, ~ as NOT, → as one way implication and ↔ as two way implication?

1. ((x→y) Λ x) →y
2. ((~x→y) Λ (~x Λ ~y)) →x
3. (x→(x V y))
4. ((x V y)↔(~x V ~y))

Q. If B is a Boolean algebra, then which of the following is true?

1. B is a finite but not complemented lattice
2. B is a finite, complemented and distributive lattice
3. B is a finite,distributive but not complemented lattice
4. B is not distributive lattice