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 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
3
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$$
4
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$$
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