1
GATE CSE 2006
MCQ (Single Correct Answer)
+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}$$
2
GATE CSE 2006
MCQ (Single Correct Answer)
+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}}$$
3
GATE CSE 2006
MCQ (Single Correct Answer)
+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$$
4
GATE CSE 2005
MCQ (Single Correct Answer)
+2
-0.6
Which one of the following graphs is NOT planar? GATE CSE 2005 Discrete Mathematics - Graph Theory Question 20 English
A
G1
B
G2
C
G3
D
G4
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP
Medical
NEET
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
CBSE
Class 12