**Q.1. **Let G=(V, E) be a graph. Define $\xi(G) = \sum\limits_d i_d*d$, where $i_d$ is the number of
vertices of degree d in G. If S and T are two different trees with $\xi(S) = \xi(T)$, then

**(A) **|S| = 2|T|
**(B) **|S| = |T| - 1
**(C) **|S| = |T|
**(D) **|S| = |T| + 1

**Sol : ** $\xi(G)$ basically is the sum of degrees of all vertices in a graph. If sum of degrees of two different trees are same,
then number of nodes in the trees has to be same. We prove this by induction on sum of degree of all vertices in the two trees.

- Base case : When $\xi(S) = \xi(T) = 1$, then we have only single node in both trees and hence |S| = |T|.
- Induction hypothesis : Assume, for $\xi(S) = \xi(T) = k$, we have |S| = |T|.
- Induction step : For $\xi(S) = \xi(T) = k+1$, we must add a leaf vertex in both trees, and hence |S| = |T|.

**Q.2. **Newton-Raphson method is used to compute a root of the equation $x^2 - 13 = 0$
with 3.5 as the initial value. The approximation after one iteration is

**(A) **3.575
**(B) **3.676
**(C) **3.667
**(D) **3.607

**Sol : **We know that, according to Newton-Raphson method,
$$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$$
In this question $f(x) = x^2-13$, and so $f'(x) = 2x$.

Here current $x_n = 3.5$, $f(x_n) = f(3.5) = -0.75$, and $f'(x_n) = f'(3.5) = 7$. So
$$x_{n+1} = 3.5 - \frac{-0.75}{7} = 3.607$$
So option **(D)** is correct.

See also Q.2.15 (2002), Q.42 (2003), Q.28 (2007) and Q.22 (2008).

**Q.3. **What is the possible number of reflexive relations on a set of 5 elements?

**(A) **$2^{10}$
**(B) **$2^{15}$
**(C) **$2^{20}$
**(D) **$2^{25}$

**Sol : ** Consider a table of size 5*5 in which each possible pair is listed. In a reflexive relation, we must include
all 5 diagonal elements. So from rest of the 20 elements, we have choice whether to include them or not. So we have $2^{20}$
possible reflexive relations. So option **(C)** is correct.

**Q.4. **Consider the set S = $\{1, ω, ω^2\}$, where $ω$ and $ω^2$ are cube roots of unity. If *
denotes the multiplication operation, the structure (S, *) forms

**(A) **A Group
**(B) **A Ring
**(C) **An integral domain
**(D) **A field

**Sol : ** We can directly answer this question as "A Group", because other three options require two operations over structure,
but let us see whether (S, *) satisfies group properties or not.

- Closure : If we multiply any two elements of S, we get one of three elements of S, so S is closed over *.
- Associativity : multiplication operation is anyway associative.
- Identity element : 1 is identity element of S.
- Inverse element : inverse of 1 is 1 because 1 * 1 = 1, inverse of $ω$ is $ω^2$, because $ω * ω^2 = 1$. Also inverse of $ω^2$ is $ω$, because $ω^2 * ω = 1$

So option

**Q.5. **What is the value of $\lim_{n \to \infty}\left(1 - \frac{1}{n}\right)^{2n}$ ?

**(A) **0
**(B) **$e^{-2}$
**(C) **$e^{-1/2}$
**(D) **1

**Sol : ** We know that $\lim_{n \to \infty}\left(1 - \frac{1}{n}\right)^{n} = e^{-1}$, so
$$\lim_{n \to \infty}\left(1 - \frac{1}{n}\right)^{2n} = e^{-2}$$. So option **(B)** is correct.

**Q.26. **Consider a company that assembles computers. The probability of a faulty
assembly of any computer is p. The company therefore subjects each
computer to a testing process. This testing process gives the correct result for
any computer with a probability of q. What is the probability of a computer
being declared faulty?

**(A) **pq + (1 - p)(1 - q)
**(B) **(1 - q)p
**(C) **(1 - q)p
**(D) **pq

