Discrete Mathematics

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?

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?

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?

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?

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?

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?

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?

Which of the properties hold for the adjacency matrix A of a simple undirected unweighted graph having n vertices?
MSQ

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

The following simple undirected graph is referred to as the Peterson graph.

Which of the following statements is/are TRUE?
MSQ