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.

$${n_3}$$ can be expressed as:

A
$${n_1}$$ $$+$$ $${n_1}$$ $$-$$ $$1$$
B
$${n_1}$$ $$-$$ $$2$$
C
$$\left[ {{{{n_1} + {n_2}} \over 2}} \right]$$
D
$${n_2}$$ $$-$$ $$1$$
2
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$$
3
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
4
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)$$
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP