Subject analysis · 2017–2026

Discrete Mathematics

Every GATE CS question on Discrete Mathematics, with how the marks are spread across years and topics.

Practise Discrete Mathematics

Questions

75

7 topics

Avg marks / year

11.3

113 marks over 10 years

Peak year

2024

16 marks

Trend

Rising

+18% last 3 yrs

Marks per year

Both shifts counted where there were two · peak highlighted

Rising +18%
avg 11.3
12
9
6
8
13
15
12
16
11
11
'17'18'19'20'21'22'23'24'25'26

Topic share

Share of Discrete Mathematics's 113 marks

7

topics

  • Graph Theory24%
  • Propositional and First-Order Quantifier Logic17%
  • Combinatorics13%
  • Sets, Relations, Functions, Partial Orders, Lattices13%
  • Algebraic Structures13%
  • Advanced Graph Bounds12%
  • Recurrence Relations and Generating Functions8%

Topic × year heatmap

Marks from each topic in each year — darker is heavier. Topics that light up every column are the safest bets.

'17'18'19'20'21'22'23'24'25'26
Graph Theory221372424
Propositional and First-Order Quantifier Logic522221131
Combinatorics21231213
Sets, Relations, Functions, Partial Orders, Lattices12132231
Algebraic Structures12121242
Advanced Graph Bounds122242
Recurrence Relations and Generating Functions21411
From RENYXERAPractise this subject in the exam simulatorTimed, GATE-style tests with analytics that find your weak topics.

All 75 Discrete Mathematics questions

2026 7 questions · 11 marks
  1. FN · Q12Consider 4 4 matrices with their elements from \ 0, 1\ . The number of such matrices with even number of 1s in every row and every column isCombinatorics · MCQ · 1 mark
  2. FN · Q47Let G(V, E) be a simple, undirected graph. A vertex cover of G is a subset V' V such that for every (u, v) E , u V' or v V' . Let the size of the smallest vert…Advanced Graph Bounds · MSQ · 2 marks
  3. FN · Q55An undirected, unweighted, simple graph G(V, E) is said to be 2-colorable if there exists a function c : V \ 0, 1\ such that for every (u, v) E , c(u) c(v) . W…Graph Theory · MSQ · 2 marks
  4. FN · Q57Let G be an undirected graph, which is a path on 8 vertices. The number of matchings in G is . (answer in integer)Combinatorics · NAT · 2 marks
  5. AN · Q11For 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…Propositional and First-Order Quantifier Logic · MCQ · 1 mark
  6. AN · Q26Let R be a binary relation on the set \ 1, 2, , 10\ , where (x, y) R if the product of x and y is square of an integer. Which of the following properties is/ar…Sets, Relations, Functions, Partial Orders, Lattices · MSQ · 1 mark
  7. AN · Q36Consider 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 repres…Graph Theory · MCQ · 2 marks
