1
Numerical

### GATE CSE 2016 Set 2

The minimum number of colours that is sufficient to vertex-colour any planar graph is _____________ .

2

### GATE CSE 2016 Set 2

A binary relation $R$ on $N \times N$ is defined as follows: $(a,b)R(c,d)$ if $a \le c$ or $b \le d.$ Consider the following propositions:

$P:$ $R$ is reflexive
$Q:$ $R$ is transitive

Which one of the following statements is TRUE?

A
Both $P$ and $Q$ are true
B
$P$ is true and $Q$ is false
C
$P$ is false and $Q$ is true
D
Both $P$ and $Q$ are false
3

### GATE CSE 2016 Set 2

Consider a set $U$ of $23$ different compounds in a Chemistry lab. There is a subset $S$ of $U$ of $9$ compounds, each of which reacts with exactly $3$ compounds of $U.$ Consider the following statements:

$\,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,$ Each compound in $U \ S$ reacts with an odd number of compounds.
$\,\,\,\,\,{\rm I}{\rm I}.\,\,\,\,\,$ At least one compound in $U \ S$ reacts with an odd number of compounds.
$\,\,\,{\rm I}{\rm I}{\rm I}.\,\,\,\,\,$ Each compound in $U \ S$ reacts with an even number of compounds.

Which one of the above statements is ALWAYS TRUE?

A
Only ${\rm I}$
B
Only ${\rm II}$
C
Only ${\rm III}$
D
None
4

### GATE CSE 2016 Set 2

Which one of the following well-formed formulae in predicate calculus is NOT valid?
A
$\left( {\forall xp\left( x \right) \vee \forall xq\left( x \right)} \right) \Rightarrow \left( {\exists x\neg p\left( x \right) \vee \forall xq\left( x \right)} \right)$
B
$\left( {\exists xp\left( x \right) \vee \exists xq\left( x \right)} \right) \Rightarrow \exists x\left( {p\left( x \right) \vee q\left( x \right)} \right)$
C
$\exists x\left( {p\left( x \right) \wedge q\left( x \right)} \right) \Rightarrow \left( {\exists xp\left( x \right) \wedge \exists xq\left( x \right)} \right)$
D
$\forall x\left( {p\left( x \right) \vee q\left( x \right)} \right) \Rightarrow \left( {\forall xp\left( x \right) \vee \forall xq\left( x \right)} \right)$

### Paper Analysis of GATE CSE 2016 Set 2

Subject NameTotal Questions
Algorithms5
Compiler Design3
Computer Networks6
Computer Organization6
Data Structures5
Database Management System4
Digital Logic3
Discrete Mathematics11
Operating Systems3
Theory of Computation6
General Aptitude10