1
GATE CSE 2008
MCQ (Single Correct Answer)
+2
-0.6
A binary tree with $$n>1$$ nodes has $${n_1}$$, $${n_2}$$ and $${n_3}$$ nodes of degree one, two and three respectively. The degree of a node is defined as the number of its neighbours.

Starting with the above tree, while there remains a node $$v$$ of degree two in the tree, add an edge between the two neighbours of $$v$$ and then remove $$v$$ from the tree. How many edges will remain at the end of the process?

A
$${2^ * }{n_1} - 3$$
B
$${n_2} + {2^ * }{n_1} - 2$$
C
$${n_3} - {n_2}$$
D
$${n_2} + {n_1} - 2$$
2
GATE CSE 2008
MCQ (Single Correct Answer)
+2
-0.6
$$G$$ is a graph on $$n$$ vertices and $$2n-2$$ edges. The edges of $$G$$ can be partitioned into two edge-disjoint spanning trees. Which of the following in NOT true for $$G$$?
A
For every subset of $$k$$ vertices, the induced subgraph has at most $$2k-2$$ edges
B
The minimum cut in $$G$$ has at least two edges
C
There are two edge-disjoint paths between every pair of vertices
D
There are two vertex-disjoint paths between every pair of vertices
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
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