1
GATE CSE 2008
MCQ (Single Correct Answer)
+2
-0.6
$$G$$ is a simple undirected graph. Some vertices of $$G$$ are of odd degree. Add a node $$v$$ to $$G$$ and make it adjacent to each odd degree vertex of $$G$$. The resultant graph is sure to be
A
Regular
B
Complete
C
Hamiltonian
D
Euler
2
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$$
3
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)$$
4
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.
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP