Discrete Mathematics is worth about 8 marks per GATE CS paper, or roughly 8% of the 100-mark paper. We counted every Discrete Maths question in all 23 official GATE CS papers from 2014 to 2026, and the subject averaged 8.3 marks, ranging from 3 to 15. The topic mix has shifted, though. Graph theory is now the largest topic, logic questions have become rarer, and since 2021 almost half of Discrete Maths marks come from multiple-select questions (MSQs), which have no negative marking but no partial credit either. This guide covers the official 2027 syllabus, the topic-by-topic numbers, five worked questions from past papers and a study order based on that data.
How we counted: we classified all 1,495 GATE CS questions from 2014 to 2026 (23 papers, each totalling exactly 100 marks) by subject and topic, using the official papers as reproduced on Success Tracker's GATE CS PYQ archive. A few questions sit on a subject boundary, for example a graph question that could be filed under Algorithms. In those cases we followed the question's main concept, so another analyst could reasonably count a mark or two differently in some papers. Confirm the syllabus itself on the official GATE 2027 syllabus page (IIT Madras).
GATE CS 2027 Discrete Mathematics Syllabus
Discrete Mathematics is part of Section 1 (Engineering Mathematics) of the official GATE 2027 CS syllabus. The official text lists:
- Logic: propositional and first-order logic
- Set theory and algebra: sets, relations, functions, partial orders and lattices; monoids, groups
- Graphs: connectivity, matching, colouring
- Combinatorics: counting, recurrence relations, generating functions
That is the complete list. Rings, fields, number theory and probability-style counting outside these headings are not named in the syllabus, so do not spend weeks on them. For the full CS syllabus across all ten sections, see our GATE CS syllabus page.
How Many Marks Does Discrete Maths Carry in GATE CS?
The official GATE 2027 question paper pattern gives Engineering Mathematics as a whole 13 marks. It does not split that between Discrete Maths, Linear Algebra, Calculus and Probability. The official pattern allots 13 marks to Engineering Mathematics; classified by topic, maths content averaged 16.4 marks per paper (12–25) in 2014–2026 — exactly 13 in only 3 of 23 papers — because many CS questions are built on discrete maths, such as counting arguments and graph properties. Discrete Maths alone averaged 8.3 marks, and Linear Algebra, Calculus and Probability together 8.1. Treat 13 as the official allocation and the figures below as our topic-based, unofficial count. This is what we found in each paper:
| Year | Marks per paper (set-wise) | % of the 100-mark paper | Questions |
|---|---|---|---|
| 2014 | 11 / 9 / 14 | 11% / 9% / 14% | 6 / 5 / 9 |
| 2015 | 7 / 10 / 5 | 7% / 10% / 5% | 5 / 7 / 4 |
| 2016 | 8 / 10 | 8% / 10% | 5 / 6 |
| 2017 | 7 / 5 | 7% / 5% | 5 / 4 |
| 2018 | 9 | 9% | 6 |
| 2019 | 10 | 10% | 7 |
| 2020 | 9 | 9% | 5 |
| 2021 | 9 / 4 | 9% / 4% | 6 / 3 |
| 2022 | 15 | 15% | 9 |
| 2023 | 13 | 13% | 8 |
| 2024 | 6 / 10 | 6% / 10% | 4 / 7 |
| 2025 | 7 / 3 | 7% / 3% | 5 / 2 |
| 2026 | 6 / 4 | 6% / 4% | 3 / 3 |
| Average (23 papers) | 8.3 | 8.3% (range 3–15%) | 5.4 |
What this means: the average is 8.3 marks, but the spread is wide. Two sets in the same year have differed by as much as 5 marks (2014, 2015, 2021). Since you cannot choose your set, prepare the whole syllabus and don't bet on a favourite topic. The 2025 and 2026 papers were on the low side (3 to 7 marks), so treat 6 to 10 marks as a realistic planning range, not a guarantee.
Topic-Wise Weightage: Where the Marks Actually Come From
We grouped the 124 Discrete Maths questions by syllabus heading. The average column covers all 23 papers:
| Topic | Questions | Total marks | Avg marks per paper (23 papers) | Last asked |
|---|---|---|---|---|
| Graph theory | 37 | 62 | 2.7 | 2026 |
| Sets, relations and functions | 22 | 33 | 1.4 | 2026 |
| Monoids and groups | 13 | 20 | 0.9 | 2025 |
| Propositional logic | 15 | 19 | 0.8 | 2024 |
| First-order (predicate) logic | 12 | 19 | 0.8 | 2026 |
| Counting (permutations, combinations, inclusion–exclusion) | 12 | 18 | 0.8 | 2025 |
| Recurrences and generating functions | 9 | 14 | 0.6 | 2024 |
| Partial orders and lattices | 4 | 6 | 0.3 | 2025 |
Three patterns stand out:
- Graph theory now gives the most marks. It has risen from about 2.2 to 3.4 marks per paper, and it was asked in both 2026 sets: vertex cover, 2-colourability and counting matchings in Set 1, and spanning trees of a complete graph in Set 2. It is the one Discrete Maths topic you cannot leave weak.
- Logic has shrunk, but it hasn't gone. Propositional and predicate logic together fell from about 2.3 to 0.8 marks per paper. Predicate logic still appeared in both 2025 sets and in 2026 Set 2, usually as a 1-mark "translate this English sentence" question, which is quick marks if you have practised it.
- Groups have grown. Group theory averaged about 1.1 marks per paper from 2021, mostly as 2-mark MSQs or numerical answers. The questions test definitions (closure, identity, inverse, associativity) on unfamiliar operations, so they reward precise thinking more than formulas.
Question Types: Why MSQs Matter in Discrete Maths
From 2021 to 2026, the 50 Discrete Maths questions split into 20 MSQs, 15 MCQs and 15 numerical answer type (NAT) questions. MSQs carried 35 of the 77 marks (45%). There were no MSQs in any paper from 2014 to 2020.
The official marking rules are on the GATE 2027 question paper pattern page. A wrong 1-mark MCQ costs 1/3 mark and a wrong 2-mark MCQ costs 2/3 mark. MSQs and NATs have no negative marking, and an MSQ gives no partial credit. For Discrete Maths, this means:
- You must check every option of an MSQ. Spotting one correct statement is not enough.
- Many Discrete Maths MSQs ask "which properties hold" (reflexive, transitive, a group, a lattice). Have a quick counterexample ready for each property.
- Counting and graph questions are often NAT. There is no penalty for a wrong answer, so always enter your best value.
Topic by Topic: What GATE Asks and How to Prepare
1. Graph Theory (connectivity, matching, colouring)
What gets asked: degree sums and the handshake lemma, paths and cycles, connectivity (cut vertices and edges), chromatic number and 2-colourability (bipartite graphs), matchings, vertex covers, spanning trees of complete graphs, and planarity. Recent questions mix definitions with counting, as in "how many matchings does a path on 8 vertices have?"
How to prepare: learn the standard results well enough to use them without thinking. Know the degree-sum formula, that a graph is bipartite exactly when it has no odd cycle, that Kn has nn−2 spanning trees (Cayley's formula), and Euler's formula for planar graphs. Then practise small cases by hand. Most graph NAT questions come down to spotting a recurrence or a pattern from n = 1, 2, 3.
Recent PYQs: vertex cover (2026, MSQ), 2-colourable graphs (2026, MSQ), spanning trees of Kn (2026).
2. Sets, Relations and Functions
What gets asked: properties of relations (reflexive, symmetric, antisymmetric, transitive), equivalence relations and the number of equivalence classes, injective, surjective and bijective functions, composition of functions, and counting relations or functions on finite sets.
How to prepare: for every property, keep one smallest counterexample in mind. For example, a relation that is symmetric but not transitive. For function questions, know exactly what composition tells you: if f∘g is injective then g must be injective, and if f∘g is surjective then f must be surjective, but nothing more follows for the other function. GATE tested this in 2025 Set 1, Q17: with f and f∘g both onto, g need not be one-to-one or onto.
Recent PYQs: relation on {1,…,10} (2026, MSQ), bijections between finite sets (2024, NAT).
3. Partial Orders and Lattices
What gets asked: Hasse diagrams, minimal and maximal elements, least upper and greatest lower bounds, whether a poset is a lattice, and counting linear extensions (topological orderings).
How to prepare: this topic is small (6 marks in 13 years), but it shows up inside group and relation questions too. Practise drawing the Hasse diagram first. Most errors come from skipping that step.
Recent PYQs: order on functions to {0,1} (2025, MSQ), linear extensions of a poset (2024, NAT).
4. Monoids and Groups
What gets asked: whether a set with an unusual operation forms a semigroup, monoid or group; identity and inverse elements; cyclic groups and generators; orders of elements; and products such as Z2 × Z3 × Z4.
How to prepare: check the axioms in a fixed order: closure, associativity, identity, inverses (and commutativity if the question asks about abelian groups). In product groups, work on each component separately and multiply the counts. Worked example 4 below shows this.
Recent PYQs: composition of functions as an operation (2025, MSQ), custom operators on integers (2024, MSQ), symmetric difference on a power set (2023, MSQ).
5. Propositional Logic
What gets asked: tautologies, logical equivalence, the contrapositive and converse, and turning English sentences into propositions.
How to prepare: rewrite every implication as ¬p ∨ q before comparing formulas. To test whether something is a tautology, look for an assignment that makes it false. Searching for a counterexample is faster than building a full truth table.
Recent PYQs: English to logic (2024), validity of an implication (2021, MSQ).
6. First-Order (Predicate) Logic
What gets asked: mostly translating English into quantified formulas, plus the order of quantifiers (∀x∃y versus ∃y∀x) and negating quantified statements.
How to prepare: learn the two standard patterns. "Every A is B" becomes ∀x (A(x) → B(x)), with an implication. "Some A is B" becomes ∃x (A(x) ∧ B(x)), with a conjunction. Most wrong options swap these, or swap the order of the quantifiers.
Recent PYQs: "knows" predicate (2026), English to predicate logic (2025, MSQ), quantifiers over naturals (2025).
7. Counting
What gets asked: permutations and combinations with restrictions, distributing identical or distinct objects into identical or distinct boxes, inclusion–exclusion, derangements and counting strings with constraints.
How to prepare: before counting anything, ask two questions. Are the objects identical or distinct? Are the boxes identical or distinct? Each of the four combinations has a different method, and GATE often tests the hardest one: identical objects into identical boxes, which means integer partitions (worked example 5).
Recent PYQs: ternary strings (2025, NAT), assigning jobs to computers (2021, NAT).
8. Recurrence Relations and Generating Functions
What gets asked: solving linear homogeneous recurrences, finding a closed form for a sequence's generating function, and recurrences hidden inside counting questions.
How to prepare: learn the characteristic-equation method, and always apply the initial conditions before deciding the growth rate. Worked example 3 is a GATE trap where the larger root drops out. For generating functions, know the standard pairs, such as 1/(1−x) and 1/(1−x)2, and how shifting and scaling change them.
Recent PYQs: T(n) = 5T(n−1) − 6T(n−2) (2024), Lucas sequence (2023), generating function closed form (2022).
Worked Examples from Official GATE CS Papers
Each answer below matches the official answer key, as reproduced on the linked question page.
Example 1: Predicate logic (GATE CS 2026 Set 2, Q11, 1 mark)
Question: M(x, y) means "x knows y". Express: "There is a person who does not know anyone else, but that person is known by everyone else."
Solution: call the special person y. "There is" gives ∃y. "Everyone else" means every x with x ≠ y, which gives ∀x ((x ≠ y) → …). For each such x, two things must hold: x knows y, and y does not know x. So the answer is (∃y)(∀x)((x ≠ y) → (M(x, y) ∧ ¬M(y, x))), option A. The wrong options change ∃y to ∀y or ∀x to ∃x. Check the quantifier order first. Practise this question.
Example 2: Matchings in a path (GATE CS 2026 Set 1, Q57, 2 marks, NAT)
Question: how many matchings does a path on 8 vertices have? Count the empty matching too.
Solution: let an be the number of matchings in a path on n vertices. The last edge is either unused, which leaves an−1 matchings, or used, which rules out the edge before it and leaves an−2. So an = an−1 + an−2, with a1 = 1 and a2 = 2. That gives 1, 2, 3, 5, 8, 13, 21, 34. This one question combines graph theory with recurrences, which is typical of recent papers. Practise this question.
Example 3: The recurrence trap (GATE CS 2024 Set 2, Q15, 1 mark)
Question: T(0) = 1, T(1) = 2 and T(n) = 5T(n−1) − 6T(n−2). What is the growth of T(n)?
Solution: the characteristic equation r² − 5r + 6 = 0 has roots 2 and 3, so T(n) = c12n + c23n. The initial conditions give c1 + c2 = 1 and 2c1 + 3c2 = 2, so c2 = 0 and c1 = 1. Therefore T(n) = 2n exactly, and the answer is Θ(2n), not Θ(3n). If you picked the larger root without solving for the constants, you lost 1/3 mark. Practise this question.
Example 4: Self-inverse elements (GATE CS 2024 Set 2, Q63, 2 marks, NAT)
Question: in Z2 × Z3 × Z4, with addition modulo n in each component, how many elements are their own inverse?
Solution: an element (a, b, c) is its own inverse when 2a ≡ 0 (mod 2), 2b ≡ 0 (mod 3) and 2c ≡ 0 (mod 4). The first holds for a ∈ {0, 1} (2 choices), the second only for b = 0 (1 choice), and the third for c ∈ {0, 2} (2 choices). So the answer is 2 × 1 × 2 = 4. Practise this question.
Example 5: Identical balls, identical bins (GATE CS 2022, Q32, 1 mark, NAT)
Question: how many ways are there to place six identical balls in three identical bins?
Solution: neither the balls nor the bins can be told apart, so this is the number of partitions of 6 into at most 3 parts: 6, 5+1, 4+2, 4+1+1, 3+3, 3+2+1, 2+2+2. That makes 7. Using stars and bars here (C(8,2) = 28) is the classic mistake, because stars and bars assumes the bins are distinct. Practise this question.
Study Order and Time Plan
Discrete Maths takes roughly 3 to 4 weeks at 2 hours a day for most aspirants. This order follows the data above: high-weightage topics first, and topics that later subjects depend on early.
- Logic (3–4 days): quick to finish, and you need it again in Theory of Computation and for reading the conditions in Databases questions.
- Sets, relations and functions (3–4 days): the base for posets, groups and Theory of Computation.
- Counting, recurrences and generating functions (5–6 days): also used in Algorithms (recurrences) and Probability.
- Graph theory (5–6 days): the highest-weightage topic now. Give it the most practice time.
- Posets, lattices and groups (3–4 days): smaller topics, but recent MSQs reward having the definitions exact.
- PYQ sweep (3–4 days): solve every Discrete Maths question from 2014 to 2026, set by set, from the full GATE CS PYQ archive. That's 124 questions, which takes about 10 to 12 hours.
If you are short on time, use the 4-month GATE CSE plan, which schedules Engineering Mathematics in the first month.
Best Books for GATE CS Discrete Mathematics
| Book | Use it for |
|---|---|
| Kenneth H. Rosen, Discrete Mathematics and Its Applications | The primary text for logic, sets, relations, functions, posets, graphs, counting, recurrences and generating functions. Its exercises are excellent practice. |
| Tremblay & Manohar, Discrete Mathematical Structures with Applications to Computer Science | Monoids and groups, where it goes deeper than Rosen. |
Read Rosen selectively against the syllabus list above. Number theory and cryptography chapters, for example, are outside the GATE syllabus. For other subjects, see our best books for GATE CSE 2027.
Free Video Lectures: Discrete Maths for GATE CS
Our Discrete Mathematics for GATE CS playlist on YouTube is taught by Jay Bansal (AIR 2, GATE CS 2019). It currently covers the combinatorics section of the syllabus:
- Counting: counting basics, permutations, combinations, inclusion–exclusion, derangements, pigeonhole principle and induction
- Recurrences: introduction, constructing recurrences, linear homogeneous recurrences, standard recurrences
- Generating functions: introduction, with more lectures being added
The full structured course, covering every subject with mock tests, is on the GATE CS course page.
Common Mistakes in GATE Discrete Maths
- Using the dominant root without the initial conditions in recurrence questions (Example 3).
- Using stars and bars for identical bins. Identical bins need integer partitions (Example 5).
- Mixing up ∧ and → under quantifiers. Use ∀ with →, and ∃ with ∧.
- Stopping after one correct MSQ option. MSQs give no partial credit, so check every option.
- Skipping groups because they look abstract. They averaged about 1.1 marks per paper from 2021, and the questions mostly test definitions.
Key Takeaways
- Discrete Maths averaged 8.3 marks per paper (8.3% of the paper) across 23 official GATE CS papers (2014–2026), with a range of 3 to 15.
- Graph theory is now the biggest topic, at about 3.4 marks per paper since 2021, up from 2.2.
- Logic fell from about 2.3 to 0.8 marks per paper, but still gives quick 1-mark questions.
- MSQs carried 45% of Discrete Maths marks from 2021 to 2026. Check every option.
- Prepare the whole official syllabus. Two sets in the same year have differed by up to 5 marks in this subject.
Frequently Asked Questions
How many marks does Discrete Mathematics carry in GATE CS?
The official pattern gives Engineering Mathematics as a whole 13 marks and does not give a separate figure for Discrete Maths. Counting by topic, which includes discrete-maths questions placed in the CS part of the paper, across all 23 official GATE CS papers from 2014 to 2026, Discrete Maths averaged 8.3 marks per paper, which is 8.3% of the 100-mark paper, with a range of 3 to 15.
Which Discrete Maths topic is most important for GATE CS 2027?
Graph theory. It has the most marks overall (62 marks across 23 papers) and has risen to about 3.4 marks per paper since 2021. After that come sets, relations and functions, and then groups, which have grown in recent papers.
Is Discrete Mathematics easy to score in GATE CS?
It is one of the more scoring subjects because the syllabus is short and the questions test standard results. Of the 124 questions, Success Tracker rates 31 as easy, 77 as medium and 16 as hard. The main risks are MSQs, which give no partial credit, and traps like the recurrence in Example 3.
Which book is best for Discrete Maths for GATE CS?
Kenneth Rosen's Discrete Mathematics and Its Applications covers almost the whole syllabus. Add Tremblay and Manohar for monoids and groups.
Where can I practise GATE CS Discrete Maths PYQs?
Every GATE CS question from 2014 to 2026 is free on Success Tracker's GATE CS PYQ archive, with the official answer and a worked solution. The questions linked in this guide are a good starting set.
Has the Discrete Maths syllabus changed for GATE 2027?
The Discrete Mathematics topics in the GATE 2027 CS syllabus are the same as in the GATE 2026 CS syllabus: logic, sets and algebra, graphs, and combinatorics.
Next in This Series
- DBMS for GATE CS 2027: syllabus, weightage and PYQs
- GATE CSE subject-wise weightage
- GATE CSE 2027 important topics
- GATE CSE previous year question papers
- GATE CS 2027 complete guide
Sources
- GATE 2027 CS Syllabus (PDF), IIT Madras: Section 1, Engineering Mathematics
- GATE 2027 Question Paper Pattern, IIT Madras: marks distribution and negative marking
- GATE 2026 CS Syllabus (PDF), IIT Guwahati
- GATE 2027 Information Brochure, IIT Madras: Section 7.3, Table 8 (Engineering Mathematics 13 marks in CS)
- Official GATE CS question papers and answer keys, IIT Madras download page
- Official GATE CS question papers and answer keys, 2014–2026 (23 papers), as reproduced on Success Tracker. Weightage figures are The ML Hub's own count, done on 25 October 2026.