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?
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?
This procedure results in a proper vertex coloring of G. | |
The number of colors used is at most \Delta (G)+1. | |
The number of colors used is at most \Delta (G). | |
The number of colors used is equal to the chromatic number of G. |
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 and B are independent. | |
A and C are independent. | |
B and C are independent. | |
Prob(B|C) = Prob(B) |
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?
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?
H is a group. | |
Every element in H has an inverse, but H is NOT a group. | |
For every A \in 2^X, the inverse of A is the complement of A. | |
For every A \in 2^X, the inverse of A is A. |
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_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?
F is NOT well-defined. | |
F is an onto (or surjective) function. | |
F is a one-to-one (or injective) function. | |
F is a bijective 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?
- 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?
n! | |
\binom{n}{2k} (n-2k)! | |
\binom{n}{2k} (n-2k)! (k!)^2 | |
2 \binom{n}{2k} (n-2k)! (k!)^2 |
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?
\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?
\exists x\left [P(x)\wedge \forall yQ(x,y) \right ] | |
\forall x \forall y Q(x,y) | |
\exists y \forall x \left [P(x) \Rightarrow Q(x,y) \right ] | |
\exists x \left [P(x) \wedge \exists y Q(x,y) \right ] |
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?
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?
L_n=\left ( \frac{1+\sqrt{5}}{2} \right )^n+\left ( \frac{1-\sqrt{5}}{2} \right )^n | |
L_n=\left ( \frac{1+\sqrt{5}}{2} \right )^n - \left ( \frac{1-\sqrt{5}}{3} \right )^n | |
L_n=\left ( \frac{1+\sqrt{5}}{2} \right )^n+\left ( \frac{1-\sqrt{5}}{3} \right )^n | |
L_n=\left ( \frac{1+\sqrt{5}}{2} \right )^n- \left ( \frac{1-\sqrt{5}}{2} \right )^n |
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
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 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
\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 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

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 10 Explanation:
There are 10 questions to complete.