# Discrete Mathematics

 Question 1
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 1 Explanation:
 Question 2
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 2 Explanation:
 Question 3
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 3 Explanation:
 Question 4
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
 A $A^3$ B $A^3$ divided by 2 C $A^3$ divided by 3 D $A^3$ divided by 6
GATE CSE 2022      Graph Theory
Question 4 Explanation:
 Question 5
Which one of the following is the closed form for the generating function of the sequence $\{a_n \}_{n \geq 0}$ defined below?
$a_n= \left \{ \begin{matrix} n+1, &n \text{ is odd} \\ 1,& \text{otherwise} \end{matrix} \right.$
 A $\frac{x(1+x^2)}{(1-x^2)^2}+\frac{1}{1-x}$ B $\frac{x(3-x^2)}{(1-x^2)^2}+\frac{1}{1-x}$ C $\frac{2x}{(1-x^2)^2}+\frac{1}{1-x}$ D $\frac{x}{(1-x^2)^2}+\frac{1}{1-x}$
GATE CSE 2022      Function
Question 5 Explanation:
 Question 6
The number of arrangements of six identical balls in three identical bins is ____.
 A 7 B 8 C 12 D 5
GATE CSE 2022      Probability Theory
Question 6 Explanation:
 Question 7
Consider a simple undirected graph of 10 vertices. If the graph is disconnected, then the maximum number of edges it can have is .
 A 72 B 36 C 16 D 48
GATE CSE 2022      Graph Theory
Question 7 Explanation:
 Question 8
Which of the following statements is/are TRUE for a group $G$?
MSQ
 A If for all $x,y \in G, (xy)^2=x^2y^2$, then $G$ is commutative. B If for all $x \in G, x^2=1$, then $G$ is commutative. Here, 1 is the identity element of $G$. C If the order of $G$ is 2 , then $G$ is commutative. D If $G$ is commutative, then a subgroup of $G$ need not be commutative.
GATE CSE 2022      Group Theory
Question 8 Explanation:
 Question 9
In a directed acyclic graph with a source vertex s, the quality-score of a directed path is defined to be the product of the weights of the edges on the path. Further, for a vertex v other than s, the quality-score of v is defined to be the maximum among the quality-scores of all the paths from s to v. The quality-score of s is assumed to be 1.

The sum of the quality-scores of all vertices on the graph shown above is ______
 A 929 B 254 C 639 D 879
GATE CSE 2021 SET-2      Graph Theory
Question 9 Explanation:
 Question 10
Let S be a set of consisting of 10 elements. The number of tuples of the form (A,B) such that A and B are subsets of S, and $A\subseteq B$ is _______
 A 49049 B 59049 C 3524 D 854
GATE CSE 2021 SET-2      Set Theory
Question 10 Explanation:

There are 10 questions to complete.