**Sol : **P(declared faulty) = P(actually faulty)*P(declared faulty|actually faulty) +
P(not faulty)*P(declared faulty|not faulty) = p*q + (1-p)*(1-q).

So option **(A)** is correct.

**Q.27. **What is the probability that divisor of $10^{99}$ is a multiple of $10^{96}$?

**(A) **1/625
**(B) **4/625
**(C) **12/625
**(D) **16/625

**Sol : ** Divisiors of $10^{99}$ are of the form $2^a*5^b$, where a and b can go from 0 to 99 each, so there are 10000 divisors
of $10^{99}$. Now Any of those divisors would be a multiple of $10^{96}$ if both a and b are atleast 96 i.e. 96, 97, 98, or 99.
So each of a and b have 4 choices each, and so there are 16 divisiors which are multiple of $10^{96}$.

So prob = 16/10000 = 1/625, so option **(A)** is correct.

**Q.28. **The degree sequence of a simple graph is the sequence of the degrees of the
nodes in the graph in decreasing order. Which of the following sequences can not
be the degree sequence of any graph?

I. 7, 6, 5, 4, 4, 3, 2, 1
II. 6, 6, 6, 6, 3, 3, 2, 2
III. 7, 6, 6, 4, 4, 3, 2, 2
IV. 8, 7, 7, 6, 4, 2, 1, 1

**(A) **I and II
**(B) **III and IV
**(C) **IV only
**(D) **II and IV

**Sol : **This can be solved using havel hakimi theorem, which says :

- First arrange degree sequence in decreasing order.
- Remove 1st vertex, and let its degree be k, then subtract 1 from next k vertices.
- If all vertices have degree 0, then answer is yes i.e. given degree seqeunce can be a degree sequence for a graph. If any vertex has degree < 0, then answer is no, otherwise repeat step 2.

- 7, 6, 5, 4, 4, 3, 2, 1. Here first vertex has degree 7, so remove this first vertex, and then subtract 1 from next 7 vertices, so we get 5,4,3,3,2,1,0. Then we get 3,2,2,1,0,0, then 1,1,0,0,0, and then 0,0,0,0. So answer is yes.
- 6, 6, 6, 6, 3, 3, 2, 2. Here first vertex has degree 6, so remove this first vertex, and then subtract 1 from next 6 vertices, so we get 5, 5, 5, 2, 2, 1, 2. Then we get 4, 4, 1, 1, 0, 2, then 3, 0, 0, -1, 2. Since degree of a vertex becomes negative, this degree sequence is not possible.

**Q.29. **Consider the following matrix
$$A = \left[\begin{array}{cc}2 & 3\\x & y \end{array}\right]$$
If the eigenvalues of A are 4 and 8, then

**(A) **x = 4, y = 10
**(B) **x = 5, y = 8
**(C) **x = -3, y = 9
**(D) **x = -4, y = 10

**Sol : **Characteristic equation for given matrix is
$$(2-λ)(y-λ)-3x = 0$$
Putting λ = 4 and 8, we get 2 equations :
$$3x+2y = 8$$
$$3x+6y = 48$$
Solving both equations, we get x = -4, y = 10. So option **(D)** is correct.

**Q.30. **Suppose the predicate F(x, y, t) is used to represent the statement that person x
can fool person y at time t. which one of the statements below expresses best
the meaning of the formula ∀x∃y∃t(¬F(x,y,t))?

**(A) **Everyone can fool some person at some time

**(B) **No one can fool everyone all the time

**(C) **Everyone cannot fool some person all the time

**(D) **No one can fool some person at some time

**Sol : **The formula ∀x∃y∃t(¬F(x,y,t)) says that for every person x, there exists a person y, and there
exists a time t, such that x cannot fool y at time t i.e. No person can fool everyone all the time. So option **(B)** is correct.
Alternatively, you can bring negation outside, thus swapping ∀ and ∃, and so statement becomes
¬(∃x∀y∀t(F(x,y,t)) i.e. there does not exist a person who can fool everyone at everytime, which is again option **(B)**.