# Discrete Mathematics

 Question 1
Let $G$ be a simple, finite, undirected graph with vertex set $\{v_1,...,v_n\}$. Let $\Delta (G)$ denote the maximum degree of $G$ and let $N=\{1,2,...\}$ denote the set of all possible colors. Color the vertices of $G$ using the following greedy strategy: for $i = 1,...,n$
$color(v_i)\leftarrow min\{ j \in N: \text{ no neighbour of } v_i \text{ is colored } j\}$
Which of the following statements is/are TRUE?
 A This procedure results in a proper vertex coloring of $G$. B The number of colors used is at most $\Delta (G)+1$. C The number of colors used is at most$\Delta (G)$. D The number of colors used is equal to the chromatic number of $G$.
GATE CSE 2023      Graph Theory
Question 1 Explanation:
 Question 2
Consider a random experiment where two fair coins are tossed. Let A be the event that denotes HEAD on both the throws, B be the event that denotes HEAD on the first throw, and C be the event that denotes HEAD on the second throw. Which of the following statements is/are TRUE?
 A A and B are independent. B A and C are independent. C B and C are independent. D Prob(B|C) = Prob(B)
GATE CSE 2023      Probability Theory
Question 2 Explanation:
 Question 3
Let $X$ be a set and $2^X$ denote the powerset of $X$.
Define a binary operation $\Delta$ on $2^X$ as follows:
$A \Delta B=(A-B) \cup (B-A)$
Let $H=(2^X,\Delta )$. Which of the following statements about $H$ is/are correct?
 A $H$ is a group. B Every element in $H$ has an inverse, but $H$ is NOT a group. C For every $A \in 2^X$, the inverse of $A$ is the complement of $A$. D For every $A \in 2^X$, the inverse of $A$ is $A$.
GATE CSE 2023      Set Theory
Question 3 Explanation:
 Question 4
Let $f:A\rightarrow B$ be an onto (or surjective) function, where $A$ and $B$ are nonempty sets. Define an equivalence relation $\sim$ on the set $A$ as
$a_1\sim a_2 \text{ if } f(a_1)=f(a_2),$
where $a_1, a_2 \in A$ . Let $\varepsilon =\{[x]:x \in A\}$ be the set of all the equivalence classes under $\sim$. Define a new mapping $F: \varepsilon \rightarrow B$ as
$F([x]) = f(x),$ for all the equivalence classes $[x]$ in $\varepsilon$
Which of the following statements is/are TRUE?
 A F is NOT well-defined. B F is an onto (or surjective) function. C F is a one-to-one (or injective) function. D F is a bijective function.
GATE CSE 2023      Function
Question 4 Explanation:
 Question 5
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\cap B=\phi$. 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.
- All members of B appear in the permutation before any of the members of A.

How many permutations of U separate A from B?
 A $n!$ B $\binom{n}{2k} (n-2k)!$ C $\binom{n}{2k} (n-2k)! (k!)^2$ D $2 \binom{n}{2k} (n-2k)! (k!)^2$
GATE CSE 2023      Combination
Question 5 Explanation:
 Question 6
Geetha has a conjecture about integers, which is of the form
$\forall x\left [P(x)\Rightarrow \exists yQ(x,y) \right ]$
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?
 A $\exists x\left [P(x)\wedge \forall yQ(x,y) \right ]$ B $\forall x \forall y Q(x,y)$ C $\exists y \forall x \left [P(x) \Rightarrow Q(x,y) \right ]$ D $\exists x \left [P(x) \wedge \exists y Q(x,y) \right ]$
GATE CSE 2023      Propositional Logic
Question 6 Explanation:
 Question 7
The Lucas sequence $L_n$ is defined by the recurrence relation:
$L_n=L_{n-1}+L_{n+2}, \; for \; n\geq 3,$
with $L_1=1 \; and \; L_2=3$
Which one of the options given is TRUE?
 A $L_n=\left ( \frac{1+\sqrt{5}}{2} \right )^n+\left ( \frac{1-\sqrt{5}}{2} \right )^n$ B $L_n=\left ( \frac{1+\sqrt{5}}{2} \right )^n - \left ( \frac{1-\sqrt{5}}{3} \right )^n$ C $L_n=\left ( \frac{1+\sqrt{5}}{2} \right )^n+\left ( \frac{1-\sqrt{5}}{3} \right )^n$ D $L_n=\left ( \frac{1+\sqrt{5}}{2} \right )^n- \left ( \frac{1-\sqrt{5}}{2} \right )^n$
GATE CSE 2023      Recurrence
Question 7 Explanation:
 Question 8
Which of the properties hold for the adjacency matrix $A$ of a simple undirected unweighted graph having $n$ vertices?
MSQ
 A The diagonal entries of $A^2$ are the degrees of the vertices of the graph. B If the graph is connected, then none of the entries of $A^{n-1}+I_n$can be zero. C If the sum of all the elements of $A$ is at most 2(n-1), then the graph must be acyclic. D If there is at least a 1 in each of A's rows and columns, then the graph must be connected.
GATE CSE 2022      Graph Theory
Question 8 Explanation:
 Question 9
Consider the following recurrence:
\begin{aligned} f(1)&=1; \\ f(2n)&=2f(n)-1, & \text{for }n \geq 1; \\ f(2n+1)&=2f(n)+1, & \text{for }n \geq 1. \end{aligned}
Then, which of the following statements is/are TRUE?
MSQ
 A $f(2^n-1)=2^n-1$ B $f(2^n)=1$ C $f(5 \dot 2^n)=2^{n+1}+1$ D $f(2^n+1)=2^n+1$
GATE CSE 2022      Recurrence
Question 9 Explanation:
 Question 10
The following simple undirected graph is referred to as the Peterson graph.

Which of the following statements is/are TRUE?
MSQ
 A The chromatic number of the graph is 3. B The graph has a Hamiltonian path. C The following graph is isomorphic to the Peterson graph. D The size of the largest independent set of the given graph is 3. (A subset of vertices of a graph form an independent set if no two vertices of the subset are adjacent.)
GATE CSE 2022      Graph Theory
Question 10 Explanation:

There are 10 questions to complete.