1
GATE CSE 2008
MCQ (Single Correct Answer)
+2
-0.6
Which of the following statements is true for every planar graph on $$n$$ vertices?
A
The graph is connected
B
The graph is Eulerian
C
The graph has a vertex-cover of size at most $$3n/4$$
D
The graph has an independent set of size at least $$n/3$$
2
GATE CSE 2007
MCQ (Single Correct Answer)
+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)$$
3
GATE CSE 2007
MCQ (Single Correct Answer)
+2
-0.6
Which of the following graphs has an Eulerian circuit?
A
Any $$k$$-regular graph where $$k$$ is an even number.
B
A complete graph on 90 vertices.
C
The complement of a cycle on 25 vertices.
D
None of the above.
4
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}$$
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP
Medical
NEETAIIMS
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
Civil Services
UPSC Civil Service
Defence
NDA
Staff Selection Commission
SSC CGL Tier I
CBSE
Class 12