Question 1

**1 Section I (10 Marks)** 1. Consider the graph $G$ whose adjacency matrix is provided below. [Marks: 4] $$\begin{bmatrix} 0 & 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 \end{bmatrix}$$ Choose all the correct option(s). (a) The degree of every vertex of $G$ is 2. (b) There are 7 edges in $G$. (c) $G$ has a proper 3-colouring. (d) $G$ is not planar. 2. How many inversions does the permutation 41235 (one-line notation) have ? [Marks: 2] 3. Which of the following options is/are true? [Marks: 4] (a) If $\phi$ is the Euler's totient function, then $\phi(n)$ is odd for all $n > 2$. (b) There is a natural number $n > 3$ for which the numbers $n, n+2, n+4$ are all prime. (c) Let $n \geq 1$. Then $78n + 15$ cannot be a prime. (d) $\sum_{k=1}^{n-1} \binom{n}{k} = 2^n - 2$ for all $n \geq 2$. **2 Section II (20 Marks)** 1. (a) Prove that any permutation of $1, 2, \ldots, n$ can have at most $\dfrac{n(n-1)}{2}$ inversions. [Marks: 5] (b) Construct an example of a permutation of $\{1, 2, 3, 4, 5\}$ with exactly 7 inversions. [Marks: 5] 2. (a) In a classroom, there are 25 students. Each student is asked to choose any number from 1 to 10. Prove that there must exist a number which is chosen by at least 3 students. [Marks: 5] (b) More generally, fix a natural number $n$. Suppose there are $k$ students in the class and each of them chooses a number from 1 to 10. Find the minimum value of $k$ to guarantee that some number will be chosen by at least $n$ students? [Marks: 5]