Discrete Mathematics — GATE Previous Year Questions

Let \(R\) and \(S\) be any two equivalence relations on a non-empty set \(A\). Which one of the following statements is TRUE?

What is the chromatic number of an \(n\)-vertex simple connected graph which does not contain any odd-length cycle? Assume \(n \geq 2\).

If \(G\) is a forest with \(n\) vertices and \(k\) connected components, how many edges does \(G\) have?

The maximum number of edges in a bipartite graph on 12 vertices is ______.

Which one of the following propositional logic formulas is TRUE when exactly two of \(p\), \(q\) and \(r\) are TRUE?

In a connected graph, a bridge is an edge whose removal disconnects the graph. Which one of the following statements is TRUE?

The cardinality of the power set of \(\{0, 1, 2, \ldots, 10\}\) is ______.

Let \(R\) be the relation on the set of positive integers such that \(aRb\) if and only if \(a\) and \(b\) are distinct and have a common divisor other than 1. Which one of the following statements about \(R\) is TRUE?

The coefficient of \(x^{12}\) in \((x^{3} + x^{4} + x^{5} + x^{6} + \cdots)^{3}\) is ______.

Consider the following expressions:

(i) false
(ii) \(Q\)
(iii) true
(iv) \(P \vee Q\)
(v) \(\neg Q \vee P\)

The number of expressions given above that are logically implied by \(P \wedge (P \Rightarrow Q)\) is ______.

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

Let \(\mathbb{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 \(\mathbb{N}\)
R: Set of functions from \(\mathbb{N}\) to \(\{0, 1\}\)
S: Set of finite subsets of \(\mathbb{N}\)

Which of the sets above are countable?