DM · previous year questions

All PYQs: Discrete Mathematics

99 real GATE CSE questions from 2012 to 2025, with the official answer key and a worked solution for each. Filter by year, topic, type, marks or keyword.

Questions belong to the GATE organising institutes; this copy is for personal study. Coverage varies by year: questions that need a figure I could not read, or whose answer I could not verify, were left out.

Showing 99 of 99 questions · 0 correct of 0 attempted · marks 0 / 150

GATE 2025 CS2 · Q15MCQ1 markPropositional & First-Order Logic
Let P(x) be an arbitrary predicate over the domain of natural numbers. Which ONE of the following statements is TRUE?
GATE 2025 CS1 · Q17MCQ1 markSets, Relations & Functions
g(·) 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 onto (surjective) functions, which ONE of the following is TRUE about the function g(·)?
GATE 2025 CS1 · Q30NAT1 markCombinatorics & Recurrences
Let 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 consecutive symbols, that is, "aa", "bb" or "cc". The number of such strings of length 5 that are possible is ______.
GATE 2025 CS2 · Q42MSQ2 marksSets, Relations & Functions
Let 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), where 0 ≤ 1. Which of the following statement(s) is/are TRUE?

One or more options may be correct. Select all that apply, then submit.

GATE 2025 CS1 · Q48MSQ2 marksPropositional & First-Order Logic
Which of the following predicate logic formulae/formula is/are CORRECT representation(s) of the statement: "Everyone has exactly one mother"? The meanings of the predicates used are: mother(y, x): y is the mother of x; noteq(x, y): x and y are not equal.

One or more options may be correct. Select all that apply, then submit.