2025 7 questions · 11 marks
  1. FN · Q17g(.) is a function from A to B , f(.) is a function from B to C , and their composition defined as f(g(.)) is a mapping from A to C . If f(.) and f(g(.)) are o…Sets, Relations, Functions, Partial Orders, Lattices · MCQ · 1 mark
  2. FN · Q30Let S be the set of all ternary strings defined over the alphabet \ a, b, c\ . Consider all strings in S that contain at least one occurrence of two consecutiv…Combinatorics · NAT · 1 mark
  3. FN · Q43Let G(V, E) be an undirected and unweighted graph with 100 vertices. Let d(u, v) denote the number of edges in a shortest path between vertices u and v in V .…Graph Theory · MCQ · 2 marks
  4. FN · Q48Which of the following predicate logic formulae/formula is/are CORRECT representation(s) of the statement: “Everyone has exactly one mother”? The meanings of t…Propositional and First-Order Quantifier Logic · MSQ · 2 marks
  5. FN · Q49A = 0, 1, 2, 3, ... 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 F we define (f 1 f 2)(…Algebraic Structures · MSQ · 2 marks
  6. AN · Q15Let P(x) be an arbitrary predicate over the domain of natural numbers. Which ONE of the following statements is TRUE?Propositional and First-Order Quantifier Logic · MCQ · 1 mark
  7. AN · Q42Let F be the set of all functions from \ 1, , n\ to \ 0, 1\ . Define the binary relation on F as follows: f, g F, f g if and only if x \ 1, , n\ , f(x) g(x) ,…Sets, Relations, Functions, Partial Orders, Lattices · MSQ · 2 marks
2024 11 questions · 16 marks
  1. FN · Q32Let A and B be non-empty finite sets such that there exist one-to-one and onto functions (i) from A to B and (ii) from A A to A B . The number of possible valu…Sets, Relations, Functions, Partial Orders, Lattices · NAT · 1 mark
  2. FN · Q34The number of spanning trees in a complete graph of 4 vertices labelled A, B, C, and D is .Graph Theory · NAT · 1 mark
  3. FN · Q51The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. Let G be any graph with n vertices and chromatic numb…Advanced Graph Bounds · MSQ · 2 marks
  4. FN · Q52Consider the operators and defined by a b = a + 2b , a b = ab , for positive integers. Which of the following statements is/are TRUE?Algebraic Structures · MSQ · 2 marks
  5. AN · Q12Let p and q be the following propositions: p : Fail grade can be given. q : Student scores more than 50% marks. Consider the statement: “ Fail grade cannot be…Propositional and First-Order Quantifier Logic · MCQ · 1 mark
  6. AN · Q15Let T(n) be the recurrence relation defined as follows: T(0) = 1 , T(1) = 2 and T(n) = 5T(n - 1) - 6T(n - 2) for n 2 Which one of the following statements is T…Recurrence Relations and Generating Functions · MCQ · 1 mark
  7. AN · Q17Let A be the adjacency matrix of a simple undirected graph G . Suppose A is its own inverse. Which one of the following statements is always TRUE?Graph Theory · MCQ · 1 mark
  8. AN · Q34Let P be the partial order defined on the set \ 1, 2, 3, 4\ as follows: P = \ (x, x) x \ 1, 2, 3, 4\ \ \ (1, 2), (3, 2), (3, 4)\ The number of total orders on…Sets, Relations, Functions, Partial Orders, Lattices · NAT · 1 mark
  9. AN · Q51Let G be an undirected connected graph in which every edge has a positive integer weight. Suppose that every spanning tree in G has even weight. Which of the f…Graph Theory · MSQ · 2 marks
  10. AN · Q60The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. The chromatic number of the following graph is .Advanced Graph Bounds · NAT · 2 marks
  11. AN · Q63Let Z n be the group of integers \ 0, 1, 2, , n - 1\ with addition modulo n as the group operation. The number of elements in the group Z 2 Z 3 Z 4 that are th…Algebraic Structures · NAT · 2 marks
2023 7 questions · 12 marks
  1. FN · Q15The Lucas sequence L n is defined by the recurrence relation: L n = L n-1 + L n-2 , for n 3, with L 1 = 1 and L 2 = 3 . Which one of the options given is TRUE?Recurrence Relations and Generating Functions · MCQ · 1 mark
  2. FN · Q26Geetha has a conjecture about integers, which is of the form x (P(x) y Q(x, y)) , where P is a statement about integers, and Q is a statement about pairs of in…Propositional and First-Order Quantifier Logic · MSQ · 1 mark
  3. FN · Q48Let U = \ 1, 2, , n\ , where n is a large positive integer greater than 1000. Let k be a positive integer less than n . Let A, B be subsets of U with A = B = k…Combinatorics · MCQ · 2 marks
  4. FN · Q49Let f : A B be an onto (or surjective) function, where A and B are non-empty sets. Define an equivalence relation on the set A as a 1 a 2 if f(a 1) = f(a 2), w…Sets, Relations, Functions, Partial Orders, Lattices · MSQ · 2 marks
  5. FN · Q51Let X be a set and 2 X denote the powerset of X. Define a binary operation on 2 X as follows: A B = (A - B) (B - A) Let H = (2 X, ). Which of the following sta…Algebraic Structures · MSQ · 2 marks
  6. FN · Q55Let G be a simple, finite, undirected graph with vertex set \ v 1, , v n\ . Let (G) denote the maximum degree of G and let N = \ 1, 2, \ denote the set of all…Advanced Graph Bounds · MSQ · 2 marks
  7. FN · Q56Let U = \ 1, 2, 3\ . Let 2 U denote the powerset of U. Consider an undirected graph G whose vertex set is 2 U. For any A, B 2 U, (A, B) is an edge in G if and…Graph Theory · NAT · 2 marks
2022 9 questions · 15 marks
  1. FN · Q27Which of the following statements is/are TRUE for a group G?Algebraic Structures · MSQ · 1 mark
  2. FN · Q30Consider a simple undirected graph of 10 vertices. If the graph is disconnected, then the maximum number of edges it can have is .Graph Theory · NAT · 1 mark
  3. FN · Q32The number of arrangements of six identical balls in three identical bins is .Combinatorics · NAT · 1 mark
  4. FN · Q36Which one of the following is the closed form for the generating function of the sequence \ a n\ n 0 defined below? a n = cases n + 1, & n is odd \\ 1, & other…Recurrence Relations and Generating Functions · MCQ · 2 marks
  5. FN · Q37Consider a simple undirected unweighted graph with at least three vertices. If A is the adjacency matrix of the graph, then the number of 3-cycles in the graph…Graph Theory · MCQ · 2 marks
  6. FN · Q50The following simple undirected graph is referred to as the Peterson graph. Which of the following statements is/are TRUE?Advanced Graph Bounds · MSQ · 2 marks
  7. FN · Q51Consider the following recurrence: f(1) = 1; f(2n) = 2f(n) - 1, for n 1; f(2n + 1) = 2f(n) + 1, for n 1; Then, which of the following statements is/are TRUE?Recurrence Relations and Generating Functions · MSQ · 2 marks
  8. FN · Q52Which of the properties hold for the adjacency matrix A of a simple undirected unweighted graph having n vertices?Graph Theory · MSQ · 2 marks
  9. FN · Q58Let G(V, E) be a directed graph, where V = \ 1, 2, 3, 4, 5\ is the set of vertices and E is the set of directed edges, as defined by the following adjacency ma…Graph Theory · NAT · 2 marks
2021 9 questions · 13 marks
  1. FN · Q17Let p and q be two propositions. Consider the following two formulae in propositional logic. S 1 : ( p (p q)) p S 2 : q ( p (p q)) Which one of the following c…Propositional and First-Order Quantifier Logic · MCQ · 1 mark
  2. FN · Q26In an undirected connected planar graph G, there are eight vertices and five faces. The number of edges in G is .Graph Theory · NAT · 1 mark
  3. FN · Q29There are 6 jobs with distinct difficulty levels, and 3 computers with distinct processing speeds. Each job is assigned to a computer such that: • The fastest…Combinatorics · NAT · 1 mark
  4. FN · Q44Let G be a group of order 6, and H be a subgroup of G such that 1 < H < 6. Which one of the following options is correct?Algebraic Structures · MCQ · 2 marks
  5. FN · Q46Let G = (V, E) be an undirected unweighted connected graph. The diameter of G is defined as diam (G) = u,v V \ the length of shortest path between u and v\ Let…Graph Theory · MCQ · 2 marks
  6. FN · Q53A relation R is said to be circular if aRb and bRc together imply cRa. Which of the following options is/are correct?Sets, Relations, Functions, Partial Orders, Lattices · MSQ · 2 marks
  7. AN · Q21Consider the following sets, where n 2: S 1 : Set of all n n matrices with entries from the set \ a, b, c\ S 2 : Set of all functions from the set \ 0, 1, 2, .…Sets, Relations, Functions, Partial Orders, Lattices · MSQ · 1 mark
  8. AN · Q25Choose the correct choice(s) regarding the following propositional logic assertion S: S : ((P Q) R) ((P Q) (Q R))Propositional and First-Order Quantifier Logic · MSQ · 1 mark
  9. AN · Q60Let S be a set consisting of 10 elements. The number of tuples of the form (A, B) such that A and B are subsets of S and A B is .Combinatorics · NAT · 2 marks
2020 5 questions · 8 marks
  1. FN · Q27Let R be the set of all binary relations on the set \ 1, 2, 3\ . Suppose a relation is chosen from R at random. The probability that the chosen relation is ref…Sets, Relations, Functions, Partial Orders, Lattices · NAT · 1 mark
  2. FN · Q28Let G be a group of 35 elements. Then the largest possible size of a subgroup of G other than G itself is .Algebraic Structures · NAT · 1 mark
  3. FN · Q49Which one of the following predicate formulae is NOT logically valid? Note that W is a predicate formula without any free occurrence of x .Propositional and First-Order Quantifier Logic · MCQ · 2 marks
  4. FN · Q52The number of permutations of the characters in LILAC so that no character appears in its original position, if the two L's are indistinguishable, is .Combinatorics · NAT · 2 marks
  5. FN · Q62Graph G is obtained by adding vertex s to K 3, 4 and making s adjacent to every vertex of K 3, 4 . The minimum number of colours required to edge-colour G is .Advanced Graph Bounds · NAT · 2 marks
2019 5 questions · 6 marks
  1. FN · Q15Let U = \ 1, 2, ..., n\ and A = \ (x, X), x X and X U\ . Consider the following two statements on A . I. A = n.2 n - 1 II. A = k=1 n k n k Which of the followi…Combinatorics · MCQ · 1 mark
  2. FN · Q20Let G be an arbitrary group. Consider the following relations on G : R 1: a, b G, aR 1b , if and only if g G such that a = g -1 bg R 2: a, b G, aR 2b , if and…Algebraic Structures · MCQ · 1 mark
  3. FN · Q22Let G be an undirected complete graph on n vertices, where n > 2 . Then, the number of different Hamiltonian cycles in G is equal toGraph Theory · MCQ · 1 mark
  4. FN · Q31The value of 3 51 5 is .Algebraic Structures · NAT · 1 mark
  5. FN · Q45Consider the first order predicate formula: x[( z \; z x ((z = x) (z = 1))) w (w > x) ( z \; z w ((w = z) (z = 1)))] Here ‘ a b ’ denotes that ‘ a divides b ’,…Propositional and First-Order Quantifier Logic · MCQ · 2 marks
2018 6 questions · 9 marks
  1. FN · Q11Which one of the following is a closed form expression for the generating function of the sequence \ a n\ , where a n = 2n + 3 for all n = 0, 1, 2, ?Recurrence Relations and Generating Functions · MCQ · 1 mark
  2. FN · Q28The chromatic number of the following graph is .Advanced Graph Bounds · NAT · 1 mark
  3. FN · Q29Let G be a finite group on 84 elements. The size of a largest possible proper subgroup of G is .Algebraic Structures · NAT · 1 mark
  4. FN · Q37Let N be the set of natural numbers. Consider the following sets. P: Set of Rational numbers (positive and negative) Q: Set of functions from \ 0, 1\ to N R: S…Sets, Relations, Functions, Partial Orders, Lattices · MCQ · 2 marks
  5. FN · Q38Consider the first-order logic sentence s t u v w x y (s, t, u, v, w, x, y) where (s, t, u, v, w, x, y) is a quantifier-free first-order logic formula using on…Propositional and First-Order Quantifier Logic · MCQ · 2 marks
  6. FN · Q53Let G be a graph with 100! vertices, with each vertex labelled by a distinct permutation of the numbers 1,2, ..., 100. There is an edge between vertices u and…Graph Theory · NAT · 2 marks
2017 9 questions · 12 marks
  1. FN · Q1The statement ( p) ( q) is logically equivalent to which of the statements below? I. p q II. q p III. ( q) p IV. ( p) qPropositional and First-Order Quantifier Logic · MCQ · 1 mark
  2. FN · Q2Consider the first-order logic sentence F : x( y R(x, y)). Assuming non-empty logical domains, which of the sentences below are implied by F? I. y( x R(x, y))…Propositional and First-Order Quantifier Logic · MCQ · 1 mark
  3. FN · Q20Let T be a tree with 10 vertices. The sum of the degrees of all the vertices in T is .Graph Theory · NAT · 1 mark
  4. FN · Q29Let p, q and r be propositions and the expression (p q) r be a contradiction. Then, the expression (r p) q isPropositional and First-Order Quantifier Logic · MCQ · 2 marks
  5. FN · Q47The number of integers between 1 and 500 (both inclusive) that are divisible by 3 or 5 or 7 is .Combinatorics · NAT · 2 marks
  6. AN · Q11Let p, q, r denote the statements " It is raining ", " It is cold ", and " It is pleasant ", respectively. Then the statement " It is not raining and it is ple…Propositional and First-Order Quantifier Logic · MCQ · 1 mark
  7. AN · Q21Consider the set X = a, b, c, d, e under the partial ordering R = (a, a), (a, b), (a, c), (a, d), (a, e), (b, b), (b, c), (b, e), (c, c), (c, e), (d, d), (d, e…Sets, Relations, Functions, Partial Orders, Lattices · NAT · 1 mark
  8. AN · Q23G is an undirected graph with n vertices and 25 edges such that each vertex of G has degree at least 3. Then the maximum possible value of n is .Graph Theory · NAT · 1 mark
  9. AN · Q47If the ordinary generating function of a sequence \ a n\ n=0 is 1 + z (1 - z) 3 , then a 3 - a 0 is equal toRecurrence Relations and Generating Functions · NAT · 2 marks