1
GATE CSE 2007
+2
-0.6
Let Graph$$(x)$$ be a predicate which denotes that $$x$$ is a graph. Let Connected$$(x)$$ be a predicate which denotes that $$x$$ is connected. Which of the following first order logic sentences DOES NOT represent the statement: $$Not\,\,\,every\,\,\,graph\,\,\,is\,\,\,connected?$$
A
$$\neg \forall x\left( {Graph\left( x \right) \Rightarrow Connected\left( x \right)} \right)$$
B
$$\exists x\left( {Graph\left( x \right) \wedge \neg Connected\left( x \right)} \right)$$
C
$$\neg \forall x\left( {\neg Graph\left( x \right) \vee Connected\left( x \right)} \right)$$
D
$$\forall x\left( {Graph\left( x \right) \Rightarrow \neg Connected\left( x \right)} \right)$$
2
GATE CSE 2006
+2
-0.6
The $${2^n}$$ vertices of a graph $$G$$ correspond to all subsets of a set of size $$n$$, for $$n \ge 6$$. Two vertices of $$G$$ are adjacent if and only if the corresponding sets intersect in exactly two elements.

the number of vertices of degree zero in $$G$$ is

A
$$1$$
B
$$n$$
C
$$n + 1$$
D
$${2^n}$$
3
GATE CSE 2006
+2
-0.6
The $${2^n}$$ vertices of a graph $$G$$ correspond to all subsets of a set of size $$n$$, for $$n \ge 6$$. Two vertices of $$G$$ are adjacent if and only if the corresponding sets intersect in exactly two elements.

The maximum degree of a vertex in $$G$$ is

A
$$\left( {\mathop 2\limits^{n/2} } \right){2^{n/2}}$$
B
$${2^{n - 2}}$$
C
$${2^{n - 3}} \times 3$$
D
$${2^{n - 1}}$$
4
GATE CSE 2006
+2
-0.6
Consider the undirected graph $$G$$ defined as follows. The vertices of $$G$$ are bit strings of length $$n$$. We have an edge between vertex $$u$$ and vertex $$v$$ if and only if $$u$$ and $$v$$ differ in exactly one bit position (in other words, $$v$$ can be obtained from $$u$$ by flipping a single bit). The ratio of the choromatic number of $$G$$ to the diameter of $$G$$ is
A
$$1/{2^{n - 1}}$$
B
$$1/n$$
C
$$2/n$$
D
$$3/n$$
GATE CSE Subjects
Discrete Mathematics
Programming Languages
Theory of Computation
Operating Systems
Digital Logic
Computer Organization
Database Management System
Data Structures
Computer Networks
Algorithms
Compiler Design
Software Engineering
Web Technologies
General Aptitude
EXAM MAP
Joint Entrance Examination