GATE 2025 CS1 · Q49MSQ2 marksGroups & Algebraic Structures
A = {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₁, f₂ ∈ F, we define (f₁ ⊙ f₂)(n) = f₁(n) + f₂(n) for every number n in A. Which of the following is/are CORRECT about the mathematical structure (F, ⊙)?

One or more options may be correct. Select all that apply, then submit.

GATE 2024 CS2 · Q12MCQ1 markPropositional & First-Order Logic
Let 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 given when student scores more than 50% marks." Which one of the following is the CORRECT representation of the above statement in propositional logic?
GATE 2024 CS2 · Q15MCQ1 markCombinatorics & Recurrences
Let 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 TRUE?
GATE 2024 CS2 · Q17MCQ1 markGraph Theory
Let 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?
GATE 2024 CS1 · Q32NAT1 markSets, Relations & Functions
Let 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 values of |A| is ______.
GATE 2024 CS2 · Q34NAT1 markSets, Relations & Functions
Let 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 {1, 2, 3, 4} that contain P is ______.
GATE 2024 CS1 · Q34NAT1 markGraph Theory
The number of spanning trees in a complete graph of 4 vertices labelled A, B, C, and D is ______.
GATE 2024 CS1 · Q51MSQ2 marksGraph Theory
The 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 number k. Which of the following statements is/are always TRUE?

One or more options may be correct. Select all that apply, then submit.

GATE 2024 CS2 · Q51MSQ2 marksGraph Theory
Let 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 following statements is/are TRUE for every such graph G?

One or more options may be correct. Select all that apply, then submit.

GATE 2024 CS1 · Q52MSQ2 marksGroups & Algebraic Structures
Consider the operators ◊ and □ defined by a ◊ b = a + 2b and a □ b = ab, for positive integers. Which of the following statements is/are TRUE?

One or more options may be correct. Select all that apply, then submit.

GATE 2024 CS2 · Q63NAT2 marksGroups & Algebraic Structures
Let Zₙ 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₂ × Z₃ × Z₄ that are their own inverses is ______.
GATE 2023 · Q15MCQ1 markCombinatorics & Recurrences
The Lucas sequence Lₙ is defined by the recurrence relation: Lₙ = Lₙ₋₁ + Lₙ₋₂, for n ≥ 3, with L₁ = 1 and L₂ = 3. Which one of the options given is TRUE?
GATE 2023 · Q26MSQ1 markPropositional & First-Order Logic
Geetha 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 integers. Which of the following (one or more) option(s) would imply Geetha's conjecture?

One or more options may be correct. Select all that apply, then submit.

GATE 2023 · Q48MCQ2 marksCombinatorics & Recurrences
Let 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 and A ∩ B = ∅. We say that a permutation of U separates A from B if one of the following is true: all members of A appear in the permutation before any of the members of B; or all members of B appear in the permutation before any of the members of A. How many permutations of U separate A from B?
GATE 2023 · Q49MSQ2 marksSets, Relations & Functions
Let f : A → B be an onto (or surjective) function, where A and B are nonempty sets. Define an equivalence relation ∼ on the set A as a₁ ∼ a₂ if f(a₁) = f(a₂), where a₁, a₂ ∈ A. Let E = {[x] : x ∈ A} be the set of all the equivalence classes under ∼. Define a new mapping F : E → B as F([x]) = f(x), for all the equivalence classes [x] in E. Which of the following statements is/are TRUE?

One or more options may be correct. Select all that apply, then submit.

GATE 2023 · Q51MSQ2 marksGroups & Algebraic Structures
Let X be a set and 2X denote the powerset of X. Define a binary operation Δ on 2X as follows: A Δ B = (A − B) ∪ (B − A). Let H = (2X, Δ). Which of the following statements about H is/are correct?

One or more options may be correct. Select all that apply, then submit.

GATE 2022 · Q27MSQ1 markGroups & Algebraic Structures
Which of the following statements is/are TRUE for a group G?

One or more options may be correct. Select all that apply, then submit.

GATE 2022 · Q30NAT1 markGraph Theory
Consider a simple undirected graph of 10 vertices. If the graph is disconnected, then the maximum number of edges it can have is ______.
GATE 2022 · Q32NAT1 markCombinatorics & Recurrences
The number of arrangements of six identical balls in three identical bins is ______.
GATE 2022 · Q36MCQ2 marksCombinatorics & Recurrences
Which one of the following is the closed form for the generating function of the sequence {aₙ}ₙ≥0 defined below? aₙ = n + 1 if n is odd, and aₙ = 1 otherwise.
GATE 2022 · Q37MCQ2 marksGraph Theory
Consider 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 is given by the trace of
GATE 2022 · Q51MSQ2 marksCombinatorics & Recurrences
Consider 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?

One or more options may be correct. Select all that apply, then submit.

GATE 2022 · Q52MSQ2 marksGraph Theory
Which of the properties hold for the adjacency matrix A of a simple undirected unweighted graph having n vertices?

One or more options may be correct. Select all that apply, then submit.

GATE 2021 Set 1 · Q7MCQ1 markPropositional & First-Order Logic
Let p and q be two propositions. Consider the following two formulae in propositional logic. S₁: (¬p ∧ (p ∨ q)) → q S₂: q → (¬p ∧ (p ∨ q)). Which one of the following choices is correct?
GATE 2021 Set 2 · Q11MSQ1 markSets, Relations & Functions
Consider the following sets, where n ≥ 2: S₁: Set of all n × n matrices with entries from the set {a, b, c}. S₂: Set of all functions from the set {0, 1, 2, …, n² − 1} to the set {0, 1, 2}. Which of the following choice(s) is/are correct?

One or more options may be correct. Select all that apply, then submit.

GATE 2021 Set 2 · Q15MSQ1 markPropositional & First-Order Logic
Choose the correct choice(s) regarding the following propositional logic assertion S: S : ((P ∧ Q) → R) → ((P ∧ Q) → (Q → R))

One or more options may be correct. Select all that apply, then submit.

GATE 2021 Set 1 · Q16NAT1 markGraph Theory
In an undirected connected planar graph G, there are eight vertices and five faces. The number of edges in G is ______.
GATE 2021 Set 1 · Q19NAT1 markCombinatorics & Recurrences
There 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 computer gets the toughest job and the slowest computer gets the easiest job; every computer gets at least one job. The number of ways in which this can be done is ______.
GATE 2021 Set 1 · Q34MCQ2 marksGroups & Algebraic Structures
Let 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?
GATE 2021 Set 1 · Q43MSQ2 marksSets, Relations & Functions
A relation R is said to be circular if aRb and bRc together imply cRa. Which of the following options is/are correct?

One or more options may be correct. Select all that apply, then submit.

GATE 2021 Set 2 · Q50NAT2 marksSets, Relations & Functions
Let 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 ______.
GATE 2020 · Q17NAT1 markSets, Relations & Functions
Let 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 reflexive (round off to 3 decimal places) is ______.
GATE 2020 · Q18NAT1 markGroups & Algebraic Structures
Let G be a group of 35 elements. Then the largest possible size of a subgroup of G other than G itself is ______.
GATE 2020 · Q39MCQ2 marksPropositional & First-Order Logic
Which one of the following predicate formulae is NOT logically valid? Note that W is a predicate formula without any free occurrence of x.
GATE 2020 · Q42NAT2 marksCombinatorics & Recurrences
The 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 ______.
GATE 2020 · Q52NAT2 marksGraph Theory
Graph G is obtained by adding vertex s to K₃,₄ and making s adjacent to every vertex of K₃,₄. The minimum number of colours required to edge-colour G is ______.
GATE 2019 Set 2 · Q21NAT1 markGroups & Algebraic Structures
The value of 3⁵¹ mod 5 is ______.
GATE 2019 Set 2 · Q34MCQ2 marksSets, Relations & Functions
Consider the following sets: S1. Set of all recursively enumerable languages over the alphabet {0, 1}. S2. Set of all syntactically valid C programs. S3. Set of all languages over the alphabet {0, 1}. S4. Set of all non-regular languages over the alphabet {0, 1}. Which of the above sets are uncountable?
GATE 2019 Set 2 · Q35MCQ2 marksPropositional & First-Order Logic
Consider 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", where a and b are integers. Consider the following sets: S1. {1, 2, 3, …, 100}; S2. Set of all positive integers; S3. Set of all integers. Which of the above sets satisfy φ?
GATE 2018 · Q1MCQ1 markCombinatorics & Recurrences
Which one of the following is a closed form expression for the generating function of the sequence {aₙ}, where aₙ = 2n + 3 for all n = 0, 1, 2, …?
GATE 2018 · Q19NAT1 markGroups & Algebraic Structures
Let G be a finite group on 84 elements. The size of a largest possible proper subgroup of G is ______.
GATE 2018 · Q27MCQ2 marksSets, Relations & Functions
Let 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: Set of functions from N to {0, 1}. S: Set of finite subsets of N. Which of the sets above are countable?
GATE 2018 · Q28MCQ2 marksPropositional & First-Order Logic
Consider 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 only predicate symbols, and possibly equality, but no function symbols. Suppose φ has a model with a universe containing 7 elements. Which one of the following statements is necessarily true?
GATE 2018 · Q43NAT2 marksGraph Theory
Let 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 v if and only if the label of u can be obtained by swapping two adjacent numbers in the label of v. Let y denote the degree of a vertex in G, and z denote the number of connected components in G. Then, y + 10z = ______.
GATE 2017 Set 1 · Q1MCQ1 markPropositional & First-Order Logic
The statement (¬p) ⇒ (¬q) is logically equivalent to which of the statements below? I. p ⇒ q II. q ⇒ p III. (¬q) ∨ p IV. (¬p) ∨ q
GATE 2017 Set 1 · Q2MCQ1 markPropositional & First-Order Logic
Consider 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)) II. ∃y (∀x R(x, y)) III. ∀y (∃x R(x, y)) IV. ¬∃x (∀y ¬R(x, y))
GATE 2017 Set 2 · Q11MCQ1 markPropositional & First-Order Logic
Let 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 pleasant, and it is not pleasant only if it is raining and it is cold" is represented by
GATE 2017 Set 1 · Q20NAT1 markGraph Theory
Let T be a tree with 10 vertices. The sum of the degrees of all the vertices in T is ______.
GATE 2017 Set 2 · Q21NAT1 markSets, Relations & Functions
Consider 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), (e,e)}. The Hasse diagram of the partial order (X, R) is a chain a < b < c < e on one side and a < d < e on the other. The minimum number of ordered pairs that need to be added to R to make (X, R) a lattice is ______.
GATE 2017 Set 2 · Q23NAT1 markGraph Theory
G 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 ______.
GATE 2017 Set 1 · Q29MCQ2 marksPropositional & First-Order Logic
Let p, q, and r be propositions and the expression (p → q) → r be a contradiction. Then, the expression (r → p) → q is
GATE 2017 Set 1 · Q47NAT2 marksCombinatorics & Recurrences
The number of integers between 1 and 500 (both inclusive) that are divisible by 3 or 5 or 7 is ______.
GATE 2017 Set 2 · Q47NAT2 marksCombinatorics & Recurrences
If the ordinary generating function of a sequence {aₙ} (n ≥ 0) is (1 + z)/(1 − z)³, then a₃ − a₀ is equal to ______.
GATE 2016 Set 1 · Q1NAT1 markPropositional & First-Order Logic
Let p, q, r, s represent the following propositions. p: x ∈ {8, 9, 10, 11, 12}; q: x is a composite number; r: x is a perfect square; s: x is a prime number. The integer x ≥ 2 which satisfies ¬((p ⇒ q) ∧ (¬r ∨ ¬s)) is ______.
GATE 2016 Set 2 · Q1NAT1 markPropositional & First-Order Logic
Consider the following expressions: (i) false (ii) Q (iii) true (iv) P ∨ Q (v) ¬Q ∨ P. The number of expressions given above that are logically implied by P ∧ (P ⇒ Q) is ______.
GATE 2016 Set 1 · Q2MCQ1 markCombinatorics & Recurrences
Let aₙ be the number of n-bit strings that do NOT contain two consecutive 1s. Which one of the following is the recurrence relation for aₙ?
GATE 2016 Set 2 · Q3NAT1 markGraph Theory
The minimum number of colours that is sufficient to vertex-colour any planar graph is ______.
GATE 2016 Set 2 · Q26MCQ2 marksSets, Relations & Functions
A binary relation R on N × N is defined as follows: (a, b) R (c, d) if a ≤ c or b ≤ d. Consider the following propositions: P: R is reflexive. Q: R is transitive. Which one of the following statements is TRUE?
GATE 2016 Set 1 · Q26NAT2 marksCombinatorics & Recurrences
The coefficient of x¹² in (x³ + x⁴ + x⁵ + x⁶ + …)³ is ______.
GATE 2016 Set 2 · Q27MCQ2 marksPropositional & First-Order Logic
Which one of the following well-formed formulae in predicate calculus is NOT valid?
GATE 2016 Set 1 · Q28NAT2 marksSets, Relations & Functions
A function f : N⁺ → N⁺, defined on the set of positive integers N⁺, satisfies the following properties: f(n) = f(n/2) if n is even; f(n) = f(n + 5) if n is odd. Let R = {i | ∃j : f(j) = i} be the set of distinct values that f takes. The maximum possible size of R is ______.
GATE 2016 Set 2 · Q28MCQ2 marksGraph Theory
Consider a set U of 23 different compounds in a Chemistry lab. There is a subset S of U of 9 compounds, each of which reacts with exactly 3 compounds of U. Consider the following statements: I. Each compound in U \ S reacts with an odd number of compounds. II. At least one compound in U \ S reacts with an odd number of compounds. III. Each compound in U \ S reacts with an even number of compounds. Which one of the above statements is ALWAYS TRUE?
GATE 2016 Set 2 · Q29NAT2 marksGroups & Algebraic Structures
The value of the expression 13⁹⁹ (mod 17), in the range 0 to 16, is ______.
GATE 2014 Set 1 · Q1MCQ1 markPropositional & First-Order Logic
Consider the statement "Not all that glitters is gold". Predicate glitters(x) is true if x glitters and predicate gold(x) is true if x is gold. Which one of the following logical formulae represents the above statement?
GATE 2014 Set 3 · Q1MCQ1 markPropositional & First-Order Logic
Consider the following statements: P: Good mobile phones are not cheap. Q: Cheap mobile phones are not good. L: P implies Q. M: Q implies P. N: P is equivalent to Q. Which one of the following about L, M, and N is CORRECT?
GATE 2014 Set 3 · Q2MCQ1 markSets, Relations & Functions
Let X and Y be finite sets and f : X → Y be a function. Which one of the following statements is TRUE?
GATE 2014 Set 2 · Q3NAT1 markGraph Theory
The maximum number of edges in a bipartite graph on 12 vertices is ______.
GATE 2014 Set 3 · Q3NAT1 markGroups & Algebraic Structures
Let G be a group with 15 elements. Let L be a subgroup of G. It is known that L ≠ G and that the size of L is at least 4. The size of L is ______.
GATE 2014 Set 2 · Q6MCQ1 markPropositional & First-Order Logic
The dual of a Boolean function F(x₁, x₂, …, xₙ, +, ·, '), written as Fᴰ, is the same expression as that of F with + and · swapped. F is said to be self-dual if F = Fᴰ. The number of self-dual functions with n Boolean variables is
GATE 2014 Set 3 · Q16MCQ1 markSets, Relations & Functions
Let Σ be a finite non-empty alphabet and let 2Σ* be the power set of Σ*. Which one of the following is TRUE?
GATE 2014 Set 2 · Q48NAT2 marksCombinatorics & Recurrences
The probability that a given positive integer lying between 1 and 100 (both inclusive) is NOT divisible by 2, 3 or 5 is ______.
GATE 2014 Set 3 · Q49MCQ2 marksSets, Relations & Functions
Consider the set of all functions f : {0, 1, …, 2014} → {0, 1, …, 2014} such that f(f(i)) = i, for all 0 ≤ i ≤ 2014. Consider the following statements. P. For each such function it must be the case that for every i, f(i) = i. Q. For each such function it must be the case that for some i, f(i) = i. R. Each such function must be onto. Which one of the following is CORRECT?
GATE 2014 Set 2 · Q49NAT2 marksCombinatorics & Recurrences
The number of distinct positive integral factors of 2014 is ______.
GATE 2014 Set 1 · Q50NAT2 marksSets, Relations & Functions
Let S denote the set of all functions f : {0, 1}⁴ → {0, 1}. Denote by N the number of functions from S to the set {0, 1}. The value of log₂ log₂ N is ______.
GATE 2014 Set 2 · Q50MCQ2 marksSets, Relations & Functions
Consider the following relation on subsets of the set S of integers between 1 and 2014. For two distinct subsets U and V of S we say U < V if the minimum element in the symmetric difference of the two sets is in U. Consider the following two statements: S1: There is a subset of S that is larger than every other subset. S2: There is a subset of S that is smaller than every other subset. Which one of the following is CORRECT?
GATE 2014 Set 3 · Q50NAT2 marksGroups & Algebraic Structures
There are two elements x, y in a group (G, ∗) such that every element in the group can be written as a product of some number of x's and y's in some order. It is known that x ∗ x = y ∗ y = x ∗ y ∗ x ∗ y = y ∗ x ∗ y ∗ x = e, where e is the identity element. The maximum number of elements in such a group is ______.
GATE 2014 Set 1 · Q51NAT2 marksGraph Theory
Consider an undirected graph G where self-loops are not allowed. The vertex set of G is {(i, j) : 1 ≤ i ≤ 12, 1 ≤ j ≤ 12}. There is an edge between (a, b) and (c, d) if |a − c| ≤ 1 and |b − d| ≤ 1. The number of edges in this graph is ______.
GATE 2014 Set 2 · Q51NAT2 marksGraph Theory
A cycle on n vertices is isomorphic to its complement. The value of n is ______.
GATE 2014 Set 3 · Q51MCQ2 marksGraph Theory
If G is a forest with n vertices and k connected components, how many edges does G have?
GATE 2014 Set 1 · Q52MCQ2 marksGraph Theory
An ordered n-tuple (d₁, d₂, …, dₙ) with d₁ ≥ d₂ ≥ … ≥ dₙ is called graphic if there exists a simple undirected graph with n vertices having degrees d₁, d₂, …, dₙ respectively. Which of the following 6-tuples is NOT graphic?
GATE 2014 Set 3 · Q52MCQ2 marksGraph Theory
Let δ denote the minimum degree of a vertex in a graph. For all planar graphs on n vertices with δ ≥ 3, which one of the following is TRUE?
GATE 2014 Set 1 · Q53MCQ2 marksPropositional & First-Order Logic
Which one of the following propositional logic formulas is TRUE when exactly two of p, q, and r are TRUE?
GATE 2014 Set 3 · Q53MCQ2 marksPropositional & First-Order Logic
The CORRECT formula for the sentence, "not all rainy days are cold" is
GATE 2014 Set 2 · Q53MCQ2 marksPropositional & First-Order Logic
Which one of the following Boolean expressions is NOT a tautology?
GATE 2013 Code A · Q1MCQ1 markGroups & Algebraic Structures
A binary operation ⊕ on a set of integers is defined as x ⊕ y = x² + y². Which one of the following statements is TRUE about ⊕?
GATE 2013 Code A · Q24MCQ1 markGraph Theory
Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is 1/2. What is the expected number of unordered cycles of length three?
GATE 2013 Code A · Q25MCQ1 markGraph Theory
Which of the following statements is/are TRUE for undirected graphs? P: Number of odd degree vertices is even. Q: Sum of degrees of all vertices is even.
GATE 2013 Code A · Q26MCQ2 marksGraph Theory
The line graph L(G) of a simple graph G is defined as follows: there is exactly one vertex v(e) in L(G) for each edge e in G; for any two edges e and e' in G, L(G) has an edge between v(e) and v(e') if and only if e and e' are incident with the same vertex in G. Which of the following statements is/are TRUE? (P) The line graph of a cycle is a cycle. (Q) The line graph of a clique is a clique. (R) The line graph of a planar graph is planar. (S) The line graph of a tree is a tree.
GATE 2013 Code A · Q27MCQ2 marksPropositional & First-Order Logic
What is the logical translation of the following statement? "None of my friends are perfect."
GATE 2012 Code A · Q1MCQ1 markPropositional & First-Order Logic
Consider the following logical inferences. I₁: If it rains then the cricket match will not be played. The cricket match was played. Inference: There was no rain. I₂: If it rains then the cricket match will not be played. It did not rain. Inference: The cricket match was played. Which of the following is TRUE?
GATE 2012 Code A · Q13MCQ1 markPropositional & First-Order Logic
What is the correct translation of the following statement into mathematical logic? "Some real numbers are rational"
GATE 2012 Code A · Q16MCQ1 markCombinatorics & Recurrences
The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with n discs is
GATE 2012 Code A · Q17MCQ1 markGraph Theory
Let G be a simple undirected planar graph on 10 vertices 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
GATE 2012 Code A · Q37MCQ2 marksSets, Relations & Functions
How many onto (or surjective) functions are there from an n-element (n ≥ 2) set to a 2-element set?