GATE CSE 2008 | Graph Theory Question 50 | Discrete Mathematics

GATE CSE 2008

MCQ (Single Correct Answer)

-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:

$${n_1}$$ $$+$$ $${n_1}$$ $$-$$ $$1$$

$${n_1}$$ $$-$$ $$2$$

$$\left[ {{{{n_1} + {n_2}} \over 2}} \right]$$

$${n_2}$$ $$-$$ $$1$$

GATE CSE 2008

MCQ (Single Correct Answer)

-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$$?

For every subset of $$k$$ vertices, the induced subgraph has at most $$2k-2$$ edges

The minimum cut in $$G$$ has at least two edges

There are two edge-disjoint paths between every pair of vertices

There are two vertex-disjoint paths between every pair of vertices

GATE CSE 2008

MCQ (Single Correct Answer)

-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

Regular

Complete

Hamiltonian

Euler

GATE CSE 2008

MCQ (Single Correct Answer)

-0.6

Which of the following statements is true for every planar graph on $$n$$ vertices?

The graph is connected

The graph is Eulerian

The graph has a vertex-cover of size at most $$3n/4$$

The graph has an independent set of size at least $$n/3$$