Question 1 |
Which of the properties hold for the adjacency matrix A of a simple undirected unweighted graph having n vertices?
MSQ
MSQ
The diagonal entries of A^2 are the degrees of the vertices of the graph. | |
If the graph is connected, then none of the entries of A^{n-1}+I_ncan be zero. | |
If the sum of all the elements of A is at most 2(n-1), then the graph must be acyclic. | |
If there is at least a 1 in each of A's rows and columns, then the graph must be connected. |
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
\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
f(2^n-1)=2^n-1 | |
f(2^n)=1 | |
f(5 \dot 2^n)=2^{n+1}+1 | |
f(2^n+1)=2^n+1 |
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

Which of the following statements is/are TRUE?
MSQ
The chromatic number of the graph is 3. | |
The graph has a Hamiltonian path. | |
The following graph is isomorphic to the Peterson graph. ![]() | |
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.) |
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^3 | |
A^3 divided by 2 | |
A^3 divided by 3 | |
A^3 divided by 6 |
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_n= \left \{ \begin{matrix} n+1, &n \text{ is odd} \\ 1,& \text{otherwise} \end{matrix} \right.
\frac{x(1+x^2)}{(1-x^2)^2}+\frac{1}{1-x} | |
\frac{x(3-x^2)}{(1-x^2)^2}+\frac{1}{1-x} | |
\frac{2x}{(1-x^2)^2}+\frac{1}{1-x} | |
\frac{x}{(1-x^2)^2}+\frac{1}{1-x} |
Question 5 Explanation:
Question 6 |
The number of arrangements of six identical balls in three identical bins is ____.
7 | |
8 | |
12 | |
5 |
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 .
72 | |
36 | |
16 | |
48 |
Question 7 Explanation:
Question 8 |
Which of the following statements is/are TRUE for a group G?
MSQ
MSQ
If for all x,y \in G, (xy)^2=x^2y^2, then G is commutative. | |
If for all x \in G, x^2=1, then G is commutative. Here, 1 is the identity element of G. | |
If the order of G is 2 , then G is commutative. | |
If G is commutative, then a subgroup of G need not be commutative. |
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 ______

The sum of the quality-scores of all vertices on the graph shown above is ______
929 | |
254 | |
639 | |
879 |
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 _______
49049 | |
59049 | |
3524 | |
854 |
Question 10 Explanation:
There are 10 questions to complete.